# 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