改进使用笛卡尔积的算法

Question

问题

假设您有 n 个整数列表，其中每个列表仅包含 1 到 n 范围内的整数。例如，对于 n = 4，我们可能有：

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

现在我的问题是： 我可以勾选那些 n 列表中 1 和 n 之间的所有整数吗？发现一旦我找到一个号码，我就不能再使用该列表来查找后续号码了吗？

例如，在上面的 n = 4 示例中，我可以从 a_1 中选择 1，从 a_4 中选择 2，从 a_2 中选择 3， a_3，因此我填写了从 1 到 4 的所有数字，但每个列表只使用一次一次。

一个我找不到范围（因此应该 return 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

笛卡尔积对我来说似乎是最直接的。我将执行以下操作来简化您的代码：

从你的 any 表达式中删除 []，正如我在评论中提到的那样
在计算笛卡尔积之前将所有输入列表折叠成集合 - 处理来自同一列表的重复值没有意义
将 range(1, len(lists)+1) 保存到局部变量并与其进行比较，而不是每次都重新创建范围（这是一种称为 "invariant lifting" 的常见优化技术，其中计算表达式在循环期间没有改变的是 "lifted" 在循环之外并且只计算一次）

但最终，计算输入列表的 a 笛卡尔坐标，然后查找值 1-n 的基本算法仍然与您最初编写的相同。

def fillRange(lists):
  cartesian = itertools.product(*(set(x) for x in lists))
  target = list(range(1, len(lists) + 1))
  return any(sorted(comb) == target for comb in cartesian)

Answer 2

您可以先测试最受约束的列表，然后在向解决方案集添加元素时更新其他列表中的备选方案，而不是按顺序测试所有组合，从而大大加快此过程。这样，您可以 "solve" 您的两个示例而无需回溯一次。

def search(n, lists):
    if n == 0:
        yield []
    else:
        lists = [l for l in lists if l != []]
        if len(lists) >= n:
            least = min(lists, key=len)
            for val in least:
                new = [[x for x in lst if x != val] for lst in lists if lst is not least]
                for res in search(n-1, new):
                    yield [val] + res

下面是您的两个示例的一些 debugging/tracing 输出，以帮助理解。第一个值是 n，然后是 lists，最后是之前选择的 val.

4 [[1, 2], [3], [4, 1, 1], [2, 3]] None
3 [[1, 2], [4, 1, 1], [2]] 3
2 [[1], [4, 1, 1]] 2
1 [[4]] 1
0 [] 4 --> solution
[3, 2, 1, 4]

5 [[1, 2], [3, 3, 5], [4], [5], [3, 4, 5]] None
4 [[1, 2], [3, 3, 5], [5], [3, 5]] 4
3 [[1, 2], [3, 3], [3]] 5
2 [[1, 2], []] 3 --> abort

如果您还想要从中获取元素的列表的索引，代码会稍微复杂一些，但不会太多：

def search(n, lists):
    if n == 0:
        yield []
    else:
        if sum(1 for l in lists if l) >= n:
            i = min(range(len(lists)), key=lambda x: (lists[x] == [], len(lists[x])))
            for val in lists[i]:
                new = [[x for x in lst if x != val] if lst is not lists[i] else [] for lst in lists]
                for res in search(n-1, new):
                    yield [(i, val)] + res

第一个例子的结果是 [(1, 3), (3, 2), (0, 1), (2, 4)]

Answer 3

您可以尝试映射哪些值出现在哪个列表中，然后从那里分解您的问题。此代码构建了那种反向查找：

In[38]: from collections import defaultdict
In[39]: occurrences = defaultdict(set)
In[40]: for i,ll in enumerate(lists):
   ...:     for x in ll:
   ...:         occurrences[x].add(i)
   ...:         
In[41]: print(occurrences)
defaultdict(<class 'set'>, {1: {0, 2}, 2: {0, 3}, 3: {1, 3}, 4: {2}})
In[42]: print(dict(occurrences.items()))
{1: {0, 2}, 2: {0, 3}, 3: {1, 3}, 4: {2}}

比如你一眼就可以看出，4只存在于list[2]中（也就是你原问题中的a_3）。从那里，如果您从其他值中删除 2，则 1 仅存在于 list[0] 中。去掉0表示2只存在于list[3]中，3则只能从list[1]中得到。如果在进行此连续消除时，从 select 开始的任何集合变为空，则无解。

Answer 4

这可以看作是matching in a bipartite graph. As it turns out, Hall's marriage theorem的一个问题告诉你答案（即匹配是否存在，而不是匹配本身）。这是一个可能的实现（为方便起见使用 NumPy）：

from itertools import chain, combinations
import numpy as np

# Recipe from itertools docs: https://docs.python.org/3/library/itertools.html#itertools-recipes
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def has_matching(lists):
    n = len(lists)
    m = np.array([np.logical_or.reduce(np.arange(1, n + 1)[:, np.newaxis] == lst, axis=1)
                  for lst in lists])
    m = m.astype(int)
    for s in powerset(range(n)):
        if np.sum(np.logical_or.reduce(m[s, :], axis=0)) < len(s):
            return False
    return True


lists1 = [[1, 2],
          [3],
          [4, 1, 1],
          [2, 3]]
print(has_matching(lists1))
>>> True

lists2 = [[1, 2],
          [3, 3, 5],
          [4],
          [5],
          [3, 4, 5]]
print(has_matching(lists2))
>>> False

然而，这需要你遍历 {1, ..., n} 的每个子集，所以我猜算法是 O(2^N).不是很好，但可能比遍历整个笛卡尔积要好，我猜它是 O(N^N).

Answer 5

您可以将其表述为二部图中的最大流问题，其中左侧节点对应列表，右侧节点对应整数 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]

改进使用笛卡尔积的算法

Improving algorithm that uses the cartesian product

python

algorithm

optimization

cartesian-product

问题

方法

问题