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
