How to get all combinations of length n in python

Question

I was wondering if there is any way of getting all combinations of length n from a list of numbers.

For example, if my list is [1, 2, 3, 4], and I want to output (if I chose n = 3)

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

the other permutations like [2,1,3] are of no use to me.

Answer 1

itertools can do this

import itertools
for comb in itertools.combinations([1, 2, 3, 4], 3):
    print comb

Outputs

(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)

Answer 2

Adding the recursive function:

def combinations(array, tuple_length, prev_array=[]):
    if len(prev_array) == tuple_length:
        return [prev_array]
    combs = []
    for i, val in enumerate(array):
        prev_array_extended = prev_array.copy()
        prev_array_extended.append(val)
        combs += combinations(array[i+1:], tuple_length, prev_array_extended)
    return combs

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

Outputs:

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

Answer 3

In case you don't want to calculate all the combinations at once, you can make a generator that returns the combinations of length n as follows:

def combinations(list_get_comb, length_combination):
    """ Generator to get all the combinations of some length of the elements of a list.

    :param list_get_comb: List from which it is wanted to get the combination of its elements.
    :param length_combination: Length of the combinations of the elements of list_get_comb.
    :return: Generator with the combinations of this list.
    """

    # Generator to get the combinations of the indices of the list
    def get_indices_combinations(sub_list_indices, max_index):
        """ Generator that returns the combinations of the indices

        :param sub_list_indices: Sub-list from which to generate ALL the possible combinations.
        :param max_index: Maximum index.
        :return:
        """
        if len(sub_list_indices) == 1:  # Last index of the list of indices
            for index in range(sub_list_indices[0], max_index + 1):
                yield [index]
        elif all([sub_list_indices[-i - 1] == max_index - i for i in
                  range(len(sub_list_indices))]):  # The current sublist has reached the end
            yield sub_list_indices
        else:
            for comb in get_indices_combinations(sub_list_indices[1:],
                                                 max_index):  # Get all the possible combinations of the sublist sub_list_indices[1:]
                yield [sub_list_indices[0]] + comb
            # Advance one position and check all possible combinations
            new_sub_list = []
            new_sub_list.extend([sub_list_indices[0] + i + 1 for i in range(len(sub_list_indices))])
            for new_comb in get_indices_combinations(new_sub_list, max_index):
                yield new_comb  # Return all the possible combinations of the new list

    # Start the algorithm:
    sub_list_indices = list(range(length_combination))
    for list_indices in get_indices_combinations(sub_list_indices, len(list_get_comb) - 1):
        yield [list_get_comb[i] for i in list_indices]

By calling:

comb = combinations([1, 2, 3, 4], 3) 

You can calculate one by one each of the possible combinations of length 3 by calling next(comb) or by using the generator in a loop: for c in comb:.

The advantage of this code is that, in case the list is very long, there are many possible combinations and you want to get one of all the possible combinations that meets some criteria, you wouldn't need to calculate all the possible combinations and then filter them by that criteria. You can just generate them one by one until you find a combination that meets your criteria. This will be computationaly much more efficient. As well, note that the above code calculates only those combinations of length n, instead of calculating all the possible combinations and then filtering them by length, which makes it more efficient as well.

However, if wanted, you can calculate all the combinations at once by listing them list(comb).