Permutations of a boolean array

Question

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 1

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

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]

Answer 2

If you actually need every permutation of the array. A cleaner method can be std::next_permutation()

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

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

Theoretical Complexity will be same as "add 1" or other methods. Plus only STL will do the work for you.