Combinations without using "itertools.combinations"

Question

What I'd need is to create combinations for two elements a time.

If a list contains: seq = ['A', 'B', 'C'] the output would be com = [['A', 'B'], ['A', 'C'], ['B', 'C']]

all this without itertools.combinations method.

I used the following code for the permutations. But how could I modify it to make it work with the combinations?

def permute(seq):

    if len(seq) <= 1:
        perms = [seq]
    else:
        perms = []
        for i in range(len(seq)):
            sub = permute(seq[:i]+seq[i+1:]) 
            for p in sub:    
                perms.append(seq[i:i+1]+p)

return perms

Barbabas

Why without itertools? – Malfunction

The equivalent source code for combinations is on the itertools documentation page. Just copy-paste it into your file. – Demarcate

Yea, I can't use alternative methods. Thanks, I'll take a look. – Barbabas

@Malfunction the itertools.combinations function returns lexicographic sort order which may be undesirable for lists of integers - ie combinations([1,2,10,3], 3) yields [1,2,10] before [1,2,3]. – Monoceros

Answer 1

If you don't want to use itertools, then use the documented pure-Python equivalent:

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

Cough

What's the Big O time complexity of this? I think it's O(r * (n! / (r! (n - r)!))): the while loops nCr times, and tuple(pool[i] for i in indices) makes each loop have O(r) work. So this iterative solution looks much more efficient than the recursive backtracking solution, which I think is O(n^r). – Perfuse

I haven't done an analysis of the complexity; at a glance I think you got the complexity correct. It certainly is well below O(nr). – Cough

Which if statement is that else inside the while loop associated with? I've never seen this before. – Androcles

@c_sagan: it isn't associated with any if statement, it's associated with the for loop. In python, while and for have else blocks too, executed when the loop completes without exiting through a break. – Cough

@c_sagan: so in this case, else: return executes when the current element index reaches the highest value it can reach (e.g. for 10 inputs with 3 combinations, that's indices 7, 8 and 9). – Cough

@MartijnPieters the complexity is o(#combinations) which is o(n choose r) which is o(n^(max(n-r, r))) – Shrift

@Gulzar: I simply quoted the documentation, this is not my own code. The code deals with indices into the iterable, finding the first index from the end that can be incremented, then after incrementing that value, propagating the next higher value to the next index, etc. The indices are then used to select the values from the input iterable. – Cough

@Gulzar: so, for the input iterable=[0, 1, 2, 3], r=3, you start with indexes [0, 1, 2], see that the 3rd index can be incremented so you get [0, 1, 3], see you can't increment the 3rd index further so move to the 2nd index and get [0, 2, 3], then move to the first index and you get [1, 2, 3]. Note how this matches the documented example in the docstring. – Cough

Answer 2

This is trivial to do directly:

def comb2(s):
    for i, v1 in enumerate(s):
        for j in range(i+1, len(s)):
            yield [v1, s[j]]

Then:

print list(comb2(['A', 'B', 'C']))

displays:

[['A', 'B'], ['A', 'C'], ['B', 'C']]

The only thing that makes combinations at all tricky is catering to a known-only-at-runtime number of elements to take at a time. So long as you know that number in advance, a fixed number of loops nested that deep does the job in an obvious way.

Span

Answer 3

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

Input:

combo2(list('ABC'),2)

Output:

[['A', 'B'], ['A', 'C'], ['B', 'C']]

Colloid

Answer 4

Here's a loose translation of the recursive C++ code in an answer to a similar question:

def combinations(sequence, length, NULL=object()):
    """ Find all combinations of the specified length from a sequence. """
    if length <= 0:
        combos = [NULL]
    else:
        combos = []
        for i, item in enumerate(sequence, 1):
            rem_items = sequence[i:]
            rem_combos = combinations(rem_items, length-1)
            combos.extend(item if combo is NULL else [item, combo]
                            for combo in rem_combos)
    return combos

print(combinations(['A', 'B', 'C'], 2))

Output:

[['A', 'B'], ['A', 'C'], ['B', 'C']]

Satisfactory

Answer 5

Combination in pure python

# generate combination of two list
import copy
def extend_list(list1,list2):
    temp=[];temp=copy.deepcopy(list1);temp.append(list2)
    return temp
def combination(list1, list2):
    return [extend_list(item1,item2) if type(item1) is list else [item1,item2] for item1 in list1 for item2 in list2]

# generate all combination of list of variables
def list_combination(list_of_variables):
    '''list_of_variables is a list of list e.g [[1,2],['True','False']]'''
    node_combinations=[]
    no_of_variables=len(list_of_variables)
    node_combinations=list_of_variables[0]
    for i in range(no_of_variables-1):
        node_combination = combination(node_combinations,list_of_variables[i+1])
        node_combinations=node_combination
    return node_combinations

Output

input_list = [['TRUE', 'FALSE'], [1, 2], ['TRUE', 'FALSE']]
list_combination(input_list)

[['TRUE', 1, 'TRUE'],
 ['TRUE', 1, 'FALSE'],
 ['TRUE', 2, 'TRUE'],
 ['TRUE', 2, 'FALSE'],
 ['FALSE', 1, 'TRUE'],
 ['FALSE', 1, 'FALSE'],
 ['FALSE', 2, 'TRUE'],
 ['FALSE', 2, 'FALSE']]

Secretarygeneral