Unique combinations of all elements from long python list with elements from shorter list

Issue

I have two lists:

trips = ['trip1', 'trip2', 'trip3', 'trip4',...., 'tripN']

trucks = ['A', 'B', 'C']

I want to obtain all possible unique combinations so that all trips are matched with a truck in the trucks list. Please note, that all trucks must execute the same number of trips. In the above case for example if len(trips) == 12 then all trucks must be matched with 4 trips each.

Moreover,

extra_trips = len(trips) % len(trucks). If extra_trips != 0

then get also all the unique combinations of trips-trucks by matching the remaining trip with whatever truck.
I have done the following but I have trouble to proceed:

import itertools
import random
trucks=['A','B','C']
trips = ['trip1', 'trip2', 'trip3', 'trip4']

combs= [list(itertools.zip_longest(trucks, x)) for x in itertools.permutations(trips,len(trips))]

From the above code, I get this output:

[[('A', 'trip1'), ('B', 'trip2'), ('C', 'trip3'), (None, 'trip4')], [('A', 'trip1'), ('B', 'trip2'), ('C', 'trip4'), (None, 'trip3')], [('A', 'trip1'), ('B', 'trip3'), ('C', 'trip2'), (None, 'trip4')], [('A', 'trip1'), ('B', 'trip3'), ('C', 'trip4'), (None, 'trip2')], [('A', 'trip1'), ('B', 'trip4'), ('C', 'trip2'), (None, 'trip3')], [('A', 'trip1'), ('B', 'trip4'), ('C', 'trip3'), (None, 'trip2')], [('A', 'trip2'), ('B', 'trip1'), ('C', 'trip3'), (None, 'trip4')], [('A', 'trip2'), ('B', 'trip1'), ('C', 'trip4'), (None, 'trip3')], [('A', 'trip2'), ('B', 'trip3'), ('C', 'trip1'), (None, 'trip4')], [('A', 'trip2'), ('B', 'trip3'), ('C', 'trip4'), (None, 'trip1')], [('A', 'trip2'), ('B', 'trip4'), ('C', 'trip1'), (None, 'trip3')], [('A', 'trip2'), ('B', 'trip4'), ('C', 'trip3'), (None, 'trip1')], [('A', 'trip3'), ('B', 'trip1'), ('C', 'trip2'), (None, 'trip4')], [('A', 'trip3'), ('B', 'trip1'), ('C', 'trip4'), (None, 'trip2')], [('A', 'trip3'), ('B', 'trip2'), ('C', 'trip1'), (None, 'trip4')], [('A', 'trip3'), ('B', 'trip2'), ('C', 'trip4'), (None, 'trip1')], [('A', 'trip3'), ('B', 'trip4'), ('C', 'trip1'), (None, 'trip2')], [('A', 'trip3'), ('B', 'trip4'), ('C', 'trip2'), (None, 'trip1')], [('A', 'trip4'), ('B', 'trip1'), ('C', 'trip2'), (None, 'trip3')], [('A', 'trip4'), ('B', 'trip1'), ('C', 'trip3'), (None, 'trip2')], [('A', 'trip4'), ('B', 'trip2'), ('C', 'trip1'), (None, 'trip3')], [('A', 'trip4'), ('B', 'trip2'), ('C', 'trip3'), (None, 'trip1')], [('A', 'trip4'), ('B', 'trip3'), ('C', 'trip1'), (None, 'trip2')], [('A', 'trip4'), ('B', 'trip3'), ('C', 'trip2'), (None, 'trip1')]]

As you can see, it returns some combinations but for every comb, one trip is not matched.

Solution

Using zip_longest sort of sounds like the right approach, but you need to cycle the shorter list so that if they don’t share a common divisor some trucks will get repeated.

from itertools import cycle

def zip_cycle_shorter(a, b):
    if len(a) < len(b):
        a = cycle(a)
    elif len(b) < len(a):
        b = cycle(b)
    return zip(a, b)

list(zip_cycle_shorter([1,2,3], ['a','b','c','d','e']))

gives me: [(1, 'a'), (2, 'b'), (3, 'c'), (1, 'd'), (2, 'e')]

which is what I think you want. It might be instructive to try generalising this to support an arbitrary number of lists. For example, try filling in code to complete:

def zip_cycle_shorter(*lists):
   ...

(you just use comprehensions instead of handling each case specifically)

Answered By – Sam Mason

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0