符合条件的列表的排列？

Question

假设我有一个图像列表['1.jpg', '2.jpg', '3.jpg'...]和相应的垂直尺寸列表[200, 400, 300...]我试图返回图像列表的所有排列,其中大小位于相邻元素的10%之内.这被证明是非常具有挑战性的!

我首先尝试itertools.permutations了整个列表,然后遍历每个元素并检查其有效性.这很有效,但是当n > 12它显然变得非常慢时,从一开始就产生如此多的无效排列似乎效率低下.

然后我意识到顺序并不是特别重要,因为图像将在循环中显示,所以我修复了列表中的第一个元素,但这仍然需要我置换每个元素,所以再次,低效.

然后我去寻找另一种方法,并决定试试这个:

images = ['1.jpg', '2.jpg', '3.jpg', '4.jpg', '5.jpg']
v_size = [100, 125, 110, 120, 95]
pairs = list(itertools.permutations(images,2))

这产生了所有可能的图像配对的列表,然后我可以验证并过滤到仅满足+/- 10%标准的对,因此我最终留下了满足我的标准的以下有效配对集:

[('1.jpg', '3.jpg'), ('1.jpg', '5.jpg'), ('2.jpg', '4.jpg'), ('3.jpg', '1.jpg'), ('3.jpg', '4.jpg'), ('4.jpg', '2.jpg'), ('4.jpg', '3.jpg'), ('5.jpg', '1.jpg')]

检查它,似乎有道理.因此,图像1和3可以彼此相邻,因此3和4,4和2等也是如此.所以我想要生成的是这些的重新组合以找到原始图像的所有(如果有的话)有效排列.例如:

['5.jpg', '1.jpg', '3.jpg', '4.jpg', '2.jpg']

将是一个有效的安排,而:

['1.jpg', '2.jpg', '3.jpg', '4.jpg', '5.jpg']

不会,因为图像大小超出了彼此10%的大小限制.

我考虑过递归,但我对此很新,不知道从哪里开始.

非常感谢有关如何解决这个问题的任何建议,因为我已经尝试了好几天!

Answer 1

这是一个图问题。每个节点都有一条到任何大小在 10% 以内的节点的双向边。查找具有限制的所有排列与查找该图中的所有哈密顿路径是同构的。

首先，您需要构建图表；使用您最喜欢的图形包或更简单的表示。此预处理必然是O(n^2)，因为边的数量可能是n(n-1)/2。然而，在实际情况中，您可以首先按大小对列表进行排序，这应该为您提供有效的O(n log n)排序和O(n)图形构建，因为从每个节点到其对应的节点只有少数连接。邻居。例如，在您给定的迷你示例中，我将添加另一个文件，因此我们有：

# Before sorting
images = ['1.jpg', '2.jpg', '3.jpg', '4.jpg', '5.jpg', '6.jpg']
v_size = [100, 125, 110, 120, 95, 102]

# After sorting
images = ['5.jpg', '1.jpg', '6.jpg', '3.jpg', '4.jpg', '2.jpg']
v_size = [95, 100, 102, 110, 120, 125]

从这里开始，保留一个上限标记，mark

• 从95开始；将边设置为 100。设置mark = 1（索引为 100）
• 移至100；将边缘设置为 102 和 110。 mark = 3
• 移至102；不检查而将边缘设为110；我们已经知道它在范围内，因为mark. 检查 120，这太远了。
• 转至110；将边缘设置为 120...您可以从这里得到这个想法。

然后，您可以查找可用于彻底遍历图的算法，即哈密顿路径。