python - 满足条件的列表的排列？

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 ... 你从这里得到了这个想法。

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