Get all (n-choose-k) combinations of length n

Question

How can I get all combinations (in order) of length n from a list of numbers? For example, given the list [1, 2, 3, 4], and setting n = 3, how can I get these results?

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

---

_{For combinations of all possible lengths, see Get all possible (2^N) combinations of a list’s elements, of any length . Note that this is not simply a matter of iterating over the possible lengths and combining the results, as there are other reasonable approaches to the problem.}

_{To avoid duplicate outputs when the input has duplicate elements, see Python combinations without repetitions .}

_{Also related: Generate all binary strings of length n with k bits set}

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).

Answer 4

This solution allows selecting only those subsets of the power set of a list or a set whose number of elements fall between a user-defined minimum and maximum. The elements in each subset maintain their original order. To obtain combinations of a specific length n, set both the min and max number of elements to the desired value, n.

    def custom_power_set(s, min_cardinal=0, max_cardinal=None):
        """
        Returns a list of all subsets of a list or a set s 
        where the number of elements is between min_cardinal 
        and max_cardinal.
        """
        # Sets max_cardinal to cardinal of set s by default:
        if max_cardinal is None:
            max_cardinal = len(s)
    
        # In case s is a proper set:
        if type(s) == set:
            s = list(s)
    
        out = [[s[i] for i in range(len(s)) if (1 << i & j)]
               for j in range(1 << len(s))
               # condition re number of elements:
               if bin(j).count('1') in range(min_cardinal, max_cardinal + 1)]
    
        return out

Example:

    custom_power_set(range(4), 3, 3)

produces [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]] as output