Permutations of a list where a condition is met?

Question

Say I have a list of images ['1.jpg', '2.jpg', '3.jpg'...] and a corresponding list of vertical sizes [200, 400, 300...] I am trying to return all permutations of the list of images where the size lies within 10% of neighbouring elements. This is proving to be quite challenging!

I firstly tried itertools.permutations on the entire list and then iterated over each element and checked for validity. This worked, but when n > 12 it obviously becomes quite slow, and it seems inefficient to generate so many invalid permutations from the outset.

I then realised that the order is not especially important, as the images will be shown in a loop, so I fixed the first element in the list, but this still required me to permute every element, so again, inefficient.

I then went searching for another approach, and decided to try this:

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

This yielded a list of all possible pairings of images, which I could then validate and filter down to only pairs which met the +/- 10% criteria, so I was ultimately left with the following set of valid pairings meeting my criteria:

[('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')]

Inspecting it, it seems to make sense. So images 1 and 3 can sit next to each other, and so can 3 and 4, 4 and 2 etc. So what I am looking to generate is a recombination of these to find all (if any) valid permutations of the original images. So for example:

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

Would be a valid arrangement, whereas:

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

Would not, as the images sizes lie outside of 10% size constraint of each other.

I have considered recursion, but I am quite new to this and am not sure where to start.

Would appreciate any advice on how to solve this problem, as I have been trying for days!

Answer 1

This is a graph problem. Each node has a bidirectional edge to any node whose size is within 10%. Finding all permutations with your restrictions is isomorphic to finding all Hamiltonian paths in this graph.

First, you need to build the graph; use your favorite graph package or simpler representation. This pre-processing is necessarily a O(n^2), as the quantity of edges may be n(n-1)/2. However, in practical cases, you can sort the list by size first, which should give you an effective O(n log n) sort and O(n) graph building, as there will be only a handful of connections from each node to its neighbors. For instance, in your given mini-example, I'll add another file, so we have:

# 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]

From here, keep an upper-bound marker, mark

• Start at 95; make the edge to 100. Set mark = 1 (index of 100)
• Move to 100; make the edges to 102 & 110. mark = 3
• Move to 102; make the edge to 110 without checking; we already know it's within range, because of mark. Check against 120, which is too far.
• Move to 110; make the edge to 120 ... you get the idea from here.

Then you get to look up the algorithms available for an exhaustive traversal of the graph, i.e. a Hamiltonian path.