所有排列的有效计算
所有排列的有效计算
提问于 2014-04-03 14:04:54
受到一个含糊不清的问题的启发，我感到很难解决对它的更严格的解释，具体如下：
如何最有效地计算所有可能包含n个零(0位数)的整数值(32位值)？例如，给定n= 7，包含确切7个零的不同整数值的数目是：
32*31*30*29*28*27*26 / (1*2*3*4*5*6*7) = 3.365.856具有确切7个零的整数值示例如下：
11111111000000011111111111111111如果你想自己解决这个问题，不要读我的答案。否则，评估我的答案，改进它或张贴一个更好，更有效的答案。
Stack Overflow用户
发布于 2014-04-03 14:04:54
我的算法的思想如下：
- 创建一个整数值，其右侧(最小有效位)的零数与函数
permut()的值相同。 - 开始将最左边的零点一点一点地移到左边。
- 将移动零点右侧的所有位作为目标值，并将相同的算法应用于缩短值。
该算法有两个重要的特点：
- 它是递归的。
- 它需要与值一样多的计算量来计算。
在这里，算法作为Java代码：
public static void main(String[] args) {
List<Integer> permutations = permut(7);
}
private static List<Integer> permut(int zeros) {
List<Integer> permutations = new ArrayList<>();
permut(zeros == 32 ? 0 : 0xFFFFFFFF << zeros, zeros, 31, permutations);
return permutations;
}
/*
* @param value
* for which to move the zero digit at bit position (zeros - 1)
* to the stopBit position
* @param zeros
* number of 0 digits available at the right most bit positions
* of value
* @param stopBit
* the left most bit position to move the zero digit at bit position
* (zeros - 1) to
* @param values
* to add the newly calculated integer values to
*/
private static void power(int value, int zeros, int stopBit, List<Integer> values) {
values.add(value);
if (zeros == 0) return;
int cleared = value | (1 << (zeros - 1));
for (int bit = zeros - 1; bit < stopBit;) {
power(cleared ^ (1 << ++bit), zeros - 1, bit - 1, values);
}
}如果您对算法的行为是否正确感到好奇，请使用修改后的main()方法尝试以下检查方法：
public static void main(String[] args) {
int zeros = 7;
List<Integer> permutations = permut(zeros);
System.out.println("Expected number of values: " + combinations(zeros));
System.out.println("Returned number of values: " + permutations.size());
System.out.println("Returned values are unique: " + (new HashSet<>(permutations).size() == permutations.size()));
System.out.printf("All values contain %d zeros: %s\n", zeros, haveZeros(zeros, permutations));
}
private static long combinations(int zeros) {
long p = 1;
long q = 1;
for (int count = 0; count < zeros;) {
p *= (32 - count);
q *= (++count);
}
return p / q;
}
private static boolean haveZeros(int zeros, List<Integer> values) {
for (Integer value : values) {
int count = 0;
for (int bit = 1; bit != 0; bit = bit << 1) {
if ((value & bit) == 0) count++;
}
if (count != zeros) {
System.out.println(Integer.toBinaryString(value));
return false;
}
}
return true;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22840189
复制相关文章
相似问题
腾讯云开发者
