如何查找多重集（允许重复的集合）的所有分区

Question

给定一个可能包含重复项的数字集合，找到它的所有分区。（划分集合的所有可能方式。）

\n\n

例如，多重集 {1, 1, 2} 有 4 个分区：

\n\n

分区 1 = { {1}, {1}, {2} }\n 分区 2 = { {1}, {1, 2} }\n 分区 3 = { {1, 1}, {2} }\n分区 4 = { {1, 1, 2} }

\n\n

这是一个类似的问题如何查找集合的所有分区，但在该问题中，所有数字都是不同的。

\n\n

集合分区的定义： https ://en.wikipedia.org/wiki/Partition_of_a_set

\n\n

多重集\xef\xbc\x9a 的定义https://en.wikipedia.org/wiki/Multiset

\n\n

用任何通用编程语言编写的带有一些解释的解决方案将不胜感激。

\n\n

---

\n\n

更新\xef\xbc\x9a

\n\n

看来很多人都搞不清楚这个问题到底想问什么。它不是给定集合的所有可能的子集。相反，它要求您找出划分给定数字集合的所有不同方法。

\n

Answer 1

这是一个分区集问题。

原始集合中的元素数量始终等于每个分区中的元素数量之和。

可以使用回溯和递归来解决。这个 C++ 程序可能有用。

void solve (set<vector<vector<int>>>& solution, vector<int> inputSet, 
vector<vector<int>>& partitions, vector<int> partition, int n, int i) {
    int numberOfElements = 0;
    for (int i=0; i<partitions.size(); i++) {
        numberOfElements += partitions[i].size();
    }
    if (numberOfElements == n) {
        vector<vector<int>> newPartitions = partitions;
        for (int i=0; i<newPartitions.size(); i++) {
            sort (newPartitions[i].begin(), newPartitions[i].end());
        }
        sort(newPartitions.begin(), newPartitions.end());
        solution.insert(newPartitions);
        return;  
    }
    for (int j=i; j<n; j++) {
        partition.push_back(inputSet[j]);
        partitions.push_back(partition);
        vector<int> partitionNew;
        solve(solution, inputSet, partitions, partitionNew, n, j+1);
        partitions.pop_back();
    }
}

void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) {
    if (i == n) {
        vector<int> partition;
        vector<vector<int>> partitions;
        solve(solution, inputSet, partitions, partition, inputSet.size(), 0);
        return;
    }
    for (int j=i; j<=n; j++) {
        swap(inputSet[i], inputSet[j]);
        permute(solution, inputSet, i+1, n);
        swap(inputSet[i], inputSet[j]);
    }
}

这是工作示例：生成所有分区

编辑：我误读了这个问题。我已经更新了答案。它现在生成所有可能的分区。