2

I have lists containing sublists. From theses lists I want to retrieve all combinations of integers that are in ascending order. Also the order of the sublists is important (see expected output).

It is not a bad thing when the function does also return the integers themselves (see optional sublists in expected output).

Also, when a sublist has more than one value, I want to consider these a seperate combinations as well. These values cannot occur together (see example 3).

example_list = [[1], [0], [4], [2]]
get_ascending_sublist_values(example_list)
>> [[1, 4], [1, 2], [0, 4], [0, 2] (optional: [1], [0], [4], [2])]

example_list2 = [[1], [0], [4], [2], [5]]
get_ascending_sublist_values(example_list2)
>> [[1, 4, 5], [1, 2, 5], [0, 4, 5], [0, 2, 5], [1, 4], [1, 2], [0, 4], [0, 2], [0, 5], [(optional: [1], [0], [4], [2], [5])]

example_list3 = [[0], [1, 4], [2]]
get_ascending_sublist_values(example_list3)
>> [[0, 1, 2], [0, 1], [0, 4], [0, 2], [1, 2], (optional: [1], [0], [4], [2])]
Improve this question
6
  • 1
    What have you tried? You may want to see itertools.combinations Commented Jun 10, 2021 at 12:08
  • Thanks for helping me! I have added some extra examples. I hope this clarifies your questions. Commented Jun 10, 2021 at 12:13
  • The third example makes no sense due to [1, 4] element. Commented Jun 10, 2021 at 12:19
  • The function has to make combinations with either 1 or 4 from the second sublist Commented Jun 10, 2021 at 12:21
  • Please see edit to the answer. Notice your case 2 is lacking some outputs, such as [4, 5]. Commented Jun 10, 2021 at 16:00

1 Answer 1

Reset to default
2

Use itertools.combinations and itertools.product. This is not an efficient solution, as this was not a requirement. Making this more efficient (i.e. using backtracking) will take quite some work, and still in theory it can't go below o(2^n).

from itertools import combinations
from itertools import product


def get_ascending_sublist_values(a):
    filtered = set()
    for comb_length in range(2, len(a)+1):
        combs = combinations(a, comb_length)

        results = []
        for comb in combs:
            for i in range(len(comb) - 1):
                prods = product(*comb)
                for prod in prods:
                    if sorted(prod) == list(prod):
                        results.append(tuple(sorted(prod)))

        for r in results:
            filtered.add(r)

    print(filtered)


a1 = [[1], [0], [4], [2]]
a2 = [[1], [0], [4], [2], [5]]
a3 = [[0], [1, 4], [2]]


get_ascending_sublist_values(a1)
print("----------")
get_ascending_sublist_values(a2)
print("----------")
get_ascending_sublist_values(a3)

out:

{(1, 2), (0, 2), (1, 4), (0, 4)}
----------
{(1, 2), (0, 4, 5), (4, 5), (1, 4), (1, 4, 5), (1, 5), (0, 5), (0, 2, 5), (0, 4), (2, 5), (1, 2, 5), (0, 2)}
----------
{(0, 1), (1, 2), (0, 1, 2), (0, 4), (0, 2)}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks this works perfect! I added: all_combs.append(list(chain.from_iterable(comb))) to chain the lists within the combination tuples.
Only one thing does not yet work as how I would like to see it. It is able to return combinations with 1 and 4. However, in my case integers that are from the same sublist cannot occur together in a combination.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.