c++ - C ++でランダムな場所に0または1のみを含むn * n配列の一意のセットを取得したい

Question

0 または 1 を含む n*n 配列のセットを取得したい

しかし、それぞれの要素は互いに異なっていなければなりません。

例えば、

arr[3][3] = {{0,1,0},
             {1,0,0},
             {1,1,1}}
arr2[3][3] = {{0,1,1},
              {1,1,1},
              {0,0,1}}

上記のように、一意の配列が必要です。

Answer 1

N個の要素の配列の場合、Nビットの数値を取り、それをカウンターとして使用します。Nビット値ごとに、配列の各要素のカウンターからのビットの1つを使用して配列を作成します。^{これにより、2 N個}の一意の配列が生成されます（つまり、その数の0sと1sで可能な最大数）。

Answer 2

マトリックスが大きい場合 (n >= 12)、単純にランダムなマトリックスを生成でき、圧倒的な確率で (PRNG が良好であると仮定して)、一意のマトリックスが得られます。(2 つのランダムな 12x12 行列が同一である確率は、2^70 に 1 未満、または 10^21 に約 1 です)。

C++11 では、mt19937乱数ジェネレーターを使用して、多数の高品質の乱数を生成できます。

#include <iostream>
#include <random>

main() {
    std::mt19937 generator;
    std::uniform_int_distribution<int> distribution(0,1);
    int n = 12;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            std::cout << distribution(generator);
        }
        std::cout << std::endl;
    }
}

出力例:

101101101001
001111110111
100110000011
111111001011
101110001000
110001000111
100110010000
101000000011
111101101101
000111011100
110111101011
100100011100

Answer 3

これを活用できますnext_permutation。以下は、0 と 1 の n サイズの配列のすべての組み合わせを取得します。

std::vector<int> root(4, 1);
std::vector<std::vector<int>> vec(1, root);

for(auto i = root.begin(); i != root.end(); ++i)
{
    *i = 0;
    do {
        vec.push_back(root);
    } while(std::next_permutation(root.begin(), root.end()));
}

ここでnは 4 です。組み合わせは に含まれていvecます。