How to Find All Combination of a List of size from 1 to length of list (Without Itertools)

Question

Is there a simple algorithm (most likely recursive algorithm) that finds all combinations of a list and of all sizes (from combo of size 1 to combo of size length of a list)?

For example: if I have a list = [1, 2, 3, 4], the combinations of all sizes I should get are:

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

So I only know a recursive algorithm I found online that finds a combination of size n but not for all sizes from 1 to length of the list. Order doesn't matter in combinations.

Here is the code I found online:

def n_length_combo(lst, n): 
  
    if n == 0: 
        return [[]] 
  
    l =[] 
    for i in range(0, len(lst)): 
      
        m = lst[i] 
        remLst = lst[i + 1:] 
      
        for p in n_length_combo(remLst, n-1): 
            l.append([m]+p) 
          
    return l

This is good only for combinations of size n. But I want to find combinations for all sizes from 1 to the length of a list.

Any ideas here?

Answer 1

Call it with the length of the list using len function:

n_length_combo(lst, len(lst))

Even better, if you don't want to always pass the second argument you can assign a default value:

def n_length_combo(lst, n=len(lst)): 

Answer 2

See below (using itertools)

from itertools import combinations

lst = [1, 2, 3, 4]
final_lst = []
for x in lst[1:]:
    final_lst.extend(combinations(lst, r=x))
print(final_lst)

output

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

Answer 3

For every element of the list: you can either take that element, or not take it. This gives us a recurrence formula:

combinations(l) = combinations(l[:-1]) + [add l[-1] to every element of combinations(l[:-1])

This gives us a recursive algorithm:

def combinations(l):
  if not l:
    return [[]]
  else:
    c = combinations(l[:-1])
    return c + [r+[l[-1]] for r in c]

print(combinations(range(4)))
# [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]

Of course there is no need for recursion:

def combinations(l):
  c = [[]]
  for x in l:
    c = c + [r+[x] for r in c]
  return c

print(combinations(range(4)))
# [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]

Answer 4

Use the function you have, but collect the results for all the combo lengths you need:

L = [1,2,3,4]
result = []
for n in range(1,len(L) + 1):
    result.extend(n_length_combo(L,n))
print(result)

Output:

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

Here's a complete recursive generator:

def all_combo(lst): 
    def n_combo(lst,n):
        if n == 1: 
            yield from ([n] for n in lst)
        for i,item in enumerate(lst):
            for combo in n_combo(lst[i+1:],n-1):
                yield [item] + combo
    for n in range(1,len(lst)+1):
        yield from n_combo(lst,n)

L = list(all_combo([1,2,3,4]))
print(L)

Output:

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