使用python从允许列表中查找阻止列表

Question

我们将向该函数传递一个策略列表。策略列表包含实体列表。我们需要返回不能相互通信的实体列表。 例如。策略 1 = [['A'], ['B', 'C'], ['D']] 此策略 1 表示允许其余所有的 B-C 流量被拒绝。我们需要返回无法相互通信的实体列表。 block_list = [('A', 'C', 'D'), ('A', 'B', 'D')]

类似地，policy2 = [['A', 'B'], ['B', 'C'], ['D']] 其中 B 可以直接与 A,C 通信，但 A 和 C 不能相互通信且无法通讯 D。D 彼此无法通讯（A、B、C）。 block_list = [('A', 'C', 'D'), ('B', 'D')]

同样，policy3 = [['A'], ['B', 'C'], ['D', 'E']]; A 无法与任何其他实体通信。 B和C可以互相通信，但不能与其他人（A，D，E）通信， block_list = [('A', 'C', 'D'), ('A', 'B', 'D'), ('A', 'C', 'E'), ('A', ‘B’、‘E’)]

与policy4类似 = [['A'], ['B', 'C'], ['D', 'E'], ['F'], ['G']] ; block_list =[('A', 'B', 'E', 'F', 'G'), ('A', 'C', 'D', 'F', 'G'), ('A ', 'C', 'E', 'F', 'G'), ('A', 'B', 'D', 'F', 'G')]

我写了代码

from itertools import product

def generate_block_list(policy):
    block_set = set()

    # Generate block list for each entity in the policy
    for entity in policy:
        other_entities = [e for e in policy if e != entity]

        # Generate all possible combinations of the current entity with other entities
        combinations = list(product(entity, *other_entities))
        unique_combinations = [tuple(sorted(set(combination))) for combination in combinations]

        # Add combinations to the block list
        block_set.update(unique_combinations)

    block_list = list(block_set)
    return block_list

# Example usage:
policy1 = [['A'], ['B', 'C'], ['D']]
block_list1 = generate_block_list(policy1)
print("\nPolicy:", policy1)
print("Block List:", block_list1)

policy2 = [['A', 'B'], ['B', 'C'], ['D']]
block_list2 = generate_block_list(policy2)
print("\nPolicy:", policy2)
print("Block List:", block_list2)

policy3 = [['A'], ['B', 'C'], ['D', 'E']]
block_list3 = generate_block_list(policy3)
print("\nPolicy:", policy3)
print("Block List:", block_list3)

policy4 = [['A'], ['B', 'C'], ['D', 'E'], ['F'], ['G']]
block_list4 = generate_block_list(policy4)
print("\nPolicy:", policy4)
print("Block List:", block_list4)

我得到了输出：

政策：[['A']，['B'，'C']，['D']] 阻止列表：[('A', 'C', 'D'), ('A', 'B', 'D')]

政策：[['A', 'B'], ['B', 'C'], ['D']] 阻止列表：[('A', 'C', 'D'), ('A', 'B', 'D'), ('B', 'D'), ('B', 'C' ，'D')]

政策：[['A']，['B'，'C']，['D'，'E']] 阻止列表：[('A', 'C', 'D'), ('A', 'B', 'D'), ('A', 'C', 'E'), ('A' ，'B'，'E'）]

政策：[['A']、['B'、'C']、['D'、'E']、['F']、['G']] 阻止列表：[('A'、'B'、'E'、'F'、'G')、('A'、'C'、'D'、'F'、'G')、(' A'、'C'、'E'、'F'、'G'), ('A'、'B'、'D'、'F'、'G')]

实体很常见的政策2是失败的。帮我解决一下。或者建议更好的方法。阻止列表：[('A', 'C', 'D'), ('A', 'B', 'D'), ('B', 'D'), ('B', 'C' , 'D')] 是错误的，应该是阻止列表：[('A', 'C', 'D'), ('B', 'D')]

Answer 1

我不确定为什么你不使用内置的组合方法，并且只计算某些组合而不计算其他组合，但这样的方法应该可行：

from itertools import combinations

def all_combinations(lst):
    for i in range(2,len(lst)+1):
        for combination in combinations(lst,i):
            yield set(combination)

def is_allowed(combination,allowed_connections):
    for connection in allowed_connections:
        if connection == combination:
            return True
    return False
            
policy = [['A'], ['B', 'C'], ['D']]
all_nodes = [item for group in policy for item in group]
allowed_connections = [set(group) for group in policy if len(group)>1]
block_list = [combination for combination in all_combinations(all_nodes) if not is_allowed(combination,allowed_connections)]
print(block_list)

这将阻止所有未明确允许的内容。

Answer 2

假设您无法控制接收“允许”连接的数据结构，下面是一个相当有效地生成一组阻止连接的示例。将阻止（或允许）的连接放在更合适的数据集中，可以对成员资格进行持续时间检查。

如果您有很多节点，您可能应该切换到每个节点允许的连接的字典，这比像本示例那样枚举它们要好。

代码：

from itertools import combinations as c
from typing import Iterable

allowed =  [['A'], ['B', 'C', 'E'], ['D']]

def block_list(allowed) -> set:
    all_nodes = {t for tt in allowed for t in tt}
    allowed_connex = set()
    for t in allowed:
        if len(t) > 1:
            allowed_connex.update(c(sorted(t), 2))
    all_connex = set(c(sorted(all_nodes), 2))
    blocked_connex = all_connex - allowed_connex
    return blocked_connex

def is_blocked(connection, blocked_connex: Iterable) -> bool:
    return tuple(sorted(connection)) in blocked_connex

# example
allowed = [['A'], ['B', 'C', 'E'], ['D']]
blocked = block_list(allowed)
print(f"Connection B-A is blocked: {is_blocked(('B', 'A'), blocked)}")

# policy 2 example
allowed_2 = [['A', 'B'], ['B', 'C'], ['D']]
blocked_2 = block_list(allowed_2)
print(blocked_2)

输出：

Connection B-A is blocked: True
{('B', 'D'), ('C', 'D'), ('A', 'C'), ('A', 'D')}