时间戳

首页 > 解决方案 > C++ 一组字符串的所有排列

c++ - C++ 一组字符串的所有排列

问题描述

我正在尝试在向量中生成所有字符串排列。例如，对于

vector<string> vs = { "a", "b", "c"};

我写了以下代码：

do{
    for (string s : vs)
        cout << s << " ";
    cout << endl;
} while (std::next_permutation(vs.begin(), vs.end()));

我的输出是：

abc
acb
bac
bca
出租车
cba

但是，我错过了像这样的组合


ab
b
c _

ETC..

我想修改我的代码，以便也包括这些安排。怎么做？谢谢！

标签： c++combinations

解决方案

您的示例表明，您不仅希望输出输入的每个子集（Power set），而且还希望输出每个集合的所有排列。

我不知道用于此的特定术语，但OEIS A000522将这些称为“安排”。

为了得到你需要的东西，你必须将你的代码与 Jarod 的部分答案（或你可以在这里找到的任何其他电源集实现）结合起来：

void outputAllPermutations(std::vector<std::string> input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    do
    {
        for (std::string s : input)
            std::cout << s << " ";
        std::cout << std::endl;
    } while (std::next_permutation(input.begin(), input.end()));
}

bool isBitSet(unsigned bitset, std::size_t i)
{
    return (bitset & (1 << i)) != 0;
}

void outputAllArrangements(const std::vector<std::string>& input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    // assert(input.size() < std::sizeof(unsigned) * 8);

    unsigned bitset = 0;

    std::vector<std::string> subset{};
    subset.reserve(input.size());

    for (unsigned bitset = 0; bitset < (1 << input.size()); ++bitset)
    {
        subset.clear();
        for (std::size_t i = 0; i != input.size(); ++i)
            if (isBitSet(bitset, i))
                subset.push_back(input[i]);

        outputAllPermutations(subset);
    }
}

包含示例输出的演示

我使用了 anunsigned而不是，std::vector<bool>因为我发现整体增量逻辑更容易以这种方式进行推理。从理论上讲，这将代码“限制”为小于 32 个字符串（或 64 个，具体取决于平台）的输入，但是看到输入长度 22 已经需要数千年才能以每个输出 1 个 CPU 周期输出，我对此感到满意。

推荐阅读