c++ - 生成有序配对

Question

我有一个非重复对象的列表。我要提取所有的安排

e.g 
    {A, B, C, D}
    ->
    [A, B, C, D]      
    [A, B, CD]
    [A, BC, D]
    [AB, C, D]
    [AB, CD]
    [ABC, D]
    [A, BCD]
    [ABCD]

秩序需要得到尊重。我可以蛮力解决方案，但有没有我可以研究用于上述问题的优雅解决方案或算法？

谢谢彼得

标签： c++algorithm

Answer 1

如果您有n个按顺序排列的项目，则在这些项目之间有 n-1 个插槽，其中可以放置“分隔符”。因此，总共有 2^( n -1) 种划分项目的方法——将它们之间没有分隔符的项目分组，以获取所有可能的放置分隔符的方式。

这将转换为 C++ 代码，如下所示：

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

template <typename T>
std::vector<std::vector<T>> GetPartitionFromIndex(const std::vector<T>& items, int index)
{
    std::vector<std::vector<T>> partition = { {} };

    for (int i = 0; i < items.size(); i++) {
        partition.back().push_back(items[i]);
        if (index & (1 << i))
            partition.push_back({});
    }

    return partition;
}

template <typename T>
std::vector<std::vector<std::vector<T>>> OrderedPartitions(const std::vector<T>& items) {
    std::vector<std::vector<std::vector<T>>> partitions;
    auto n = (1 << items.size()-1) - 1;
    for (int partition_index = 0; partition_index <= n; partition_index++)
        partitions.push_back(GetPartitionFromIndex(items, partition_index));

    return partitions;
}

int main()
{
    auto test = OrderedPartitions( std::vector<std::string>{ "A", "B", "C", "D" } );
    std::cout << "ordered partitions:" << std::endl;
    for (auto& partitions : test) {
        for (auto& partition : partitions) {
            auto p = std::accumulate(
                std::next(partition.begin()),
                partition.end(),
                partition[0],
                [](std::string a, std::string b) {
                    return a + "," + b;
                }
            );
            std::cout << "{" << p << "} ";
        }
        std::cout << std::endl;
    }

}

产生

ordered partitions:
{A,B,C,D}
{A} {B,C,D}
{A,B} {C,D}
{A} {B} {C,D}
{A,B,C} {D}
{A} {B,C} {D}
{A,B} {C} {D}
{A} {B} {C} {D}

作为输出。