How can I find all sets of integers within certain ranges?

Question

I have a list of lists, and I want to find all permutations of the items in the lists. I'm having a hard time explaining this, so here's an example. I have three lists:

level_list = [
    [1, 2, 3],
    [1, 2],
    [1, 2, 3, 4, 5]
]

I want to end up with a list of lists, all of which are length 3 and contain the potential options from my original 3 lists within them; like this:

final_list =[
    [1, 1, 1],
    [1, 1, 2],
    [1, 1, 3],
    [1, 1, 4],
    [1, 1, 5],
    [1, 2, 1],
    [1, 2, 2],
    [1, 2, 3],
    [1, 2, 4],
    [1, 2, 5],
    [2, 1, 1],
    [2, 1, 2],
    [2, 1, 3],
    [2, 1, 4],
    [2, 1, 5],
    [2, 2, 1],
    [2, 2, 2],
    [2, 2, 3],
    [2, 2, 4],
    [2, 2, 5],
    [3, 1, 1],
    [3, 1, 2],
    [3, 1, 3],
    [3, 1, 4],
    [3, 1, 5],
    [3, 2, 1],
    [3, 2, 2],
    [3, 2, 3],
    [3, 2, 4],
    [3, 2, 5]
]

It feels like I should be doing what I would do if I were going to do this manually, which would be to:

Increment the final sublist, holding the values of the other two constant at 1
Increment the middle sublist, holding the values of the first sublist constant at 1 and continuing to vary the final sublist
Finish up with the first sublist

I could do this with nested for loops if I hard-coded the # of lists, but that feels very "un-pythonic" and also isn't really feasible because I ultimately need this to be a function that works with any number of sublists:

final_list = []
for i1 in level_list[0]:
    for i2 in level_list[1]:
        for i3 in level_list[2]:
            final_list.append([i1, i2, i3])
            
print(final_list)

It's almost like I need a for loop of for loop nesting. Or some more clever solution than what I can envision. I'm also open to solutions that just take in the min and max -- this will always be lists of integers with 1 step between them.

That was SO fast. I think I didn't really know the right keywords to search, so thank you all! — Laura, Sep 23 '20 at 18:56

score 4 · Accepted Answer · answered Sep 23 '20 at 18:54

4

You may use itertools.product that

does the Cartesian product of input iterables.

final_list = list(itertools.product(*level_list)))

Example

list(itertools.product(*[[1, 2], [3, 4]]))) # [(1, 3), (1, 4), (2, 3), (2, 4)]

answered Sep 23 '20 at 18:54

azro

53,056
7
34
70

score 0 · Answer 2 · answered Sep 23 '20 at 19:27

Edit: Solution posted by @azro is better.

        level_list = [
            [1, 2, 3],
            [1, 2],
            [1, 2, 3, 4, 5]
        ]

        nb_lists = len(level_list)
        least_significant_position = nb_lists - 1
        indices = defaultdict(int)
        solution_found = False
        solution = list()

        while not solution_found:
            possible_combination = list()
            index_incremented = False

            for i in range(nb_lists, 0, -1):
                current_selection = level_list[i - 1]
                index = indices[i - 1]
                possible_combination.insert(0, current_selection[index])

                max_index_for_this_list = len(current_selection) - 1

                if not index_incremented and index < max_index_for_this_list:
                    indices[i - 1] += 1
                    index_incremented = True

                    if i - 1 != least_significant_position:
                        less_significant_position = i

                        while less_significant_position <= least_significant_position:
                            indices[less_significant_position] = 0
                            less_significant_position += 1

            solution.append(possible_combination)

            if not index_incremented:
                solution_found = True

        print(solution.__str__())

How can I find all sets of integers within certain ranges?

2 Answers2