ブール値配列の順列

Question

ブール値の配列がnの場合、どのように配列のすべての可能な順列を反復処理できますか？

[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.：

例えば、サイズ3のアレイのために、8個の可能な順列が存在します私は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); 
    } 
} 

コンパイルして実行します：GMPを使用して

$ 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

長さnのベクトルに対して一般的なC言語の解を（質問タグがCとなるとすぐに）作るには、整数変数iのバイナリ表現を使うことができます：[0,2^n] nは配列の長さで、ビット演算子を使用してすべてのベクトルをループ反復する。

Answer 3

は、あなたが本当に実際の配列を必要としない場合は特に、これは少し楽に行うことができますちょうど何かのビットをテストすることができます：

#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); 

Answer 4

実際にすべての配列の並べ替えが必要な場合。クリーナー方法はのstd :: next_permutation（）

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

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

ことができる理論的複雑さは、 "追加1" 又は他の方法と同じであろう。プラスだけSTLがあなたのために仕事をします。