Ask Your Question
0

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

asked 2020-07-12 12:37:33 -0500

Boston gravatar image

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

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
0

answered 2020-07-13 14:38:17 -0500

mwageringel gravatar image

updated 2020-07-13 14:38:51 -0500

There are two functions in Sage which are similar, but do not do exactly what you need. The implementations might provide useful ideas though. This one does not respect the grading, but otherwise solves the second problem. It is implemented in Cython, so is probably quite fast:

sage: IntegerListsLex(n=9, length=3, min_slope=1, min_part=1, max_part=6).list()
[[2, 3, 4], [1, 3, 5], [1, 2, 6]]

This one respects the grading. Though, it does not enumerate subsets, but multisets (subsets with repetition):

sage: WeightedIntegerVectors(4, (1,1,1,2,2,3)).list()
[[0, 0, 1, 0, 0, 1],
 [0, 1, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 1],
 [0, 0, 0, 0, 2, 0],
 ...

In general, you will want to avoid constructing elements of the wrong grade, as early as possible.

edit flag offensive delete link more

Comments

@mwageringel Thanks a lot :-)

Boston gravatar imageBoston ( 2020-07-16 07:05:28 -0500 )edit

I converted @mwageringel's comment to an answer.

slelievre gravatar imageslelievre ( 2020-08-06 06:51:43 -0500 )edit
0

answered 2020-08-06 04:08:36 -0500

dan_fulea gravatar image

For decent values of $n$ one can try the following:

N = 6
S = [1..N]
grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3}

# Question 0
S2 = Combinations(S,2) 
S2_list = S2.list()
# Alternatively:
S2_list = [(j, k) for j in [1..N] for k in [j+1..N]]

# Question 1
g0 = 4
S2_list_in_deg_g0 = [(j, k) for j in [1..N] for k in [j+1..N] if grading[j] + grading[k] == g0]

# Question 2 :: same game
S3_list_in_deg_g0 = \
    [(j, k, n) for j in [1..N] for k in [j+1..N] for n in [k+1..N] 
     if grading[j] + grading[k] + grading[n] == g0]

S3_list_in_deg_g0_starting_with_one = \
    [(1, k, n) for k in [2..N] for n in [k+1..N] 
     if 1 + grading[k] + grading[n] == g0]

This is slow, since the python loops are slow, but should work good enough for values of $N$ up to $10000$ say. But i wonder if this lists are really needed as lists, to be stored on the HD as such. Instead, if the lists are an intermediate step, iterables may be better. (But python loops are still to slow.) To build the last as an iterable...

S3_iterable_in_deg_g0_starting_with_one = \
    ((1, k, n) for k in [2..N] for n in [k+1..N] 
     if 1 + grading[k] + grading[n] == g0)

For instance, consuming the iterable:

sage: S3_iterable_in_deg_g0_starting_with_one = \ 
....:     ((1, k, n) for k in [2..N] for n in [k+1..N]  
....:      if 1 + grading[k] + grading[n] == g0) 
....:                                                                                                                                                                           
sage: S3_iterable_in_deg_g0_starting_with_one                                                                                                                                   
<generator object <genexpr> at 0x7f5f920eba50>
sage: for triple in S3_iterable_in_deg_g0_starting_with_one: 
....:     print(triple) 
....:                                                                                                                                                                           
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)

The above solutions are using list comprehension. If the above is slow for the needed purpose, than to improve consider the following ideas:

  • I suppose that $N$ may be bigger $10^6$, but the "grading(s)" have a small range. In our case, the values of the gradings / weights dictionary, taken as a set, is {1,2,3}. Suppose this list is relatively small. (Less than $10^5$.) Then build all tuples of two weights which sum up to g0. Then define the iterable by passing through the weights first.

For instance:

weights = list(set(grading.values()))
weights2 = [(u, v) for u in weights for v in weights if u <= v if u + v == g0]

S2_iterable_in_deg_g0 = \
        ((j, k) for (u, v) in weights2 for j in [1..N-1] for k in [j+1..N] 
         if grading[j] == u and grading[k] == v)

# consume it via...
for tup in S2_iterable_in_deg_g0:
    print(tup)

(The above can be done better...)

  • Use numpy for vectorialization.
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-07-12 12:37:33 -0500

Seen: 101 times

Last updated: Aug 06