3
\$\begingroup\$

generate all combinations from list of numbers,the combinations can be pair of two numbers

example 1 : list of 2 numbers [1,2]

[
[[1],[2]],
[[1,2]]
]

example 2 : list of 3 numbers [1,2,3]

[
[[1], [2], [3]],
[[1], [2, 3]],
[[1, 3], [2]],
[[1, 2], [3]]
]

example 3 : list of 4 numbers [1,2,3,4]

[
[[1], [2], [3], [4]]
[[1], [2], [3, 4]],
[[1], [2, 4], [3]],
[[1], [2, 3], [4]],
[[1, 4], [2], [3]],
[[1, 3], [2], [4]],
[[1, 2], [3], [4]],
[[1, 2], [3, 4]],
[[1, 3], [2, 4]],
[[1, 4], [2, 3]]
]

The current implementation works but it is slow for list of 10 numbers

from itertools import combinations
def get_all_order_combinations(nums, first=True):
    if first and len(nums) == 1:
        return [[[nums[0]]]]
    if len(nums) == 2:
        nums.sort()
        return [
            [[nums[0]], [nums[1]]],
            [[nums[0], nums[1]]]
        ]
    else:
        all_results = []
        for i in range(0, len(nums)):
            temp_list = list(nums)
            del temp_list[i]
            current_num = nums[i]
            results = get_all_order_combinations(temp_list, False)
            results = [[[current_num]]+result for result in results]
            for result in results:
                result.sort()
                if result not in all_results:
                    all_results.append(result)
        if len(nums) >= 4:
            for comb in combinations(nums, 2):
                comb = list(comb)
                results = get_all_order_combinations(
                    [n for n in nums if n not in comb]
                    ,False
                )
                results = [[comb]+result for result in results]
                for result in results:
                    result.sort()
                    if result not in all_results:
                        all_results.append(result)
        return all_results

an old implementation that works only for 5 numbers

from itertools import combinations
from functools import reduce 

def _is_unique(items):
    return len(items) == len(set(items))


def _is_valid(items, ids_len):
    if _is_unique(items):
        if ids_len == len(items):
            return True
        else:
            return False
    else:
        return False


def _generate_combinations(combs, ids):
    all_combinations = []
    ids_len = len(ids)
    for i in range(1, len(combs)+1):
        if i > ids_len:
            break
        if i == ids_len:
            all_combinations += [[[id] for id in ids]]
            continue
        if i == 1:
            if ids_len == 2:
                all_combinations += [[ids]]
            continue

        comb = combinations(combs, i)
        all_combinations += list(comb)  

    all_combinations = [list(c) for c in all_combinations if _is_valid(
        reduce(lambda a, b: a+b, c), ids_len)]
    return all_combinations


def _generate_initial_combinations(ids):
    all_combinations = []
    for i in range(1, 3):
        comb = combinations(ids, i)
        all_combinations += list(comb)
    all_combinations = [list(c) for c in all_combinations]
    return all_combinations


def get_all_order_combination_old(ids_list):
    combs = _generate_initial_combinations(ids_list)
    results = _generate_combinations(combs, ids_list)
    return results
\$\endgroup\$
9
  • 2
    \$\begingroup\$ Example 2: I suspect you lack [1, 2, 3]. \$\endgroup\$
    – coderodde
    Aug 10, 2022 at 16:13
  • 1
    \$\begingroup\$ Also, it seems your aim is to generate so called partitions of a set. \$\endgroup\$
    – coderodde
    Aug 10, 2022 at 16:14
  • \$\begingroup\$ the way we write [1,2,3] is [[1],[2],[3]] \$\endgroup\$ Aug 10, 2022 at 18:09
  • 1
    \$\begingroup\$ (I guess coderodde intended [[1, 2, 3]]: partition into one triple.) \$\endgroup\$
    – greybeard
    Aug 11, 2022 at 6:48
  • \$\begingroup\$ Specification by examples is almost as bad as specification by (old) undocumented code. Does ordered partitions into singletons and pairs fit the bill? \$\endgroup\$
    – greybeard
    Aug 11, 2022 at 6:52

1 Answer 1

1
\$\begingroup\$

What should be bogging this down is generating equivalent partitions more than once (and checking for duplicates) -
a first improvement was to add a start parameter to the recursive function, set to i in the first/shorten by 1 loop.
(The next one may be dynamic programming/function result caching.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.