c++ 关于输出所有n个数的所有子集的一个算法问题[副本]

sg24os4d  于 2023-04-08  发布在  其他
关注(0)|答案(1)|浏览(112)

此问题已在此处有答案

How to find all partitions of a set(8个回答)
5天前关闭。
现在我正在研究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],实际上是一样的,但我不知道怎么识别)
我认为我的想法是错误的使用这个功能。

8i9zcol2

8i9zcol21#

您要查找的是partitions,而不是组合或排列。
您可以通过注意到如果 P,来找到具有 n 个成员的集合 S 的分区。(n-1)是 S-a 的划分,其中 a 是任意成员,则可以构造 Pn)作为包含插入到 P 的每个成员中的 a 的集合也就是说,如果 qP 中的某个分区,(n-1),为了构建 Pn)中的分区,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";
    }
}

相关问题