关于输出所有n个数字的所有子集的算法问题[重复]

Question

现在我在研究n辆车的通信，我遇到的问题可以简化为：

n个数，我想得到所有的子集，它们满足被划分的条件（如下例）并且所有这n个数都是**全部使用并且只使用一次**。

比如如果n = 3，我可以将它们划分为：

[[1, 2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[2, 3], [1]]
[[1], [2], [3]]

我试过用c++的next_permutation函数来解决（因为它没有任何组合问题的功能）但失败了，因为它输出了太多重复的答案（比如

[1 2][3]

和

[2 1][3]

，它们实际上是相同但我不知道如何识别它们）

我认为我使用这个功能的想法是错误的。

Answer 1

您正在寻找分区，而不是组合或排列。

您可以找到具有 n 成员的集合 S 的分区，注意如果 P(n-1) 是 S-a 的分区，其中 a 是任意的成员，那么你可以构造 P(n) 作为包含 a 的集合，以所有可能的方式插入到 P(n-1) 的每个成员中。也就是说，如果 q 是 P(n-1) 中的某个分区，要在 P(n) 中构造分区，a 可以是附加到 q 或 的单例集a 可以附加到 q 中已有的集合之一。

代码如下：

#include <iostream> 
#include <vector>

using set = std::vector<int>;
using partition = std::vector<set>;
using partitions = std::vector<partition>;

template<typename T>
std::vector<T> append(const std::vector<T>& vec, const T& item) {
    auto output = vec;
    output.push_back(item);
    return output;
}

template<typename T>
std::vector<std::vector<T>> append_to_nth(const std::vector<std::vector<T>>& vec, 
        const T& item, int n) {
    auto output = vec;
    output[n] = append(output[n], item);
    return output;
}

partitions all_partitions(int n) {
    if (n <= 0) {
        return {};
    } else if (n == 1) {
        return { { { 1 } } };
    }
    auto partitions_of_n_minus_1 = all_partitions(n - 1);
    partitions partions_n;
    for (const auto& p : partitions_of_n_minus_1) {
        partions_n.push_back(append(p, set{ n }));
        for (size_t i = 0; i < p.size(); ++i) {
            partions_n.push_back(append_to_nth(p, n, i));
        }
    }
    return partions_n;
}

int main() {
    auto partitions = all_partitions(3);
    for (const auto& partition : partitions) {
        std::cout << "[ ";
        for (const auto& set : partition) {
            std::cout << "[ ";
            for (int item : set) {
                std::cout << item << " ";
            }
            std::cout << "]";
        }
        std::cout << " ]\n";
    }
}