从列表列表中的每个列表中获取唯一元素

Question

我有一个用整数填充的列表列表。这些整数代表图中的节点，主列表中的列表代表图中的循环。我想按照列表列表的顺序提取一组唯一的节点 - 每个循环一个节点。

示例：

我知道，只有两个节点的循环是不可能的，但这是我想出的最简单的重要示例，它应该清楚我在寻找什么。

cycles = [[11, 22, 55], [22, 44], [11, 33], [22, 33]]
result = [11, 44, 33, 22]

另一个可能的结果是 [22, 44, 11, 33]

我的解决方案：

我现在尝试的是使用 itertools.product，到运行遍历列表列表中元素的所有组合，直到我找到一个长度与我的列表数量相同的集合主列表。

def find_random_unique_combination_from_cycles(cycles):
    only_one = dict()
    for ci, cy in enumerate(cycles):
        for element in cy:
            if len([element for cyc in cycles if element in cyc]) == 1:
                only_one.update({element: ci})

    prod_cycles = [cycle for ci, cycle in enumerate(cycles) if ci not in only_one.values()]
    cycle_length = len(prod_cycles)
    result = []
    for combi in it.product(*prod_cycles, repeat=1):
        if len(set(combi)) == cycle_length:
            result = list(combi)
            break
    for element, index in only_one.items():
        result.insert(index, element)
    return result

问题：

此解决方案适用于上述示例和类似情况。但是对于具有越来越多循环的更大图形，它无法在适当的运行时间内找到解决方案（我不得不停止执行包含 ~200 个循环的列表）。我还尝试通过删除所有只有一个唯一元素的循环来减少列表列表的大小，但这并没有太大帮助。有没有更好更快的方法从每个列表列表中找到单个唯一元素？

非常感谢您的帮助！提前致谢！

Answer 1

cycles = [[11, 22], [22, 44], [11, 33], [22, 33]]
from itertools import product
a=list(product(*cycles))
[list(i) for i in a if len(i) == len(set(i))]

输出：

[[11, 44, 33, 22], [22, 44, 11, 33]]

如果您对效率感兴趣，可以查看 networkx 模块。

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
cycles = [(11, 22), (22, 44), (11, 33), (22, 33)]
G.add_edges_from(cycles)
nx.draw(G, with_labels=True, font_weight='bold')
G.nodes

G.nodes returns NodeView((11, 22, 44, 33))

Answer 2

我建议使用递归生成器方法将已用数字集带到下一级递归：

def getPath(cycles,used=None):
    if not cycles: yield [];return  # end of path
    if used is None: used = set()   # track used numbers
    for n in cycles[0]:             # take from first sub list
        if n in used: continue      # skip used, recurse, tagging used n
        yield from ([n]+p for p in getPath(cycles[1:],used|{n}))

输出：

cycles = [[11, 22, 55], [22, 44], [11, 33], [22, 33]]

for path in getPath(cycles): print(path)

[11, 44, 33, 22]
[22, 44, 11, 33]
[55, 22, 11, 33]
[55, 44, 11, 22]
[55, 44, 11, 33]
[55, 44, 33, 22]

如果你想让路径随机出来，可以在函数的开头添加这一行（并导入随机模块）：

if used is None: cycles = [random.sample(c,len(c)) for c in cycles]

这将允许您使用 next() 函数获得随机路径，而无需遍历所有组合：

randomPath = next(getPath(cycles))

请注意，生成器使用的是朴素的暴力遍历。还有优化空间

例如，可以检查循环中不同的未使用数是否足以覆盖子列表的数量。这将允许遍历分支更早短路。

...
if len(set().union(*cycles)-used)<len(cycles): return
for n in cycles[0]:
    ...

或者，可以从每个递归级别的循环列表中删除使用过的数字。

def getPath(cycles):
    if not cycles: yield [];return  # end of path
    if not all(cycles): return      # no path when there is an empty sublist
    for n in cycles[0]:             # take from first sub list
        nextCycles = [ [r for r in c if r!=n] for c in cycles[1:] ]
        yield from ( [n] + p for p in getPath(nextCycles) )

从列表列表中的每个列表中获取唯一元素

Get unique elements from each list in list of lists

python

itertools