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, 22 Apr 2021 06:02:31 +0200How to create lists of n-tuples efficiently?https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/The ultimate problem I'm trying to solve, is that given two integers *p* and *q*, I would like to create a list (say "*List1*"), whose entries are (all of the) lists of length *2q* which:
1) For all *L* in *List1*, the first *q* entries are between 0 and *pq-1* (inclusive), and the next *q* entries are between *pq* and *2pq-1* (inclusive)
2) For all *L* in *List1*, the entries are strictly increasing, that is for all *1<=i<=2pq*, *L[i] < L[i+1]*
I have a way of doing this which is very "brute force", where I first construct the list of lists of length 1, then the list of lists of length 2, etc.
I'm imagining (hoping) there exists some way for me to just iterate over all *2q* -tuples (without repetition) of numbers from 1 to *2pq* Something along the lines of
List1 = []
for x in 2q-tuples of [0, 1, 2, ..., 2pq-1]:
if x satisfies 1) and 2):
List1.append(x)
I suppose I would want to convert x to a list before appending to List1, or many there's some way to iterate over lists instead of tuples. That's not so important, I just want an efficient way to construct these lists.Wed, 21 Apr 2021 19:12:26 +0200https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/Answer by Max Alekseyev for <p>The ultimate problem I'm trying to solve, is that given two integers <em>p</em> and <em>q</em>, I would like to create a list (say "<em>List1</em>"), whose entries are (all of the) lists of length <em>2q</em> which:</p>
<p>1) For all <em>L</em> in <em>List1</em>, the first <em>q</em> entries are between 0 and <em>pq-1</em> (inclusive), and the next <em>q</em> entries are between <em>pq</em> and <em>2pq-1</em> (inclusive)</p>
<p>2) For all <em>L</em> in <em>List1</em>, the entries are strictly increasing, that is for all <em>1<=i<=2pq</em>, <em>L[i] < L[i+1]</em></p>
<p>I have a way of doing this which is very "brute force", where I first construct the list of lists of length 1, then the list of lists of length 2, etc. <br>
I'm imagining (hoping) there exists some way for me to just iterate over all <em>2q</em> -tuples (without repetition) of numbers from 1 to <em>2pq</em> Something along the lines of </p>
<pre><code>List1 = []
for x in 2q-tuples of [0, 1, 2, ..., 2pq-1]:
if x satisfies 1) and 2):
List1.append(x)
</code></pre>
<p>I suppose I would want to convert x to a list before appending to List1, or many there's some way to iterate over lists instead of tuples. That's not so important, I just want an efficient way to construct these lists.</p>
https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/?answer=56761#post-id-56761Each half of `x` can be viewed as a subset of size `q` of the corresponding set: `{0,1,...,pq-1}` and `{pq,pq+1,...,2pq-1}`, respectively. This gives raise to the following code:
for x1 in Subsets(range(p*q),q):
for x2 in Subsets(range(p*q,2*p*q),q):
x = sorted(x1|x2)
List1.append(x)Thu, 22 Apr 2021 06:02:31 +0200https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/?answer=56761#post-id-56761Answer by FrédéricC for <p>The ultimate problem I'm trying to solve, is that given two integers <em>p</em> and <em>q</em>, I would like to create a list (say "<em>List1</em>"), whose entries are (all of the) lists of length <em>2q</em> which:</p>
<p>1) For all <em>L</em> in <em>List1</em>, the first <em>q</em> entries are between 0 and <em>pq-1</em> (inclusive), and the next <em>q</em> entries are between <em>pq</em> and <em>2pq-1</em> (inclusive)</p>
<p>2) For all <em>L</em> in <em>List1</em>, the entries are strictly increasing, that is for all <em>1<=i<=2pq</em>, <em>L[i] < L[i+1]</em></p>
<p>I have a way of doing this which is very "brute force", where I first construct the list of lists of length 1, then the list of lists of length 2, etc. <br>
I'm imagining (hoping) there exists some way for me to just iterate over all <em>2q</em> -tuples (without repetition) of numbers from 1 to <em>2pq</em> Something along the lines of </p>
<pre><code>List1 = []
for x in 2q-tuples of [0, 1, 2, ..., 2pq-1]:
if x satisfies 1) and 2):
List1.append(x)
</code></pre>
<p>I suppose I would want to convert x to a list before appending to List1, or many there's some way to iterate over lists instead of tuples. That's not so important, I just want an efficient way to construct these lists.</p>
https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/?answer=56759#post-id-56759Look at
sage: IntegerListsLex?Wed, 21 Apr 2021 20:52:58 +0200https://ask.sagemath.org/question/56756/how-to-create-lists-of-n-tuples-efficiently/?answer=56759#post-id-56759