我有以下问题,最初我有3个集合。
A [1,2,3],B [2,3,4,5] and C [2,5,6,7]
接下来,我考虑两两组合的交点 以及所有组合的交点。
AB [2,3],
AC [2],
BC [2,5] and
ABC [2] (Full intersection)
现在我想要的是对我的集合进行一个新的重新排序,条件如下:1.保留每个集合的cardinality.2.保留所有可能的交集的cardinality。
例如,我应该得到
A [3,4,7],
B [1,3,7,5] and
C [2,6,5,7]
注意到A和B的新交点(现在是[3,7])和之前的交点一样有2个元素,类比交点AC ,BC和全交点ABC,当然,A,B,C的卡数继续分别是3,4,4。最后我需要尽可能多地进行这种重组的过程,我理解这取决于集合的cardinality和集合的总数。
你可以直接生成原元素集的所有可能的排列组合,并将它们作为原元素到新配置的 "映射"。所以,比如说 2345671
将每个数字映射到下一个数字,并环绕起来;这就创建了集合。
A = {2, 3, 4} # from {1, 2, 3}
B = {3, 4, 5, 6} # from {2, 3, 4, 5}
C = {3, 6, 7, 1} # from {2, 5, 6, 7}
这是很直接的,使用 itertools
:
from itertools import permutations
def all_configurations(*sets):
elements = list(set.union(*sets))
for perm in permutations(elements):
map = {old: new for old, new in zip(elements, perm)}
new_sets = [{map[k] for k in old_set} for old_set in sets]
yield new_sets
A = {1, 2, 3}
B = {2, 3, 4, 5}
C = {2, 5, 6, 7}
confs = all_configurations(A, B, C)
for conf in confs:
print(conf)
# Or: Ax, Bx, Cx = conf
注意我是如何使用的 yield
语句,这将一次生成一个新的排列组合,而不是一次全部生成,所以你可以在不占用内存的情况下对大量元素使用这个函数。另外,这个函数也可以用于任何数量的输入集。
当然,这肯定会产生一些重复的东西(例如,在你的例子中,将6映射到7和将7映射到6并不会改变任何东西),但它也应该肯定会产生每一个有效的选项。一些样本输出。
[{2, 4, 6}, {3, 4, 5, 6}, {1, 3, 6, 7}]
[{4, 5, 7}, {1, 3, 4, 7}, {2, 3, 6, 7}]
[{3, 5, 6}, {1, 3, 5, 7}, {2, 3, 4, 7}]
[{1, 6, 7}, {1, 2, 4, 7}, {2, 3, 5, 7}]
EDIT: 为了得到固定数量的非重复安排,可以将原来的代码改为返回一个。tuple
的 frozensets
而不是一个集合列表,这样一来,整个东西就可以哈希,所以你只能得到唯一性。然后,你可以将东西添加到输出集中,直到它达到你想要的cardinality。
from itertools import permutations
def all_configurations(*sets):
elements = list(set.union(*sets))
for perm in permutations(elements):
map = {old: new for old, new in zip(elements, perm)}
new_sets = tuple(frozenset(map[k] for k in old_set) for old_set in sets)
yield new_sets
def n_configurations(n, *sets):
output = set()
confs = all_configurations(*sets)
for conf in confs:
output.add(conf)
if len(output) >= n:
break
return output
A = {1, 2, 3}
B = {2, 3, 4, 5}
C = {2, 5, 6, 7}
confs = n_configurations(10, A, B, C)
for a, b, c in confs:
print(a, b, c)
这将产生以下10个配置
(frozenset([1, 2, 3]), frozenset([2, 3, 5, 6]), frozenset([2, 4, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 6]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 6, 7]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 6]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 5]), frozenset([2, 4, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 5, 6]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 7]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 5]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 7]), frozenset([2, 4, 5, 6]))
(frozenset([1, 2, 3]), frozenset([2, 3, 5, 7]), frozenset([2, 4, 6, 7]))
这能让你入门吗?
import random
import itertools
def same_intersect_len(x, y, z):
return (len(x & y) == len(a & b) and
len(x & z) == len(a & c) and
len(z & y) == len(b & c) and
len(x & y & z) == len(a & b & c))
a = set(random.sample(range(0, 10), 1))
b = set(random.sample(range(0, 10), 2))
c = set(random.sample(range(0, 10), 3))
elements = list(a) + list(b) + list(c)
ps = set(itertools.permutations(elements))
new_a = list()
new_b = list()
new_c = list()
for p in ps:
candidate_a = {p[len(a) - 1]} - a
candidate_b = set(p[len(a):len(a) + len(b) - 1]) - b
candidate_c = set(p[len(a) + len(b):len(a) + len(b) + len(c) - 1]) - c
if same_intersect_len(
candidate_a,
candidate_b,
candidate_c):
new_a.append(candidate_a)
new_b.append(candidate_b)
new_c.append(candidate_c)