Permutations Between Two Lists of Unequal Length

Permutations between two lists of unequal length

Note: This answer is for the specific question asked above. If you are here from Google and just looking for a way to get a Cartesian product in Python, itertools.product or a simple list comprehension may be what you are looking for - see the other answers.

---

Suppose len(list1) >= len(list2). Then what you appear to want is to take all permutations of length len(list2) from list1 and match them with items from list2. In python:

import itertools
list1=['a','b','c']
list2=[1,2]

[list(zip(x,list2)) for x in itertools.permutations(list1,len(list2))]

Returns

[[('a', 1), ('b', 2)], [('a', 1), ('c', 2)], [('b', 1), ('a', 2)], [('b', 1), ('c', 2)], [('c', 1), ('a', 2)], [('c', 1), ('b', 2)]]

Find all possible combinations of different lists with Different lengths of output lists in Python(NOT a Duplicate)

Your goal is to select either one element or none from each list, right? So append None (or any other non-occurring value) to each list, run itertools.product(), and strip None from each of the results. Done.

>>> raw = itertools.product(a+[None], b+[None], c+[None])
>>> clean = [ [ e for e in result if e is not None ] for result in raw ]
>>> clean[:10]
[[2, 3, 10], [2, 3], [2, 6, 5], [2, 6, 10], [2, 6], [2, 9, 5], [2, 9, 10], [2, 9], 
[2, 5], [2, 10]]

How to iterate lists with different lengths to find all permutations?

I can't say if the following is the easiest way, but IMO it's the most efficient way. It's basically a generalized version of the my answer to the Looking at each combination in jagged array:

public static class Algorithms
{
    public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input)
    {
        var result = new T[input.Count];
        var indices = new int[input.Count];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < result.Length; pos++, index = 0)
            {
                indices[pos] = index;
                result[pos] = input[pos][index];
            }
            yield return result;
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos] + 1;
            }
            while (index >= input[pos].Count);
        }
    }
}

You can see the explanation in the linked answer (shortly it's emulating nested loops). Also since for performace reasons it yields the internal buffer w/o cloning it, you need to clone it if you want store the result for later processing.

Sample usage:

var list1 = new List<int> { 1 };
var list2 = new List<int> { 1, 2 };
var lists = new[] { list1, list2 };

// Non caching usage
foreach (var combination in lists.GenerateCombinations())
{
    // do something with the combination
}

// Caching usage
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList();

UPDATE: The GenerateCombinations is a standard C# iterator method, and the implementation basically emulates N nested loops (where N is the input.Count) like this (in pseudo code):

for (int i₀ = 0; i₀ < input[0].Count; i₀++)

for (int i₁ = 0; i₁ < input[1].Count; i₁++)

for (int i₂ = 0; i₂ < input[2].Count; i₂++)

...

for (int i_N-1 = 0; i_N-1 < input[N-1].Count; i_N-1++)

yield { input[0][i₀], input[1][i₁], input[2][i₂], ..., input[N-1][i_N-1] }

or showing it differently:

for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++)
{
    result[0] = input[0][indices[0]];
    for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++)
    {
        result[1] = input[1][indices[1]];
        // ...
        for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++)
        {
            result[N-1] = input[N-1][indices[N-1]];
            yield return result;
        }
    }
}

Faster way of building string combinations (with separator) than using a for loop?

Try this:

import itertools as it
combined = [f'{a}--{b}' for a, b in it.product(x, y)]

Output:

>>> combined
['sector_1--7',
 'sector_1--19',
 'sector_1--21',
 'sector_1--Ellipsis',
 'sector_2--7',
 'sector_2--19',
 'sector_2--21',
 'sector_2--Ellipsis',
 'sector_3--7',
 'sector_3--19',
 'sector_3--21',
 'sector_3--Ellipsis',
 'Ellipsis--7',
 'Ellipsis--19',
 'Ellipsis--21',
 'Ellipsis--Ellipsis']

---

Instead of all that though, you should use a combination of np.tile and np.repeat:

combined_df = pd.DataFrame({0: np.repeat(x, len(x)), 1: np.tile(y, len(x))})

Output:

>>> combined_df
           0         1
0   sector_1         7
1   sector_1        19
2   sector_1        21
3   sector_1  Ellipsis
4   sector_2         7
5   sector_2        19
6   sector_2        21
7   sector_2  Ellipsis
8   sector_3         7
9   sector_3        19
10  sector_3        21
11  sector_3  Ellipsis
12  Ellipsis         7
13  Ellipsis        19
14  Ellipsis        21
15  Ellipsis  Ellipsis

---

Related Topics