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}

Operant

If having [1,2,3] means you don't want [2,1,3], what you are describing are combinations, not permutations. – Clinquant

Kind of, but not exactly. In my case if I already have [1,2,3] then [1,3,2],[2,1,3],[2,3,1], [3,1,2], and [3,2,1] are of no use to me. @Clinquant sorry, I didn't know the difference. :S – Operant

I haven't been able to hunt down an exact duplicate of this question, where the OP wants all combinations of a specific length. The other combination questions I can find all ask for a way of generating the full power set, interestingly. Until such a question is found (which may exist), I'm going to say this isn't a dupe. – Quamash

@J.F.Sebastian I strongly disagree with that being a duplicate. That question imposes the additional restriction of using recursion, and the answer here does not appear on that question. – Quamash

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)

Phillie

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]]

Fewer

by far the most readable, clean, elegant solution I've found so far. Kudos! This answer should rank higher. – Mablemabry

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

Maidenhead

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

Custombuilt

Answer 5

Adding to the excellent answers, for the case that you'd like to know the amount of combinations before you actually start working on them. This might be helpful, if your code dynamically yields values for n and k which may give you too many combinations to handle or if you want to estimate the run time, dynamically manage resources and so on.

For instance (400-choose-22) = 869220235645633221187116908079236800. That could be a tad much and you might want to handle such situation differently from say (4-choose-2).

To calculate the amount, the best way is to use math modules comb function:

>>> import math
>>> n = 400
>>> k = 22
>>> math.comb(n,k)
869220235645633221187116908079236800
# let's not start calculations that won't finish before the sun blows up

The reason to use this over the following naive approach:

>>> math.factorial(n)/math.factorial(k)*math.factorial(n-k)
# ...
OverflowError: integer division result too large for a float

is that the former uses the same factorial-reduction that you'd use if calculating manually. So while the naive method already fails to report the amount for (400-choose-22), math.comb(n,k) calculates super fast, until it reaches its limit given for integer string conversion. This limit can be changed, but for very large values of n and k it might be more reasonable to check whether min(n/(n-k), n/k) is close enough to 1 to be an amount of combinations you want your program to deal with.

Fabri