corresponding permutation number

Question

I have a given word, for wich I need to find its number of permutation on its corresponding sorted word . Say I have word BABA , its corresponding sorted word would be, AABB, if I start permuting this sorted word, would come to AABB as a second "word", regardless of letter repetition, then ABAB, ABBA , BABA .. so the permute number for word BABA is 5 . The easy way would be start doing all possible combinations, and then compared with the initial word . so far , ive done..

import java.util.Arrays;

public class Permutation {
 int location =1;
public static char[]  warray;

void printArray(char []a) {
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
  System.out.println("location " + location );
}
 void permute(char []a,int k ) {
  if(k==a.length) {
     location++;
  // Check if the permuted word is the one looking for.
 if (Arrays.equals(a, warray))
  { System.out.println("final iteration k" + k);        
  printArray(a); 
  System.exit(0);}
  }
else
   for (int i = k; i < a.length; i++) {
   char temp=a[k];
   a[k]=a[i];
   a[i]=temp;
    permute(a,k+1);
   }
}

public static void main(String[] args) {
  if (args[0].length() > 25 )  {
     System.out.println(" Word not in permited range " );        
     System.exit(0);
 }
 else {
 Permutation p=new Permutation();
 warray = new char[args[0].length()];
  char [] wpermute = new char[args[0].length()];

for (int i = 0; i < args[0].length(); i++) {
     warray[i] = new Character(args[0].charAt(i));
     wpermute[i] = new Character(args[0].charAt(i));
 }

Arrays.sort(wpermute);

System.out.print("sorted word : " );
for (int i = 0; i < wpermute.length; i++) {
  System.out.print(wpermute[i]);
  }
  p.permute(wpermute,0);
  }
}

---

But this could be very slow performance. My second guess, would be , starting like a binary search startting with first letter of unsorted word, calculate possibble permutations to have this letter as the first letter on permutations, and then second letter..and so ... would that sound good ?

Answer 1

If you only have 2 letters and if the length of the word is N and the number of A's is n then the number of permutations is N choose n.

If you have N letters total and n_a, n_b, ..., n_z describe the number of each letter then the total number of permutations is

N!/(n_a! n_b! n_c! ... n_z!)

Check out Multinomials, scroll down to the bit on permutations.

Answer 2

Another word would be QUESTION , its sorted word is EINOQSTU . for question , q is in position 1 , and in postion 5 in the new word, how many permutations need to do to put is in postion 1 = 20161 . Now I take second letter in question, is U, which is in position 8 in sorted word , how many permutations need to do, is 24481

I think, I could calculate , not perform, the number permutations needed to put a letter in y position, to be in X position. and then , the sum of all , would be the permutations needed for the whold word.

Now, how to calculate those numbers, I know has to be with factorial plus something else ..is not ?

Answer 3

So I finally completed the code, and yes, needed to check the multinomials. also got part of the idea from a related post here. But here my code.

package WordPuzzle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/** Rafael G.  */

public class WordPuzzle {

    static String sortWord (String[] wordinput){
        char [] wsorted = new char[wordinput[0].length()];
        wsorted = wordinput[0].toCharArray();
        Arrays.sort(wsorted);
        String aux="";
        for (int i = 0; i < wsorted.length; i++) {
            aux = aux + wsorted[i];
        }   
        return aux;
    }

    static void calculatePerm(String wordtofind,String wordsorted)
    {
        int sum = 0;
        int numberpermutations;
        char nextchar;
        int charlocremainder =0;
        String lowerLetters;
        String greaterLetters;

        Map<Character, Integer> characterCounts = new HashMap<Character, Integer> ();
        int count ;
        char letter;
        int factorial;
        int [] factorials = new int [wordsorted.length()+1];

        factorial =1;        
        numberpermutations = 1;
        int nMinusI;
        int nextcharcount;

        // set a mapping of repeated letters and its number 
        // and store factorial calculation.
        for (int i = 0; i < wordsorted.length(); i++) {
            letter = wordsorted.charAt(i);
            factorial = factorial * (i+1);
            factorials[i+1]= factorial;
            count = characterCounts.containsKey(letter) ? characterCounts.get(letter) + 1 : 1;
            characterCounts.put(letter, count);
           }

        String trimWord = new String(wordsorted);

        for (int i = 0; i < wordtofind.length() ; i++){
            nMinusI = wordtofind.length()-(i+1);
            nextchar = wordtofind.charAt(i);
            charlocremainder = trimWord.indexOf(nextchar);
            lowerLetters = trimWord.substring(0, charlocremainder); 

            // Calculate the denominator  which is the number of repeated letters
            // of the formula (N-i)! * (Na+Nb) /Na!Nb!.. 
              nextcharcount = characterCounts.get(nextchar);
              characterCounts.put(nextchar, nextcharcount-1);
              int denomfact = factorials[nextcharcount];
              if (lowerLetters.length() > 1){
                   char x = lowerLetters.charAt(0);
                   char y = x;
                  for (int k = 1 ; k < lowerLetters.length(); k++){
                      y = lowerLetters.charAt(k);
                      if (x != y) {
                          denomfact = denomfact * factorials[characterCounts.get(x)];
                          x = y;
                      }
                     }
                     denomfact = denomfact * factorials[characterCounts.get(y)];
                   }

            numberpermutations = factorials[nMinusI] * lowerLetters.length() / denomfact;
            sum = sum + numberpermutations;
            greaterLetters= trimWord.substring(charlocremainder+1);         
            trimWord = lowerLetters.concat(greaterLetters);

        }
           System.out.println(" Rank of permutation " + (sum+1));
    }

    /**
     * @param args the command line arguments
     */

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        String wordsorted;
        String wordentered;

        if (args[0].length() > 25 )  {
            System.out.println("Word not in permited range " );        
            System.exit(0);
        }
        else {
            wordentered = args[0].toUpperCase();
            wordsorted = sortWord(args).toUpperCase();
            calculatePerm(wordentered,wordsorted);
        }

        long endTime = System.nanoTime();
        System.out.println("Took "+(endTime - startTime)/1000000000.0 + " seconds");
        System.out.println("Took "+(endTime - startTime)* 0.000001 + " milliseconds");
    }

 }