基于初始输入生成所有组合（n 选择 k）的快速算法

Question

我正在研究应用集覆盖问题。在这项研究中，我想生成所有可能的组合。 IE。 n = 5 和 k = 3 产量

0 0 1
0 0 2 
0 0 3
etc..

这对于较小规模的问题没有问题，但是当 n 和 k 增加时，比如 n = 250 和 k = 6，组合的数量是 3.1920e+11。不能将所有组合存储在一个矩阵中，因此我需要一种算法可以计算 x 组合，然后在给定第一个矩阵的终点的情况下计算 x 下一个组合。有谁知道在 C/C++/CUDA 或 Matlab 中快速执行此操作的任何算法？

谢谢。

Answer 1

我认为你会遇到的最大问题不是计算，而是磁盘写入速度或内存大小。顺便说一下，您似乎错误地确定了 n = 250 和 k = 6 的组合数。你用过uint64_t吗？我的号码是 244 140 625 000 000.

因此，对于这个数字，您需要 ~1.4 Petabyte (~1400 Tb) 的内存。这是你的主要问题。如果你有那么大的硬盘，写的时候最好用memory mapping。您可以考虑使用多个线程来写入：每个线程都会写入自己的内存块。

所以，我认为你应该考虑其他方法来提供组合来解决你的实际目标。

一个天真的解决方案。用内存映射对象更改 std::ofstream。

int main()
{
    const constexpr uint8_t N = 250;
    const constexpr uint8_t K = 6;
    const constexpr uint64_t CombinationsCount = std::pow(N, K);
    using TCombination = std::array<uint8_t, K>;

    std::cout << CombinationsCount << std::endl;

    std::ofstream file("output.txt");
    TCombination c;
    for (uint64_t i = 0; i < CombinationsCount; ++i)
    {
        auto I = i;
        for (auto j = 0; j < K; ++j)
        {
            c[j] = I % N;
            I /= N;
            file << (int)c[j];
        }
        file << std::endl;
    }

}

如果你想使用线程，只需将 CombinationsCount 除以核心数，并给每个线程一个任务，从特定的内存地址（偏移量）写入。

您要求的是类似函数的解决方案。您可以传递不同的文件名并使用不同的线程。买了还是需要用到内存映射

const constexpr uint8_t N = 250;
const constexpr uint8_t K = 6;
const constexpr uint64_t CombinationsCount = std::pow(N, K);
using TCombination = std::array<uint8_t, K>;

void Generate(uint64_t start, uint64_t size, const char* fileName)
{
    std::ofstream file(fileName);
    TCombination c;
    for (uint64_t i = start; i < start + size; ++i)
    {
        auto I = i;
        for (auto j = 0; j < K; ++j)
        {
            c[j] = I % N;
            I /= N;
            file << (int)c[j];
        }
        file << std::endl;
    }
}

int main()
{
    std::cout << CombinationsCount << std::endl;

    unsigned int threadsNum = std::thread::hardware_concurrency();

    std::vector<std::thread> workers;
    for (size_t i = 0; i < threadsNum; ++i)
        workers.emplace_back(
            Generate, 
            i * CombinationsCount / threadsNum,
            CombinationsCount / threadsNum,
            (std::string("output") + std::to_string(i)).c_str());

    for (size_t i = 0; i < threadsNum; ++i)
        workers[i].join();
}

Answer 2

I am working on an applied set-covering problem. In this research I want to generate all possible combinations. ... Does anyone know any algorithms that does this quickly in either C/C++/CUDA or Matlab?

没有生成所有可能组合的东西"quickly"。根据定义，随着 n 和 k 的增加，这非常慢：n!/((n-k)!k!) 上升得比 (k/e)^n 快，渐近地作为 n 的函数；因此，通过使用 GPU 以常数因子加快组合生成速度只会让您将 n and/or k 增加一点点。

抱歉听起来有点说教，但除了尝试生成所有组合之外，您可能需要做一些其他事情。

基于初始输入生成所有组合（n 选择 k）的快速算法

Fast algorithm for generating all combinations (n choose k) based on an initial input

c++

matlab

combinations

combinatorics