c++ - 我想获得一组唯一的 n*n 数组，这些数组在 c++ 中的随机位置仅包含 0 或 1

Question

我想获取一组 n*n 数组，包括 0 或 1

但是，每个元素必须彼此不同。

例如，

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 位值，使用数组的每个元素中的计数器中的一个位创建一个数组。这将生成 2 ^N0个唯一数组（即， s 和s的最大可能数量1）。

Answer 2

您可以利用next_permutation这一点。以下为您提供 n 大小的 0 和 1 数组的每种组合：

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.

Answer 3

如果您的矩阵很大（n >= 12），那么您可以简单地生成一个随机矩阵，并且具有压倒性的概率（假设您的 PRNG 很好），您将获得唯一的矩阵。（两个随机 12x12 矩阵相同的几率小于 2^70 分之一，或大约 10^21 分之一）。

在 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