Statistics: Combinations in Python

Is there a math nCr function in python?

The following program calculates nCr in an efficient manner (compared to calculating factorials etc.)

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom  # or / in Python 2

As of Python 3.8, binomial coefficients are available in the standard library as math.comb:

>>> from math import comb
>>> comb(10,3)
120

Statistics: combinations in Python

Updated answer in 2023: Use the math.comb function, which exists since Python 3.8 and has gotten much faster in 3.11.

Old answer: See scipy.special.comb (scipy.misc.comb in older versions of scipy). When exact is False, it uses the gammaln function to obtain good precision without taking much time. In the exact case it returns an arbitrary-precision integer, which might take a long time to compute.

Calculate average value of all sorted array combinations

For each position in the combination, the possible values are a subset of the list starting at the position and up to the last k-p-1 element. e.g. for combinations of 6 in 1..100, position 3 can only contain values 3..96

For each of the positon/value pairs, the number of occurrences will be the product of combinations of left side elements and combinations of right side elements.

For example, for combinations of 6 elements within a list of 1..100, the number of times 45 will appear at the third position is the combinations of 2 in 1..44 times the combinations of 3 in 46..100. So we will have C(44,2) * C(55,3) * 45 for that positon/value pair.

You can repeat this calculation for each positon/value pair to obtain a total for each position in the output combinations. Then divide these totals by the number of combinations to get the expected value:

from math import comb

def countComb(N,k):
    result = [0]*k
    for p in range(k):                 # p is count on the left
        q = k-p-1                      # q is count on the right
        for i in range(p,len(N)-q):
            left  = comb(i,p)          # combinations on the left >= 1
            right = comb(len(N)-i-1,q) # combinations on the right >= 1
            result[p] += left * right * N[i]
    return result
            
def combProb(N,k):
    Cnk = comb(len(N),k)
    return [S/Cnk for S in countComb(N,k)]

Output:

print(countComb([1,2,3],2)) # [4, 8]
print(combProb([1,2,3],2))  # [1.3333333333333333, 2.6666666666666665]

print(countComb([1,2,3,4,5],3)) # [15, 30, 45]
print(combProb([1,2,3,4,5],3))  # [1.5, 3.0, 4.5]

# test with large number of combinations:

print(countComb(list(range(1,301)),7))
[1521500803497675, 3043001606995350, 4564502410493025, 
 6086003213990700, 7607504017488375, 9129004820986050,
 10650505624483725]

print(combProb(list(range(1,301)),7))
[37.625, 75.25, 112.875, 150.5, 188.125, 225.75, 263.375]

Unique combinations of dice

You can use itertools.combinations_with_replacement() in Python:

from itertools import combinations_with_replacement
options = list(range(1, 7))
print(list(combinations_with_replacement(options, 5)))

All possible combinations of elements in a list which are next to each other

You can use a recursive generator function:

stuff = [1, 2, 3, 4]
def get_combos(d, c = []):
   yield tuple(c)
   if d:
      yield from get_combos(d[1:], c+[d[0]])
      yield from get_combos(d[1:], [d[0]])

result = set(filter(None, get_combos(stuff)))

Output:

{(1,), 
 (2,), 
 (3,), 
 (4,), 
 (1, 2), 
 (2, 3), 
 (3, 4), 
 (1, 2, 3), 
 (2, 3, 4), 
 (1, 2, 3, 4)}

All possible combinations of operations on list of numbers to find a specific number

You could use permutations from the itertools module to arrange numbers and operators in all possible ways into a string formula. Then use eval() to compute the result.

For example:

from itertools import permutations
numbers   = ["1","9","8","2"]
target    = 24
operators = ["+","-","*","/"]
for values in permutations(numbers,len(numbers)):
    for oper in permutations(operators,len(numbers)-1):
        formula = "".join(o+v for o,v in zip([""]+list(oper),values))
        if eval(formula) == target: print(formula,"=",target)

[UPDATE1] If you are allowed to use the same operator more than once (as suggested by your comment on 1+1+1*8=24), you will need to use combinations_with_replacement to generate more operator patterns:

from itertools import permutations,combinations_with_replacement
numbers   = ["1","1","1","8"]
target    = 10
operators = ["+","-","*","/"]
seen      = set()
for values in permutations(numbers,len(numbers)):
    for operCombo in combinations_with_replacement(operators,len(numbers)-1):
        for oper in permutations(operCombo,len(numbers)-1):
            formula = "".join(o+v for o,v in zip([""]+list(oper),values))
            if formula not in seen and eval(formula) == target:
                print(formula,"=",target)
                seen.add(formula)

Essentially, this only differs from the previous example by the insertion of the for operCombo in ... loop.

Note: The combinations will generate formulas that look exactly the same so you will want to avoid printing solutions that have already been seen (as I did here). Duplications would also occur in the previous example if any numbers were repeated in the input.

Also note that in order for 9-1+8*2 to result in 24, the multiplication must be performed before additions and subtractions (i.e. under precedence rules) otherwise 9-1+8*2=32. You would need to support parentheses to cover different orders of operation.

[UPDATE2] Supporting parentheses is a bit more involved depending on how many numbers you want to allow. For 4 numbers, there are 11 patterns:

