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.
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]
n <= 30 (if you have 32-bit ints), otherwise 1 << n causes undefined behaviour. The limit could be increased to n <= 63 with some code modifications.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.
to make general C language solution (as soon as question tag is C) for vector of length n you can use binary representation of integer variable i: [0,2^n) where n is length of array and within single loop iterate all vectors using bitwise operators.
^ is the XOR operator in CUsing GMP can make this a little easier, particularly if you don't really need actual arrays, just something you can test the bits of:
#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);
