piper1935 - 1 year ago 61

C 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 Source

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