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

Answer 1

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
Answer 2

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
Answer 3

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))
READ ALSO
jQuery submit function add data several times

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&#39;s value to show a certain div(a div of radio buttons)?

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?

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

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