CODEWITHSUNDEEP
pythonpython-3.xpermutation
Random Channel
Random Channel

Reputation: 1164

Function to find number of 'ordered combinations' with no particular length of a list Python

While variants of this question have been asked numerous times on this site, I haven't found any information on how to do 'ordered combinations' with a given list.

First of all, I don't exactly know what the correct term for this function is, but I will use this list:

list = [1,2,3,4,5,6,7,8,9,10]

What I want to find is how many possible ways this list can be ordered, so that

list[0] < list[1] < list[2] ... < list[len(list)-1] (Ascending order w/o repeats )

But

list[0] + 1 doesn't have to be equal to list[1] (Doesn't matter which numbers are chosen, so long that they are in ascending order and are in the list)

And, assuming outList is a qualifying list sourced from list

len(outList) doesn't have to be to len(list) - 'Qualifying' lists do not have to be the same length of the given list, but it must not be longer.

Some examples of what would fit under these rules:

[1,4,5,9] [2,6,7,8,9] [1,2,4,8] [8,10]

Some non-examples:

[1,3,2,5,10] [1,1,10] [5,2,8,7,9]

Numbers CANNOT repeat, and they must strictly be larger than the previous number.

How would I go about making such a function? I haven't a clue at how to approach such a problem. I tried using a for loop, but I couldn't seem to get that to work properly.

Edit: sorry this question was unclear, and if it still is, because I really don't know what term I would use. I didn't know how to phrase it correctly, so I added some more detail, and my version of the answer is down below. Clearly it is not optimized. Btw AlexanderCécile, if you look at my history, I used to do js and jQuery (not that I don't anymore, but I changed my focus), so the function follows the naming standards of js.

Second edit: All these answers are quite different from each other, which shows the beauty of coding :) - My solution is quite basic, although it does work. Do these work quicker on higher length lists, such as [1,2,3,4...100,101]?

Upvotes: 0

Views: 774

Answers (3)

James Mchugh
James Mchugh

Reputation: 1014

You can do this mathematically using the formula to calculate the number of combinations.

import math
def binomial_coeff(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

def num_all_combinations(lst_len):
    return sum(binomial_coeff(lst_len, i) for i in range(lst_len))

list1 = list(range(10))
print(num_all_combinations(len(list1))) # prints 1023

The binomial_coeff function uses the combinations formula (also known as the binomial coefficient) to get the number of combinations for a list of size n with groups of size k. We then use the num_all_combinations function to get the number of combinations for all group sizes and add them together.

You can even simplify this further using the sums of binomial coefficients identity as suggested by @kaya3. This would result in the following code:

list1 = list(range(10))
print(2**len(list1) - 1) # prints 1023

Upvotes: 1

kaya3
kaya3

Reputation: 51132

As I understand your question, you want to know how many different lists there are with some subset of the elements as lst, kept in order. Since each subset can only exist in one order, the answer is simply the number of subsets: 2^n where n is the length of the list.

def count_subsets(lst):
    return 2 ** len(lst)

For example, if the list is [1, 2, 3] then there are 2^3 = 8 ordered sublists:

  1. []
  2. [1]
  3. [2]
  4. [3]
  5. [1, 2]
  6. [1, 3]
  7. [2, 3]
  8. [1, 2, 3]

If you want to exclude the empty list and/or the original list, you can simply do 2 ** len(lst) - 1 or max(0, 2 ** len(lst) - 2), as appropriate. The max(0, ...) handles the special case when your input list is empty.

The above handles the case like your example when the elements of the input list are all distinct. If there may be repeated elements, then the formula above overcounts. To fix it, we can use a Counter to find the number of copies of each element. If there are k copies of some element, then instead of 2 ** k combinations, we should count k + 1 sublists containing 0, 1, 2, ..., k copies.

from collections import Counter

def count_subsets(lst):
    r = 1
    for k in Counter(lst).values():
        r *= k + 1
    return r

Upvotes: 3

Random Channel
Random Channel

Reputation: 1164

This solution is most likely unoptimized, but I somehow figured out what I wanted to do. Is there a nice way to improve this?

def orderedCombinations():
    z = 0
    for x in range(len(list1)):
        comb = combinations(list1, x)
        for i in list(comb):
            z += 1
    print(str(z))

Upvotes: 0

Related Questions