生成多重集的幂集

Question

假设我有一个多重集

{a,a,a,b,c}

我可以从中做出以下选择：

{}
{a}
{a,a}
{a,a,a}
{a,a,a,b}
{a,a,a,b,c}
{a,a,a,c}
{a,a,b}
{a,a,b,c}
{a,a,c}
{a,b}
{a,b,c}
{a,c}
{b}
{b,c}
{c}

注意选择数等于 16。多重集的幂集的基数 card(P(M)) 在 OEIS 上定义为

card(P(M)) = prod(mult(x) + 1) for all x in M

其中 mult(x) 是 M 中 x 的重数，而 prod 是项的乘积。因此，对于我们的示例，这将等于 4 x 2 x 2 = 16.

比方说，这些元素的多重性非常高：

m(a) = 21
m(b) = 36
m(c) = 44

然后

card(P(M)) = 22 * 37 * 45 = 36630.

但如果我们将所有这些元素视为不同的 - 作为一个集合 - 幂集的基数将为

card(P(S)) = 2^(21+36+44) = 2535301200456458802993406410752.

这个问题的“标准”解决方案建议只计算所有元素都被视为不同的集合的幂集，然后修剪结果以删除重复项。这是一个 O(2^n) 复杂的解决方案。

是否存在生成复杂度为 card(P(M)) 的多重集的幂集的通用算法？

Answer 1

这将为您提供 lst 和 tuples 的所有组合。希望这能回答您的问题。

from itertools import combinations
lst = ['a', 'a', 'a', 'b', 'c']

combs = set()

for i in range(len(lst)+1):
    els = [tuple(x) for x in combinations(lst, i)]
    for item in tuple(els):
       combs.add(item)

print(combs)

Answer 2

`powerset` 配方 `itertools`

您要问的通常称为 powerset，可作为 itertools 配方使用，也可作为模块 more_itertools 中的函数使用。请参阅文档：

multiset = ['a', 'a', 'a', 'b', 'c']

#
# USING ITERTOOLS
#
import itertools

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

print(list(powerset(multiset)))
# [(), ('a',), ('a',), ('a',), ('b',), ('c',), ('a', 'a'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'c'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'c'), ('a', 'b', 'c'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'a', 'b', 'c')]

#
# USING MORE_ITERTOOLS
#
import more_itertools

print(list(more_itertools.powerset(multiset)))
# [(), ('a',), ('a',), ('a',), ('b',), ('c',), ('a', 'a'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'c'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'c'), ('a', 'b', 'c'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'b', 'c'), ('a', 'a', 'a', 'b', 'c')]

`collections.Counter` 对象的幂集

在Python中，多重集通常用collections.Counter而不是list表示。 class collections.Counter 是 dict 的子 class；它实现了将元素映射到计数的字典，以及一些有用的方法，例如通过计算序列中出现的次数来构建 Counter。

取 Counter 的幂集是 Whosebug 上另一个问题的主题：

虽然我不知道在标准模块中已经实现了这样做的方法，但该问题的答案提供了一个使用 itertools:

的解决方案

import collections
import itertools

multiset = collections.Counter(['a', 'a', 'a', 'b', 'c'])
# Counter({'a': 3, 'b': 1, 'c': 1})

def powerset(multiset):
    range_items = [[(x, z) for z in range(y + 1)] for x,y in multiset.items()]
    products = itertools.product(*range_items)
    return [{k: v for k, v in pairs if v > 0} for pairs in products]

print(powerset(multiset))
# [{}, {'c': 1}, {'b': 1}, {'b': 1, 'c': 1}, {'a': 1}, {'a': 1, 'c': 1}, {'a': 1, 'b': 1}, {'a': 1, 'b': 1, 'c': 1}, {'a': 2}, {'a': 2, 'c': 1}, {'a': 2, 'b': 1}, {'a': 2, 'b': 1, 'c': 1}, {'a': 3}, {'a': 3, 'c': 1}, {'a': 3, 'b': 1}, {'a': 3, 'b': 1, 'c': 1}]

Answer 3

我认为最好的方式是从空集开始，然后为每个角色选择是将其添加到当前现有集还是不添加。由于每一步有 2 个选择，因此幂集中的元素总数为 2^n。可以通过此 Java 代码来实现：

    public List<List<Integer>> subsets(int[] nums) {
    
    // list variable contains all of the subsets

    List<List<Integer>> list = new ArrayList<>();
    // add the empty set to start with
    list.add(new ArrayList<Integer>());
    
    for (int i = 0; i < nums.length; i++) {
        //find current list size
        int length = list.size();
        
        // Loop through and add the current element to all existing 
        subsets
        //Represents making the choice of adding the element
        for (int j = 0; j < length; j++) {
            // making a copy of current subset list
            ArrayList<Integer> temp = new ArrayList<>(list.get(j));
            temp.add(nums[i]);
            list.add(temp);
        }
    }
    
    return list;
}

生成多重集的幂集

Generating the powerset of a multiset

algorithm

pseudocode

combinatorics

multiset

`powerset` 配方 `itertools`

`collections.Counter` 对象的幂集

生成多重集的幂集

Generating the powerset of a multiset

algorithm

pseudocode

combinatorics

multiset

powerset 配方 itertools

collections.Counter 对象的幂集

`powerset` 配方 `itertools`

`collections.Counter` 对象的幂集