给定一个仅包含不同数量的数字 1、2、3 和 4 的序列（例如：13244、4442 等），我想计算其所有排列，以便没有两个相邻的数字是相同的。我相信它是 O(N! * N) 并且想知道是否有更好的。有人有主意吗？
class Ideone
{
static int permutationCount++;
public static void main(String[] args) {
String str = "442213";
permutation("", str);
System.out.println(permutationCount);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0){
boolean bad = false;
//Check whether there are repeating adjacent characters
for(int i = 0; i < prefix.length()-1; i++){
if(prefix.charAt(i)==prefix.charAt(i+1))
bad = true;
}
if(!bad){
permutationCount++;
}
}
else {
//Recurse through permutations
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
}
我是这样理解你的问题的：给定一个仅包含数字 1,2,3,4 的字符串 - 这些字符存在多少种排列，当您再次将它们放入字符串中时，将不会有任何相同的相邻数字。
我建议采用这种方法：
L - length of your string
n1 - how many times is 1 repeated, n2 - how many times is 2 repeated etc.
P - number of all possible permutations
P = L! / (n1!*n2!*n3!*n4!)
C - number of all solutions fitting your constraint
C = P - start with all permutations
substract all permutations which have 11 in it (just take 11 as one number)
C = C - (L - 1)! / ((n1 - 1)! * n2! * n3! * n4!)
... do the same for 22 ...
add all permutations which have both 11 and 22 in it (because we have substracted them twice, so you need to add them)
C = C + (L - 2)! / ((n1 - 1)! * (n2 - 1)! * n3! * n4!)
... repeat previous steps for 33 and 44 ...
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
