改进使用笛卡尔积的算法

Question

问题

假设您有n整数列表,其中每个列表仅包含from 1到的整数n.例如,对于n = 4,我们可能有:

a_1 = [1, 2]
a_2 = [3]
a_3 = [4, 1, 1]
a_4 = [2, 3]

现在我的问题是:我可以勾选这些列表之间1和之间的所有整数,但是一旦我找到一个数字,我就不能再使用该列表来查找后续数字了吗？nn

例如,在上面的示例中n = 4,我可以选择1,from a_1,from a_4,3 from a_2和4 for a_3,因此我填充了从1到4的所有数字,但仅使用每个列表一次.

我无法找到范围(因此应该返回False)的示例将是:

a_1 = [1, 2]
a_2 = [3, 3, 5]
a_3 = [4]
a_4 = [5]
a_5 = [3, 4, 5]

原因是因为如果我从a_1中选择1,我就不能从任何列表中选择2.

途径

这是我目前直截了当的方法.我制作列表的笛卡尔积,并检查是否有任何,排序,将是一个范围.

import itertools

def fillRange(lists):
  cartesian = itertools.product(*lists)
  return any([sorted(comb) == range(1, len(lists) + 1) for comb in cartesian])

题

虽然我的方法有效,但对于大型列表来说,它变得有点低效.有关如何改进此算法的任何想法？

谢谢!

Answer 1

您可以将其表述为二部图中的最大流问题，其中左侧节点对应于列表，右侧节点对应于整数 1 到 n。

当且仅当整数在相应的列表中时，图中就有一条边。

图中所有容量都等于 1。

如果你能找到从左侧到右侧的大小为 n 的流，那么问题就解决了。

执行此操作的 Python 代码如下：

import networkx as nx

a_1 = [1, 2]
a_2 = [2]
a_3 = [4, 1, 1]
a_4 = [2, 3]
A = [a_1,a_2,a_3,a_4]
n = 4

G=nx.DiGraph()
for i,a in enumerate(A):
    for j in set(a):
        l = 'list'+str(i)
        G.add_edge(l,j,capacity=1)
        G.add_edge('start',l,capacity=1)
for j in range(1,n+1):
    G.add_edge(j,'dest',capacity=1)
v,flow = nx.maximum_flow(G,'start','dest')
if v<n:
    print 'Impossible'
else:
    for i,a in enumerate(A):
        for j in set(a):
            if flow['list'+str(i)][j]>0:
                print 'Use',j,'from list',a

这打印：

Use 1 from list [1, 2]
Use 2 from list [2]
Use 4 from list [4, 1, 1]
Use 3 from list [2, 3]