在 Python 中的某些约束下生成集合的最大子集
Generating Maximal Subsets of a Set Under Some Constraints in Python
我有一组属性 A= {a1, a2, ...an} 和一组簇 C = {c1, c2, ... ck} 我有一组对应关系 COR 是 A x C 和 |COR|<< A x C。这是一组通信示例
COR = {(a1, c1), (a1, c2), (a2, c1), (a3, c3), (a4, c4)}
现在，我想生成 COR 的所有子集，使得子集中的每一对代表从集合 A 到集合 C 的单射函数。让我们将每个这样的子集称为一个映射，然后来自上述集合 COR 的有效映射将是
m1 = {(a1, c1), (a3, c3), (a4, c4)} 和 m2 = {(a1, c2), (a2, c1), (a3, c3), (a4, c4)}
m1 在这里很有趣，因为将 COR 中的任何剩余元素添加到 m1 要么违反函数的定义，要么违反成为单射函数的条件。例如，如果我们将 (a1,c2) 添加到 m1，m1 将不再是一个函数，如果我们将 (a2,c1) 添加到 m1，它将停止成为单射函数。因此，我对可用于生成所有此类映射的一些代码片段或算法感兴趣。这是我到目前为止在 python 中尝试过的
导入集合
导入 itertools
corr = set({('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')})
clusters = [c[1] for c in corr]
attribs = [a[0] for a in corr]
rep_clusters = [item for item, count in collections.Counter(clusters).items() if count>1]
rep_attribs = [item for item, count in collections.Counter(attribs).items() if count>1]
conflicting_sets = []
for c in rep_clusters:
conflicting_sets.append([p for p in corr if p[1] == c])
for a in rep_attribs:
conflicting_sets.append([p for p in corr if p[0] == a])
non_conflicting = corr
for s in conflicting_sets:
non_conflicting = non_conflicting - set(s)
m = set()
for p in itertools.product(*conflicting_sets):
print(p, 'product', len(p))
p_attribs = set([k[0] for k in p])
p_clusters = set([k[1] for k in p])
print(len(p_attribs), len(p_clusters))
if len(p) == len(p_attribs) and len(p) == len(p_clusters):
m.add(frozenset(set(p).union(non_conflicting)))
print(m)
正如预期的那样，代码会生成 m2 但不会生成 m1，因为 m1 不会从 itertools.product 生成。任何人都可以指导我吗？我还想要一些关于性能的指导，因为实际的集会比这里使用的 COR 集大，并且可能包含更多冲突集。
您的要求的更简单定义是：
- 您有一组独特的元组。
- 您想生成以下所有子集：
- 元组的所有第一个元素都是唯一的（以确保功能）；
- 并且所有的第二个元素都是唯一的（以确保单射性）。
- 你的标题表明你只需要最大子集，也就是说，在不破坏其他要求的情况下，不可能从原始集合中添加任何额外的元素。
我还假设任何 a<x> 或 c<y> 都是唯一的。
这是一个解决方案：
def get_maximal_subsets(corr):
def is_injective_function(f):
if not f:
return False
f_domain, f_range = zip(*f)
return len(set(f_domain)) - len(f_domain) + len(set(f_range)) - len(f_range) == 0
def generate_from(f):
if is_injective_function(f):
for r in corr - f:
if is_injective_function(f | {r}):
break
else:
yield f
else:
for c in f:
yield from generate_from(f - {c})
return list(map(set, set(map(frozenset, generate_from(corr)))))
# representing a's and c's as strings, as their actual value doesn't matter, as long as they are unique
print(get_maximal_subsets(corr={('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')}))
测试 is_injective_function 检查提供的集合 f 是否表示有效的单射函数，方法是从函数的域和范围中获取所有值，并检查两者是否仅包含唯一值。
生成器接受一个 f，如果它表示一个单射有效函数，它会检查 none 个已从原始 corr 中删除的元素reach f 可以加回去，同时仍然代表一个内射有效函数。如果是这种情况，它会产生 f 作为有效结果。
如果 f 不是一个有效的单射函数，它将尝试依次删除 f 中的每个元素，并从每个子集中生成任何单射有效函数.
最后，整个函数从生成的生成器中删除重复项，returns它作为唯一集的列表。
输出：
[{('a1', 'c1'), ('a3', 'c3'), ('a4', 'c4')}, {('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4'), ('a1', 'c2')}]
请注意，有几种方法可以对 non-hashable 值的列表进行重复数据删除，但这种方法会将列表中的所有集合变成 frozenset 以使其可哈希，然后将列表变成设置删除重复项，然后再次将内容变成集合，returns 结果作为列表。
您可以通过跟踪已尝试删除的子集来防止最后删除重复项，这可能会根据您的实际数据集执行得更好：
def get_maximal_subsets(corr):
def is_injective_function(f):
if not f:
return False
f_domain, f_range = zip(*f)
return len(set(f_domain)) - len(f_domain) + len(set(f_range)) - len(f_range) == 0
previously_removed = []
def generate_from(f, removed: set = None):
previously_removed.append(removed)
if removed is None:
removed = set()
if is_injective_function(f):
for r in removed:
if is_injective_function(f | {r}):
break
else:
yield f
else:
for c in f:
if removed | {c} not in previously_removed:
yield from generate_from(f - {c}, removed | {c})
return list(generate_from(corr))
这可能是一个通常性能更好的解决方案，但我更喜欢第一个的干净算法，以便更好地解释。
在评论询问它是否扩展到 100 个元素且有 ~15 个冲突（解决它需要 运行 很多分钟）之后，我对上述解决方案的缓慢感到恼火，所以这里有一个更快的对于 100 个元素有 15 个冲突 运行s 在 1 秒以下的解决方案，尽管执行时间仍然呈指数增长，因此它有其局限性）：
def injective_function_conflicts(f):
if not f:
return {}
conflicts = defaultdict(set)
# loop over the product f x f
for x in f:
for y in f:
# for each x and y that have a conflict in any position
if x != y and any(a == b for a, b in zip(x, y)):
# add x to y's entry and y to x's entry
conflicts[y].add(x)
conflicts[x].add(y)
return conflicts
def get_maximal_partial_subsets(conflicts, off_limits: set = None):
if off_limits is None:
off_limits = set()
while True and conflicts:
# pop elements from the conflicts, using them now, or discarding them if off-limits
k, vs = conflicts.popitem()
if k not in off_limits:
break
else:
# nothing left in conflicts that's not off-limits
yield set()
return
# generate each possible result from the rest of the conflicts, adding the conflicts vs for k to off_limits
for sub_result in get_maximal_partial_subsets(dict(conflicts), off_limits | vs):
# these results can have k added to them, as all the conflicts with k were off-limits
yield sub_result | {k}
# also generated each possible result from the rest of the conflicts without k's conflicts
for sub_result in get_maximal_partial_subsets(conflicts, off_limits):
# but only yield as a result if adding k itself to it would actually cause a conflict, avoiding duplicates
if sub_result and injective_function_conflicts(sub_result | {k}):
yield sub_result
def efficient_get_maximal_subsets(corr):
conflicts = injective_function_conflicts(corr)
final_result = list((corr - set(conflicts.keys())) | result
for result in get_maximal_partial_subsets(dict(conflicts)))
print(f'size of result and conflict: {len(final_result)}, {len(conflicts)}')
return final_result
print(efficient_get_maximal_subsets(corr={('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')}))
我有一组属性 A= {a1, a2, ...an} 和一组簇 C = {c1, c2, ... ck} 我有一组对应关系 COR 是 A x C 和 |COR|<< A x C。这是一组通信示例
COR = {(a1, c1), (a1, c2), (a2, c1), (a3, c3), (a4, c4)}
现在，我想生成 COR 的所有子集，使得子集中的每一对代表从集合 A 到集合 C 的单射函数。让我们将每个这样的子集称为一个映射，然后来自上述集合 COR 的有效映射将是
m1 = {(a1, c1), (a3, c3), (a4, c4)} 和 m2 = {(a1, c2), (a2, c1), (a3, c3), (a4, c4)}
m1 在这里很有趣，因为将 COR 中的任何剩余元素添加到 m1 要么违反函数的定义，要么违反成为单射函数的条件。例如，如果我们将 (a1,c2) 添加到 m1，m1 将不再是一个函数，如果我们将 (a2,c1) 添加到 m1，它将停止成为单射函数。因此，我对可用于生成所有此类映射的一些代码片段或算法感兴趣。这是我到目前为止在 python 中尝试过的
导入集合
导入 itertools
corr = set({('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')})
clusters = [c[1] for c in corr]
attribs = [a[0] for a in corr]
rep_clusters = [item for item, count in collections.Counter(clusters).items() if count>1]
rep_attribs = [item for item, count in collections.Counter(attribs).items() if count>1]
conflicting_sets = []
for c in rep_clusters:
conflicting_sets.append([p for p in corr if p[1] == c])
for a in rep_attribs:
conflicting_sets.append([p for p in corr if p[0] == a])
non_conflicting = corr
for s in conflicting_sets:
non_conflicting = non_conflicting - set(s)
m = set()
for p in itertools.product(*conflicting_sets):
print(p, 'product', len(p))
p_attribs = set([k[0] for k in p])
p_clusters = set([k[1] for k in p])
print(len(p_attribs), len(p_clusters))
if len(p) == len(p_attribs) and len(p) == len(p_clusters):
m.add(frozenset(set(p).union(non_conflicting)))
print(m)
正如预期的那样，代码会生成 m2 但不会生成 m1，因为 m1 不会从 itertools.product 生成。任何人都可以指导我吗？我还想要一些关于性能的指导，因为实际的集会比这里使用的 COR 集大，并且可能包含更多冲突集。
您的要求的更简单定义是：
- 您有一组独特的元组。
- 您想生成以下所有子集：
- 元组的所有第一个元素都是唯一的（以确保功能）；
- 并且所有的第二个元素都是唯一的（以确保单射性）。
- 你的标题表明你只需要最大子集，也就是说，在不破坏其他要求的情况下，不可能从原始集合中添加任何额外的元素。
我还假设任何 a<x> 或 c<y> 都是唯一的。
这是一个解决方案：
def get_maximal_subsets(corr):
def is_injective_function(f):
if not f:
return False
f_domain, f_range = zip(*f)
return len(set(f_domain)) - len(f_domain) + len(set(f_range)) - len(f_range) == 0
def generate_from(f):
if is_injective_function(f):
for r in corr - f:
if is_injective_function(f | {r}):
break
else:
yield f
else:
for c in f:
yield from generate_from(f - {c})
return list(map(set, set(map(frozenset, generate_from(corr)))))
# representing a's and c's as strings, as their actual value doesn't matter, as long as they are unique
print(get_maximal_subsets(corr={('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')}))
测试 is_injective_function 检查提供的集合 f 是否表示有效的单射函数，方法是从函数的域和范围中获取所有值，并检查两者是否仅包含唯一值。
生成器接受一个 f，如果它表示一个单射有效函数，它会检查 none 个已从原始 corr 中删除的元素reach f 可以加回去，同时仍然代表一个内射有效函数。如果是这种情况，它会产生 f 作为有效结果。
如果 f 不是一个有效的单射函数，它将尝试依次删除 f 中的每个元素，并从每个子集中生成任何单射有效函数.
最后，整个函数从生成的生成器中删除重复项，returns它作为唯一集的列表。
输出：
[{('a1', 'c1'), ('a3', 'c3'), ('a4', 'c4')}, {('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4'), ('a1', 'c2')}]
请注意，有几种方法可以对 non-hashable 值的列表进行重复数据删除，但这种方法会将列表中的所有集合变成 frozenset 以使其可哈希，然后将列表变成设置删除重复项，然后再次将内容变成集合，returns 结果作为列表。
您可以通过跟踪已尝试删除的子集来防止最后删除重复项，这可能会根据您的实际数据集执行得更好：
def get_maximal_subsets(corr):
def is_injective_function(f):
if not f:
return False
f_domain, f_range = zip(*f)
return len(set(f_domain)) - len(f_domain) + len(set(f_range)) - len(f_range) == 0
previously_removed = []
def generate_from(f, removed: set = None):
previously_removed.append(removed)
if removed is None:
removed = set()
if is_injective_function(f):
for r in removed:
if is_injective_function(f | {r}):
break
else:
yield f
else:
for c in f:
if removed | {c} not in previously_removed:
yield from generate_from(f - {c}, removed | {c})
return list(generate_from(corr))
这可能是一个通常性能更好的解决方案，但我更喜欢第一个的干净算法，以便更好地解释。
在评论询问它是否扩展到 100 个元素且有 ~15 个冲突（解决它需要 运行 很多分钟）之后，我对上述解决方案的缓慢感到恼火，所以这里有一个更快的对于 100 个元素有 15 个冲突 运行s 在 1 秒以下的解决方案，尽管执行时间仍然呈指数增长，因此它有其局限性）：
def injective_function_conflicts(f):
if not f:
return {}
conflicts = defaultdict(set)
# loop over the product f x f
for x in f:
for y in f:
# for each x and y that have a conflict in any position
if x != y and any(a == b for a, b in zip(x, y)):
# add x to y's entry and y to x's entry
conflicts[y].add(x)
conflicts[x].add(y)
return conflicts
def get_maximal_partial_subsets(conflicts, off_limits: set = None):
if off_limits is None:
off_limits = set()
while True and conflicts:
# pop elements from the conflicts, using them now, or discarding them if off-limits
k, vs = conflicts.popitem()
if k not in off_limits:
break
else:
# nothing left in conflicts that's not off-limits
yield set()
return
# generate each possible result from the rest of the conflicts, adding the conflicts vs for k to off_limits
for sub_result in get_maximal_partial_subsets(dict(conflicts), off_limits | vs):
# these results can have k added to them, as all the conflicts with k were off-limits
yield sub_result | {k}
# also generated each possible result from the rest of the conflicts without k's conflicts
for sub_result in get_maximal_partial_subsets(conflicts, off_limits):
# but only yield as a result if adding k itself to it would actually cause a conflict, avoiding duplicates
if sub_result and injective_function_conflicts(sub_result | {k}):
yield sub_result
def efficient_get_maximal_subsets(corr):
conflicts = injective_function_conflicts(corr)
final_result = list((corr - set(conflicts.keys())) | result
for result in get_maximal_partial_subsets(dict(conflicts)))
print(f'size of result and conflict: {len(final_result)}, {len(conflicts)}')
return final_result
print(efficient_get_maximal_subsets(corr={('a1', 'c1'), ('a1', 'c2'), ('a2', 'c1'), ('a3', 'c3'), ('a4', 'c4')}))