如何在python中实现一个简单的基于greedy multiset的算法

Question

我想实现以下算法.对于n和k,考虑所有重复排序的组合,我们k从{0,..n-1}重复中选择数字.例如,如果n=5和k =3我们有:

[(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,0,4),(0,1,1),( 0,1,2),(0,1,3),(0,1,4),(0,2,2),(0,2,3),(0,2,4),(0, 3,3),(0,3,4),(0,4,4),(1,1,1),(1,1,2),(1,1,3),(1,1, 4),(1,2,2),(1,2,3),(1,2,4),(1,3,3),(1,3,4),(1,4,4) ,(2,2,2),(2,2,3),(2,2,4),(2,3,3),(2,3,4),(2,4,4),( 3,3,3),(3,3,4),(3,4,4),(4,4,4)]

从现在开始,我将把每个组合视为一个多重组合.我想贪婪地浏览这些多字节并对列表进行分区.分区具有属性,其中所有多个集合的交集大小必须至少为k-1.所以在这种情况下我们有:

(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)

然后

 (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)

然后

(0, 2, 2), (0, 2, 3), (0, 2, 4)

然后

(0, 3,  3), (0, 3, 4)

然后

(0, 4, 4)

等等.

在python中,您可以按如下方式迭代组合:

import itertools
for multiset in itertools.combinations_with_replacement(range(5),3):
    #Greedy algo

我该如何创建这些分区？

我遇到的一个问题是如何计算多集合交集的大小.多集的交集(2,1,2)和(3,2,2)具有大小2中,例如.

---

这是完整的答案n=4, k=4.

(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)

Answer 1

创建分区的一种方法是迭代迭代器，然后将每个多重集 * 与前一个进行比较。我测试了 4 种方法**来比较多重集，我发现最快的方法是测试成员资格，即in先前多重集的迭代器，一旦成员资格测试失败，该迭代器就会被消耗并短路。如果多重集中和前一个多重集中的相等项目数等于多重集的长度减 1，则满足对它们进行分组的标准。list然后构建 s的结果输出生成器，其中append满足前一个条件的项目并开始包含其他条件的list新项目，一次一个组以最小化内存使用量：listtupleyield

import itertools

def f(n,k):
    prev, group = None, []
    for multiset in itertools.combinations_with_replacement(range(n),k):
        if prev:
            it = iter(prev)
            for idx, item in enumerate(multiset):
                if item not in it:
                    break
            if idx == len(multiset) - 1:
                group.append(multiset)
                continue
        if group:
            yield group
        group = [multiset]
        prev = multiset
    yield group

测试用例

输入：

for item in f(4,4):
    print(item)

输出：

[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)]
[(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)]
[(0, 0, 2, 2), (0, 0, 2, 3)]
[(0, 0, 3, 3)]
[(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)]
[(0, 1, 2, 2), (0, 1, 2, 3)]
[(0, 1, 3, 3)]
[(0, 2, 2, 2), (0, 2, 2, 3)]
[(0, 2, 3, 3), (0, 3, 3, 3)]
[(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)]
[(1, 1, 2, 2), (1, 1, 2, 3)]
[(1, 1, 3, 3)]
[(1, 2, 2, 2), (1, 2, 2, 3)]
[(1, 2, 3, 3), (1, 3, 3, 3)]
[(2, 2, 2, 2), (2, 2, 2, 3)]
[(2, 2, 3, 3), (2, 3, 3, 3)]
[(3, 3, 3, 3)]

输入：

for item in f(5,3):
    print(item)

输出：

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)]
[(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)]
[(0, 2, 2), (0, 2, 3), (0, 2, 4)]
[(0, 3, 3), (0, 3, 4)]
[(0, 4, 4)]
[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)]
[(1, 2, 2), (1, 2, 3), (1, 2, 4)]
[(1, 3, 3), (1, 3, 4)]
[(1, 4, 4)]
[(2, 2, 2), (2, 2, 3), (2, 2, 4)]
[(2, 3, 3), (2, 3, 4)]
[(2, 4, 4)]
[(3, 3, 3), (3, 3, 4)]
[(3, 4, 4), (4, 4, 4)]

* 我将它们称为多重集以匹配您的术语，但它们实际上是tuples （有序且不可变的数据结构）；使用collections.Counter对象（例如Counter((0, 0, 0, 1)) returns ）Counter({0: 3, 1: 1})和递减就像真正的多重集方法，但我发现这会更慢，因为使用顺序实际上很有用。

** 其他较慢的函数提供与我测试的相同的输出：

def f2(n,k):
    prev, group = None, []
    for multiset in itertools.combinations_with_replacement(range(n),k):
        if prev:
            if sum(item1 == item2 for item1, item2 in zip(prev,multiset)) == len(multiset) - 1:
                group.append(multiset)
                continue
        if group:
            yield group
        group = [multiset]
        prev = multiset
    yield group

def f3(n,k):
    prev, group = None, []
    for multiset in itertools.combinations_with_replacement(range(n),k):
        if prev:
            lst = list(prev)
            for item in multiset:
                if item in lst:
                    lst.remove(item)
                else:
                    break
            if len(multiset) - len(lst) == len(multiset) - 1:
                group.append(multiset)
                continue
        if group:
            yield group
        group = [multiset]
        prev = multiset
    yield group

import collections
def f4(n,k):
    prev, group = None, []
    for multiset in itertools.combinations_with_replacement(range(n),k):
        if prev:
            if sum((collections.Counter(prev) - collections.Counter(multiset)).values()) == 1:
                group.append(multiset)
                continue
        if group:
            yield group
        group = [multiset]
        prev = multiset
    yield group

时间示例：

from timeit import timeit
list(f(11,10)) == list(f2(11,10)) == list(f3(11,10)) == list(f4(11,10))
# True
timeit(lambda: list(f(11,10)), number = 10)
# 4.19157001003623
timeit(lambda: list(f2(11,10)), number = 10)
# 7.32002648897469
timeit(lambda: list(f3(11,10)), number = 10)
# 6.236868146806955
timeit(lambda: list(f4(11,10)), number = 10)
# 47.20136355608702

n请注意，对于较大的和值，所有方法都会变慢k，因为生成了大量组合。