# Revision history [back]

### Built-in tools for fast extraction of tuples of a given grade with respect to grading on [1, 2, ..., n]

Hi,

Note that I have just posted the same question on Stack Overflow.

I am in the process of coding 2 mathematical combinatorial operations that I want to iterate (as) many times (as possible), so speed is obviously crucial.

Here is an example of what I want to do as fast and efficiently as possible for any positive integer n and any grading (see example below).

Remark: This is a self-motivated question coming from mathematical experimentations with Sage. Many thanks in advance for your help.

Example: Let us take n = 6, and the set S = {1, 2, ..., n} = {1, 2, 3, 4, 5, 6}. There are binomial(6, 2) = 15 couples

 [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)] 

in increasing order that we can extract from S. The built-in tool I was advised to use in order to obtain the above list is the following:

 from itertools import combinations n = 6 iterable = list(range(1, n+1)) r = 2 print(list(combinations(iterable, r)))from itertools 

Question 0: Is there anything faster in Python?

Now let me choose a grading on the set S in the form of a function from S to {1, 2, 3}

grading: 1, 2, 3 --> 1 and 4, 5 --> 2 and 6 --> 3

I have decided to store this function as a dictionary as follows:

 grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3} 

With respect to this grading, we can compute the grade of elements, couples, or tuples constructed from S.

Examples: - grade(2) = 1 - grade(5) = 2 - grade((2, 5)) = grade(2) + grade(5) = 1 + 2 = 3 - grade((2, 3, 5)) = 1 + 1 + 2 = 5

1 - First Construction:

I want all the couples with grade equal to g0 = 4. Here is an obvious way to do it, which is built naively on the previous lines of code:

 g0 = 4 gradedList = [] for couple in list(combinations(iterable, 2)): grade = grading[couple[0]] + grading[couple[1]] if grade == g0: gradedList.append(couple) print(gradedList) 

This yields

 [(1, 6), (2, 6), (3, 6), (4, 5)] 

as desired.

Question 1: Is there a built-in way to obtain gradedList and/or what is the fastest way to do this with Python?

2 - Second Construction:

Now I want to extract all the increasing 3-tuples (i, j, k) with grade equal to 4, and which starts with i = 1.

In other terms, I want the following list:

 [(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)] 

Of course, this can be obtained as follows:

 newIterable = list(range(2, n+1)) secondGradedList = [] for couple in list(combinations(newIterable, 2)): grade = grading[1] + grading[couple[0]] + grading[couple[1]] if grade == g0: secondGradedList.append((1,) + couple) print(secondGradedList) 

Question 2: Is there a built-in way to obtain secondGradedList and/or what is the fastest way to do this with Python?

Thanks, Julien