No parentheses: A+B+C+D
A+B group: (A+B)+C+D
B+C group: A+(B+C)+D
C+D group: A+B+(C+D)
A+B and C+D groups: (A+B)+(C+D)
A+B+C group: (A+B+C)+D
B+C+D group: A+(B+C+D)
A+B group + C: ((A+B)+C)+D
A + group B+C: (A+(B+C))+D
B+C group + D: A+((B+C)+D)
B + group C+D: A+(B+(C+D))

If you have more than 4 numbers there will be more patterns of parentheses grouping.

Here's an example (for 4 numbers):

from itertools import permutations,combinations_with_replacement
numbers   = ["9","8","1","2"]
target    = 24
operators = ["+","-","*","/"]
groups    = ['X+X+X+X', 'X+X+(X+X)', 'X+(X+X)+X', '(X+X+X)+X', '(X+X)+X+X', 'X+(X+X+X)', '((X+X)+X)+X', 'X+(X+(X+X))', 'X+((X+X)+X)', '(X+X)+(X+X)', '(X+(X+X))+X']
seen      = set()
for values in permutations(numbers,len(numbers)):
    for operCombo in combinations_with_replacement(operators,len(numbers)-1):
        for oper in permutations(operCombo,len(numbers)-1):
            formulaKey = "".join(oper+values)
            if formulaKey in seen: continue # ignore variations on parentheses alone
            for pattern in groups:
                formula = "".join(o+p for o,p in zip([""]+list(oper), pattern.split("+")))
                formula = "".join(v+p for v,p in zip([""]+list(values),formula.split("X")))
                try:
                    if eval(formula) == target:
                        print(formula,"=",target)
                        seen.add(formulaKey)
                        break 
                except: pass

Groupings could result in divisions by zero, so a try:except block had to be added.

This produces the following result:

9*8/(1+2) = 24
9+8*2-1 = 24
9*8/(2+1) = 24
9-1+8*2 = 24
9-(1-8*2) = 24
9-1+2*8 = 24
(9-1)*2+8 = 24
9/(1+2)*8 = 24
9/((1+2)/8) = 24
9-(1-2*8) = 24
9+2*8-1 = 24
9/(2+1)*8 = 24
9/((2+1)/8) = 24
8+(9-1)*2 = 24
8*9/(1+2) = 24
8*9/(2+1) = 24
8-(1-9)*2 = 24
8/(1+2)*9 = 24
8/((1+2)/9) = 24
8+2*(9-1) = 24
8*2+9-1 = 24
8*2-1+9 = 24
8/(2+1)*9 = 24
8/((2+1)/9) = 24
8-2*(1-9) = 24
8*2-(1-9) = 24
2*(9-1)+8 = 24
2*8+9-1 = 24
2*8-1+9 = 24
2*8-(1-9) = 24

To generate the parentheses grouping patterns for more numbers, you can use this function:

from itertools import product
import re
def groupPatterns(count,pattern=None):
    arr = pattern or "X"*count
    if len(arr) < 2 : return [arr]
    result = []
    for mid in range(1,len(arr)):
        leftPattern  = groupPatterns(count,arr[:mid])
        rightPattern = groupPatterns(count,arr[mid:])
        for left,right in product(leftPattern,rightPattern):
            result += [left + right]
            if len(left)  > 1 : result += ["(" + left + ")" + right]
            if len(right) > 1 : result += [left + "(" + right + ")"]
            if len(left) > 1 and len(right) > 1: 
                result += ["(" + left + ")(" + right + ")"]
    if pattern: return result # recursion
    patterns = [] # final, add "+" between X value placeholders or groups
    for pat in sorted(set(result),key=lambda x:len(x)):
        pat = re.sub("X(?=X)", r"X+",  pat)  # XX --> X+X
        pat = re.sub("X\(",    r"X+(", pat)  # X( --> X+(
        pat = re.sub("\)X",    r")+X", pat)  # )X --> )+X
        pat = re.sub("\)\(",   r")+(", pat)  # )( --> )+(
        patterns.append(pat)
    return patterns

And then replace groups = ["X+X+X+X",... with groups = groupPatterns(len(numbers)) in the previous example.

OR, create a completely generic function for any number of values, with or without grouping and operator reuse:

from itertools import permutations,combinations_with_replacement
def numbersToTarget(numbers,target,reuseOper=True,allowGroups=True,operators=["+","-","*","/"]):   
    groups      = groupPatterns(len(numbers)) if allowGroups else [ "+".join("X"*len(numbers)) ]
    seen        = set()
    for values in permutations(numbers,len(numbers)):
        for operCombo in combinations_with_replacement(operators,len(numbers)-1) if reuseOper else [operators]:
            for opers in permutations(operCombo,len(numbers)-1):
                formulaKey = str(opers)+str(values)
                if formulaKey in seen: continue # ignore variations on parentheses alone
                for pattern in groups:
                    formula = "".join(o+p      for o,p in zip([""]+list(opers), pattern.split("+")))
                    formula = "".join(str(v)+p for v,p in zip([""]+list(values),formula.split("X")))
                    try:
                        if eval(formula) == target:
                            seen.add(formulaKey)
                            yield formula
                            break 
                    except: pass

for formula in numbersToTarget([9,8,1,2],24):
    print("24 =",formula)
for formula in numbersToTarget([9,8,1,2,5],0,allowGroups=False):
    print("0 =",formula)