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

63
December 03, 2019, at 01:00 AM

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 < list < list ... < list[len(list)-1]` (Ascending order w/o repeats )

But

`list + 1` doesn't have to be equal to `list` (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]?

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. ``
3. ``
4. ``
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
``````

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

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))
``````
POPULAR ONLINE

#### How to access Unity settings from Java/Android? ### jQuery submit function add data several times

I have this function I use to store items (voucher codes) based on some rules

50 ### How to use a select's value to show a certain div(a div of radio buttons)?

My goal: The user picks selection 1 and the corresponding div will showThe user picks selection 2, the selection 1 div disappears and shows the selection 2's div

73 ### How can I run jQuery function only if user hasn’t scrolled?

I’ve been trying to incorporate an auto scroll function on my website (live here)I want it to scroll to the content 6 seconds after load, but only if the user is on the very top of the page and hasn’t scrolled enough to uncover the #introduction element

65 ### how can get only numbers from the input

I have on keyup and mask for phone numbers, I need to get only digits, not symbols on mask, but it is not working, please let me know my mistake

93