對應的排列數

Question

我有一個給定的單詞，因爲我需要找到它的相應排序單詞的排列數。 說我有單詞BABA，它的相應排序單詞將是，AABB，如果我開始排列這個排序的單詞，會來AABB作爲第二個「單詞」，無論字母重複，然後ABAB，ABBA，BABA ..所以單詞BABA的排列數是5。 簡單的方法將開始做所有可能的組合，然後與最初的單詞進行比較。 到目前爲止，我已經做了..

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); 
    } 
} 

---

但是，這可能是非常慢的性能。 我的第二個猜測是，從二進制搜索開始，用未排序的單詞的第一個字母開始，計算可能的排列，將這個字母作爲排列的第一個字母，然後是第二個字母......所以...聽起來不錯？

Answer 1

如果您只有2個字母，並且該單詞的長度爲N，並且A的數量爲n，則排列的數量爲N choose n。

如果你有N信道達爾和n_a，n_b，...，n_z描述每個字母的編號，然後排列的總數爲

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

退房Multinomials，向下滾動到位排列。

Answer 2

另一個單詞是QUESTION，它的排序字是EINOQSTU。 對於問題，q在位置1，並且在新詞中的位置5，需要做多少置換以置於位置1 = 20161。 現在我拿第二個字母問題，是U，它是在排序字的位置8，排列次數需要做的是24481

我想，我可以計算，而不是執行需要放置的數字排列在y位置的一個字母，在X位置。然後，所有的總和，就是這個詞所需要的排列組合。

現在，如何計算這些數字，我知道必須與因子加上別的東西..不是嗎？

Answer 3

所以我終於完成了代碼，是的，需要檢查多項式。 也從這裏的相關帖子得到了部分想法。 但在這裏我的代碼。

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"); 
    } 

}