combination element in list with possible way is going over O(n^n)

Question

I making something that combination each element in list in possible way without duplicate but it took long time for working, I dont know to improve performance. I need to decrease time of my combination function and you can see in result my code not return complete answer it need to run twice for sure, Thanks.

To use: (forget about find_subsets() it work fine)

SIZE = 4
mylist = list(range(SIZE))
subsets = find_subsets(mylist)
result = combination(subsets , SIZE)

My code:

def combination(subsets, n):
    subsets_size = len(subsets)
    combinelist = []
    templist = []

    for first_element in subsets:
        for follow_element in subsets:
            if templist == []: # first loop
                templist.append(first_element)
                templist_size = len(first_element)
            else:
                if not isDuplicate(templist, follow_element):
                    templist.append(follow_element)
                    templist_size += len(follow_element)

                # case : full element (templist has all number)
                # then find combination from current again
                if templist_size == n:
                    # add new combination to combinelist
                    if templist not in combinelist:
                        combinelist.append(templist) 
                    # renew templist
                    templist = []
                    templist.append(first_element)
                    templist_size = len(first_element)
    return combinelist

def isDuplicate(mainlist, subset):
    for isubset in mainlist:
        if len(list(set(isubset) & set(subset))) > 0:
            return True
    return False

Output:

Mylist
    [0, 1, 2, 3]

Subsets
    (0,)
    (1,)
    (2,)
    (3,)
    (0, 1)
    (0, 2)
    (0, 3)
    (1, 2)
    (1, 3)
    (2, 3)
    (0, 1, 2)
    (0, 1, 3)
    (0, 2, 3)
    (1, 2, 3)
    (0, 1, 2, 3)


Result
    [(0, 1, 2, 3)]
    [(0, 1, 2), (3,)]
    [(0, 1, 3), (2,)]
    [(0, 2, 3), (1,)]
    [(1, 2, 3), (0,)]
    [(0,), (1, 2), (3,)]
    [(1,), (0, 2), (3,)]
    [(2,), (0, 1), (3,)]
    [(3,), (0, 1), (2,)]
    [(0, 1), (3,), (2,)]
    [(0, 2), (3,), (1,)]
    [(0, 3), (2,), (1,)]
    [(1, 2), (3,), (0,)]
    [(1, 3), (2,), (0,)]
    [(2, 3), (1,), (0,)]
    [(0,), (1,), (2,), (3,)]

It missing [(0,1),(2,3)] [(0,2),(1,3)] [(0,3),(1,2)] and more i dont know.

itertools combinations gives "r-length tuples, in sorted order, no repeated elements" https://docs.python.org/3/library/itertools.html#itertools.combinations — Vorsprung, Jun 12 '21 at 10:42
Is this what you're looking for? https://stackoverflow.com/a/30134039/2482744 — Alex Hall, Jun 12 '21 at 11:27

score 0 · Accepted Answer · edited Jan 18 '22 at 10:46

For a non-recursive generator of combinations you can use the fact that a set of n distinct items has 2^n combinations in total. It's easy to "believe" as each item can either be part of a given combination, or not, so there are 2*2*2*...*2 "decisions" to make.
So one half of the solution is a loop over something like range(2**len(mainlist)).

The other half is picking a subset for a bit-pattern. We need to check if the kth bit of a number n (between 0 and 2*2*...*2) happens to be 0 or 1. I don't know a Pythonic way for it, but in practically all programming languages it can be done via shifting, n>>k and checking if the lowest bit is 1 via masking, so a check like (n>>k)&1==1 (>> has a lower precedence than &).

def subset(items,bits):
  return [items[i] for i in range(len(items)) if (bits >> i) & 1 == 1]

def combinations(items):
  n = len(items)
  if n != len(set(items)): # if there are repeated elements, this approach is not enough
    return "nope"
  return [subset(items,bits) for bits in range(2**n)]

print(combinations([1,2,3,4]))

will produce

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

combination element in list with possible way is going over O(n^n)

1 Answers1