改进使用笛卡尔积的算法

Question

改进使用笛卡尔积的算法

pythonalgorithmoptimizationcartesian-product

9

问题

假设你有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选择4，因此我填满了从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])

问题

虽然我的方法是可行的，但对于大型列表来说有些低效。您有什么改进算法的想法吗？

谢谢！

- McGuire

@Chris_Rands 看看我的更新编辑，有许多例子是无法实现从1到n的范围。 - McGuire

我明白了，之前有些困惑是因为你的代码在 Python 3 中运行失败了。在 Python 3 中，你需要使用 list(range(1, len(lists) + 1)) 来获取一个列表。 - Chris_Rands

当您选择一个列表来搜索数字时，您必须停在第一个新数字吗？还是可以选择列表中任意位置的一个数字？ - jdehesa

你想要的任何位置 @jdehesa - McGuire

你正在检查的整数列表是完全任意的吗？ - wwii

显示剩余5条评论

5个回答

2

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

- Peter de Rivaz

嗨，彼得，这是一个不错的解决方案，复杂度是多少？ - McGuire

应该大约是O(Esqrt(n))，其中E是您所有列表的总长度。 - Peter de Rivaz

1

笛卡尔积对我来说似乎是最直接的。为了简化你的代码，我会做以下几点：

从你的any表达式中删除[]，就像我在评论中提到的那样
在计算笛卡尔积之前将所有输入列表合并为集合——没有必要处理来自同一列表的重复值
将range(1, len(lists)+1)保存到本地变量中，并与其进行比较，而不是每次重新创建范围（这是一种常见的优化技术，称为“不变量提升”，其中一个在循环期间不发生变化的计算表达式被“提升”出循环，只计算一次）

但最终，计算输入列表的笛卡尔积，然后查找任何值为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)

- PaulMcG

谢谢你的方法，Paul，但我正在寻找一种新的方法，完全避免使用笛卡尔积。我相信一定有更快的解决方法，但我只是没有看到它。 - McGuire

1

这可以被看作是二分图匹配的问题。事实证明，霍尔定理可以告诉你答案（即是否存在匹配，而不是匹配本身）。以下是一个可能的实现（为了方便使用 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)。

- jdehesa

霍尔婚姻问题似乎非常有趣。然而，我仍然不完全确定在这个问题上O(2^N)是我们能做到的最好的，你不觉得吗？ - McGuire

@McGuire 嗯，这已经比尝试每种可能的组合要好了。我缺乏数学权威来确保没有更好的算法，但霍尔定理确实是“当且仅当”。然而，也许有更好的实现来检查条件，例如动态规划或其他方法... - jdehesa

可能更好地使用霍普克罗夫特-卡普算法来解决匹配问题 - 这将是O(Esqrt(V))，而不是O(2^V)。 - Peter de Rivaz

@PeterdeRivaz 这听起来像是一个独立的问题答案。 - jdehesa

@PeterdeRivaz 但问题实际上不是精确覆盖问题吗（有DLX解决方案）？ - גלעד ברקן

@גלעדברקן 我猜如果你运行Hopcroft-Karp算法，输出的大小为_N_，那么答案是肯定的，对吗？我还没有深入了解细节，但这就是我的理解，也许我理解错了。 - jdehesa

0

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

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]中获取。如果在进行这种连续消除时，任何一个可供选择的集合变为空，则没有解决方案。

- PaulMcG

谢谢Paul，这差不多是我想要的，看一下我给tobias的评论。 - McGuire

你会如何搜索“occurrences”？用图表吗？ - wwii

"occurrences" 只是一个被美化过的字典集合。要查找的列表值是键，它们所在的列表是值。 - PaulMcG

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tobias_k · Accepted Answer

与其按顺序测试所有组合，你可以通过先测试限制最多的列表并在将元素添加到解集时更新其他列表的替代方案，大大加快速度。这样，你可以在不回溯的情况下“解决”这两个示例。

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

以下是针对您提供的两个示例进行的调试/跟踪输出，以帮助您理解。首先是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)]