java - 对应的排列数

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 选择n.

如果您总共有 N 个字母，并且 n_a、n_b、...、n_z 描述了数字每个字母的排列总数为

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

查看Multinomials ，向下滚动到排列位。