ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 06 Aug 2020 13:51:43 +0200Built-in tools for fast extraction of tuples of a given grade with respect to grading on [1, 2, ..., n]https://ask.sagemath.org/question/52440/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](https://stackoverflow.com/q/62864317/2886628).
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,
JulienSun, 12 Jul 2020 19:37:33 +0200https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/Answer by dan_fulea for <p>Hi,</p>
<p>Note that I have just posted <a href="https://stackoverflow.com/q/62864317/2886628">the same question on Stack Overflow</a>.</p>
<p>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.</p>
<p>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).</p>
<p><strong>Remark:</strong> This is a self-motivated question coming from mathematical experimentations with Sage.
Many thanks in advance for your help.</p>
<p><strong>Example:</strong>
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 </p>
<p><code>
[(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)]
</code></p>
<p>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:</p>
<p><code>
from itertools import combinations
n = 6
iterable = list(range(1, n+1))
r = 2
print(list(combinations(iterable, r)))from itertools
</code></p>
<p><strong>Question 0:</strong> Is there anything faster in Python?</p>
<p>Now let me choose a grading on the set S in the form of a function from S to {1, 2, 3}</p>
<p>grading: 1, 2, 3 --> 1 and 4, 5 --> 2 and 6 --> 3</p>
<p>I have decided to store this function as a dictionary as follows:</p>
<p><code>
grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3}
</code></p>
<p>With respect to this grading, we can compute the grade of elements, couples, or tuples constructed from S.</p>
<p>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 </p>
<p>1 - First Construction:</p>
<p>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:</p>
<p><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)
</code></p>
<p>This yields</p>
<p><code>
[(1, 6), (2, 6), (3, 6), (4, 5)]
</code></p>
<p>as desired.</p>
<p><strong>Question 1:</strong> Is there a built-in way to obtain gradedList and/or what is the fastest way to do this with Python?</p>
<p>2 - Second Construction:</p>
<p>Now I want to extract all the increasing 3-tuples (i, j, k) with grade equal to 4, and which starts with i = 1.</p>
<p>In other terms, I want the following list:</p>
<p><code>
[(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)]
</code> </p>
<p>Of course, this can be obtained as follows:</p>
<p><code>
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)
</code></p>
<p><strong>Question 2:</strong> Is there a built-in way to obtain secondGradedList and/or what is the fastest way to do this with Python?</p>
<p>Thanks,
Julien</p>
https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?answer=52888#post-id-52888For 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.
Thu, 06 Aug 2020 11:08:36 +0200https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?answer=52888#post-id-52888Answer by mwageringel for <p>Hi,</p>
<p>Note that I have just posted <a href="https://stackoverflow.com/q/62864317/2886628">the same question on Stack Overflow</a>.</p>
<p>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.</p>
<p>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).</p>
<p><strong>Remark:</strong> This is a self-motivated question coming from mathematical experimentations with Sage.
Many thanks in advance for your help.</p>
<p><strong>Example:</strong>
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 </p>
<p><code>
[(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)]
</code></p>
<p>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:</p>
<p><code>
from itertools import combinations
n = 6
iterable = list(range(1, n+1))
r = 2
print(list(combinations(iterable, r)))from itertools
</code></p>
<p><strong>Question 0:</strong> Is there anything faster in Python?</p>
<p>Now let me choose a grading on the set S in the form of a function from S to {1, 2, 3}</p>
<p>grading: 1, 2, 3 --> 1 and 4, 5 --> 2 and 6 --> 3</p>
<p>I have decided to store this function as a dictionary as follows:</p>
<p><code>
grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3}
</code></p>
<p>With respect to this grading, we can compute the grade of elements, couples, or tuples constructed from S.</p>
<p>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 </p>
<p>1 - First Construction:</p>
<p>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:</p>
<p><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)
</code></p>
<p>This yields</p>
<p><code>
[(1, 6), (2, 6), (3, 6), (4, 5)]
</code></p>
<p>as desired.</p>
<p><strong>Question 1:</strong> Is there a built-in way to obtain gradedList and/or what is the fastest way to do this with Python?</p>
<p>2 - Second Construction:</p>
<p>Now I want to extract all the increasing 3-tuples (i, j, k) with grade equal to 4, and which starts with i = 1.</p>
<p>In other terms, I want the following list:</p>
<p><code>
[(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)]
</code> </p>
<p>Of course, this can be obtained as follows:</p>
<p><code>
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)
</code></p>
<p><strong>Question 2:</strong> Is there a built-in way to obtain secondGradedList and/or what is the fastest way to do this with Python?</p>
<p>Thanks,
Julien</p>
https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?answer=52455#post-id-52455There 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.Mon, 13 Jul 2020 21:38:17 +0200https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?answer=52455#post-id-52455Comment by slelievre for <p>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:</p>
<pre><code>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]]
</code></pre>
<p>This one respects the grading. Though, it does not enumerate subsets, but multisets (subsets with repetition):</p>
<pre><code>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],
...
</code></pre>
<p>In general, you will want to avoid constructing elements of the wrong grade, as early as possible.</p>
https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?comment=52893#post-id-52893I converted @mwageringel's comment to an answer.Thu, 06 Aug 2020 13:51:43 +0200https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?comment=52893#post-id-52893Comment by Boston for <p>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:</p>
<pre><code>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]]
</code></pre>
<p>This one respects the grading. Though, it does not enumerate subsets, but multisets (subsets with repetition):</p>
<pre><code>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],
...
</code></pre>
<p>In general, you will want to avoid constructing elements of the wrong grade, as early as possible.</p>
https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?comment=52500#post-id-52500@mwageringel Thanks a lot :-)Thu, 16 Jul 2020 14:05:28 +0200https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/?comment=52500#post-id-52500