c - bool 数组的排列

Question

如果我有一个长度为 n 的 bool 值数组，我该如何迭代该数组的所有可能排列？

例如，对于大小为 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]

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

Answer 1

在二进制中实现“加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]