如何查找多集(允许重复的集)的所有分区

嘿,我有一个python解决方案:

from sympy.utilities.iterables import multiset_partitions
from pi in multiset_partitions([1,1,3]):
    print pi

查看代码,您可以在Knuth的AOCP中找到算法,就在那里: http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf

算法M,第39/40页。

干杯:)

这是一个 问题

回溯 和 递归

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]);
    }
}

以下是工作示例: Generate all Partitions