piper1935 piper1935 - 2 months ago 6
C Question

Permutations of a boolean array

If I have an array of boolean values of n length, how can I iterate over all possible permutations of the array?

For example, for an array of size 3, there are eight possible permutations:

[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. I am working in C, although I'm not necessarily looking for a language specific answer. Just trying to find an efficient algorithm to do this with large arrays and many possible permutations.

Answer

Implement "add 1" in binary:

#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[] = { 0, 0, 0 };
  for (int i = 0; i < 8; i++) {
    print(a, 3);
    add1(a, 3);
  }
}

Compile and run:

$ 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]