布尔数组的排列

Question

如果我有一个长度为 n 的布尔值数组，我如何遍历数组的所有可能排列？

例如，对于大小为 3 的数组，有八种可能的排列：

[0,0,0]
[0,0,1]
[0,1,0]
[0,1,1]
[1,0,0]
[1,0,1]
[1,1,0]
[1,1,1]

P.S。我在 C 中工作，尽管我不一定要寻找特定于语言的答案。只是想找到一种有效的算法来处理大型数组和许多可能的排列。

Answer 1

要为长度为 n 的向量制作通用 C 语言解决方案（只要问题标记为 C），您可以使用整数变量 i 的二进制表示：[0,2^n)，其中 n 是数组的长度并且在单循环使用按位运算符迭代所有向量。

Answer 2

用二进制实现"add 1"：

#include <stdio.h>

void add1(int *a, int len) {
  int carry = 1;
  for (int i = len - 1; carry > 0 && i >= 0; i--) {
    int result = a[i] + carry;
    carry = result >> 1;
    a[i] = result & 1;
  }
}

void print(int *a, int len) {
  printf("[");
  for (int i = 0; i < len; i++) {
    if (i > 0) printf(",");
    printf("%d", a[i]);
  }
  printf("]\n");
}

int main(void) {
  int a[3] = { 0 };
  int n = sizeof a / sizeof a[0];
  for (int i = 0; i < (1 << n); i++) {
    print(a, n);
    add1(a, n);
  }
}

编译并运行:

$ gcc foo.c -o foo
$ ./foo
[0,0,0]
[0,0,1]
[0,1,0]
[0,1,1]
[1,0,0]
[1,0,1]
[1,1,0]
[1,1,1]

Answer 3

使用 GMP 可以让这更容易一些，特别是如果你真的不需要实际的数组，只是一些你可以测试的位：

#include <gmp.h>

...
int numbits = 3;  // Insert whatever you want
mpz_t curperm;
mpz_init(curperm);

for (; mpz_sizeinbase(curperm, 2) <= numbits; mpz_add_ui(curperm, curperm, 1)) {
    ... test specific bits w/mpz_tstbit(curperm, #) instead of array check of curperm[#] ...
}

mpz_clear(curperm);

Answer 4

如果你真的需要数组的每一个排列。更简洁的方法可以是 std::next_permutation()

do{
    std::cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<std::endl;
}

while(std::next_permutation(v.begin(),v.end()));

理论复杂度与"add 1"或其他方法相同。另外，只有 STL 会为您完成这项工作。

布尔数组的排列

Permutations of a boolean array

c

arrays

algorithm

permutation