0

Say there is a list [1,2,3,4,5], I would need to get the count of all possible combinations of the elements (or 'sub-lists'), e.g. 1, 2, 3, 4, 5, 12, 13, 14, ..., 123, 124, ..., 12345.

I know how to get nCr, the count of combinations of r elements of a list with total n elements.
Python 3.8 or above:

from math import comb
p, r = 5, 2
print(comb(p, r))

Then I could do nC1 + nC2 +...+ nCn. But is there a better/faster way?

p, result = 5, 0
for r in range(1, 6):
    result += comb(p, r)
print(result)

Would appreciate your answers.

nov05
  • 151
  • 2
  • 11

2 Answers2

3

This concept is called a power set in mathematics, and it refers to all subsets of a given set. Your question refers to the size of the power set which is 2^n where n is the size of your original set. This total includes the empty set, so as C4stor said, your total would be 2^n - 1.

The above answer works if the input has all unique elements. If there are repeated elements then take the product of (count + 1) of every element, and again subtract one at the end to remove the empty set.

E.g. [1,1,1,2,2,3]: our counts are 3, 2, 1, so our answer is 4 * 3 * 2 - 1 = 23.

The idea is that for each element, you can have anywhere from 0 up to count(element) in your sublists.

Dave
  • 7,460
  • 3
  • 26
  • 39
jprebys
  • 2,469
  • 1
  • 11
  • 16
  • 2
    This answer is assuming unique elements. If there's repetition it's incorrect. – Edward Peters Nov 23 '22 at 16:24
  • 3
    The OP does not provide any rules, just an example dataset, so I take the half-full-cup side : OP should have given more specific instructions :=) – LoneWanderer Nov 23 '22 at 16:26
  • Thanks. (2^n-1) should be enough. If there are duplicate elements, I could simply use set() to get the unique ones then the power set count. – nov05 Nov 23 '22 at 16:44
  • @Nov05 You know your use case better than we do, but combinations can still have repeated elements - `[1,1]` is, in general, a valid length-2 combination of `[1,1,1]` – Edward Peters Nov 23 '22 at 16:53
  • 1
    @EdwardPeters You could give an answer for 2 cases, one for the case of unique elements, the other for the case of duplicate elements. But thanks all the same! – nov05 Nov 23 '22 at 16:56
0

This specific sum is equal to 2^n -1 :-)

C4stor
  • 8,355
  • 6
  • 29
  • 47
  • 1
    While this is true, a little bit of context would be needed (probably linked to binomial coefficents in some way) see @jprebys answer – LoneWanderer Nov 23 '22 at 16:23
  • 1
    This is only true for unique elements. If there's repetition it's more complicated. – Edward Peters Nov 23 '22 at 16:26
  • Right. Thanks. Is there a term for this num? https://stats.stackexchange.com/questions/27266/simplify-sum-of-combinations-with-same-n-all-possible-values-of-k – nov05 Nov 23 '22 at 16:34
  • OP's question is sufficiently detailed for context. – C4stor Nov 24 '22 at 11:07