python - 创建集合的分区，使得每个分区的长度相同

Question

根据标题，我正在尝试编写一个函数，该函数返回长度为 p 的集合的元组列表，其中每个集合都是集合 S 的一个分区。等分({0,1,2,3}, 2) --> [({0, 1}, {2, 3}), ({0, 2}, {1, 3}), ({0, 3}, {1, 2})]。然而，我很难让它在其他情况下正常工作，因为 itertools.products 不会连接集合的元组。任何有关如何编写/修复该函数的建议或帮助将不胜感激。以下是我迄今为止的尝试:

equipartitions_cache_d = {}
def equipartitions(S,p):
    global equipartitions_cache_d
    if len(S) % p != 0:
        raise ValueError("Set must be of a length which is a multiple of p")
    if equipartitions_cache_d.get((frozenset(S),p)):
        return equipartitions_cache_d[(frozenset(S),p)]
    else:
        if len(S) == p:
            equipartitions_cache_d[(frozenset(S),p)] = [S]
        else:
            gens = []
            combs = [set(s) for s in itertools.combinations(S, p)]
            for c in combs:
                gens += [s for s in itertools.product([c], equipartitions(S-c,p))]
            uniqgens = []
            for g in gens:
                if not any([all([x in q for x in g]) for q in uniqgens]):
                    uniqgens.append(g)
            equipartitions_cache_d[(frozenset(S),p)] = uniqgens
        return equipartitions_cache_d[(frozenset(S),p)]

Answer 1

效率不高(对于较大的输入(例如 equipart(set(range(100), 5)))需要花费大量时间)，但有效。

def equipart(s, p):
    import itertools
    if len(s) % p != 0:
        raise ValueError("Set must be of a length which is a multiple of p")
    com = map(set, set(itertools.combinations(s, p)))
    res = list()
    for ia, a in enumerate(com):
        for il, l in enumerate(res):
            if not any([(a&x) for x in l]):
                res[il] = res[il] + (a, )
                break
        else:
            res.append((a, ))
    res = filter(lambda x: len(x) == len(s) / p, res)
    return res

输出:

In [94]: equipart({1,2,3,4,5,6}, 3)
Out[94]: 
[({3, 4, 6}, {1, 2, 5}),
 ({2, 3, 5}, {1, 4, 6}),
 ({1, 2, 6}, {3, 4, 5}),
 ({2, 3, 4}, {1, 5, 6}),
 ({4, 5, 6}, {1, 2, 3}),
 ({2, 3, 6}, {1, 4, 5}),
 ({1, 3, 6}, {2, 4, 5}),
 ({2, 4, 6}, {1, 3, 5}),
 ({2, 5, 6}, {1, 3, 4}),
 ({3, 5, 6}, {1, 2, 4})]

In [95]: equipart({1,2,3,4,5,6}, 2)
Out[95]: [({1, 2}, {5, 6}, {3, 4}), ({1, 3}, {4, 6}, {2, 5}), ({1, 6}, {2, 4}, {3, 5})]

编辑:

在多个元组中使用单个子集的新方法。

def equipart(s, p):
    import itertools
    if len(s) % p != 0:
        raise ValueError("Set must be of a length which is a multiple of p")
    com = map(set, set(itertools.combinations(s, p)))
    res = [x for x in itertools.combinations(com, len(s)/p) if set().union(*x) == s]
    return res

输出:

In [37]: equipart({1,2,3,4,5,6}, 3)
Out[37]: 
[({3, 4, 6}, {1, 2, 5}),
 ({2, 3, 5}, {1, 4, 6}),
 ({1, 2, 6}, {3, 4, 5}),
 ({2, 3, 4}, {1, 5, 6}),
 ({4, 5, 6}, {1, 2, 3}),
 ({2, 3, 6}, {1, 4, 5}),
 ({1, 3, 6}, {2, 4, 5}),
 ({2, 4, 6}, {1, 3, 5}),
 ({2, 5, 6}, {1, 3, 4}),
 ({3, 5, 6}, {1, 2, 4})]

In [38]: equipart({1,2,3,4,5,6}, 2)
Out[38]: 
[({1, 2}, {5, 6}, {3, 4}),
 ({1, 2}, {4, 6}, {3, 5}),
 ({1, 2}, {4, 5}, {3, 6}),
 ({5, 6}, {1, 3}, {2, 4}),
 ({5, 6}, {1, 4}, {2, 3}),
 ({1, 3}, {4, 6}, {2, 5}),
 ({1, 3}, {4, 5}, {2, 6}),
 ({4, 6}, {1, 5}, {2, 3}),
 ({4, 5}, {1, 6}, {2, 3}),
 ({1, 4}, {2, 6}, {3, 5}),
 ({1, 4}, {3, 6}, {2, 5}),
 ({1, 5}, {2, 6}, {3, 4}),
 ({1, 5}, {3, 6}, {2, 4}),
 ({1, 6}, {2, 5}, {3, 4}),
 ({1, 6}, {2, 4}, {3, 5})]