Ask Your Question

How to create lists of n-tuples efficiently?

asked 2021-04-21 19:12:26 +0200

sum8tion gravatar image

updated 2021-04-21 19:18:25 +0200

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):

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.

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2021-04-22 06:02:31 +0200

Max Alekseyev gravatar image

updated 2021-04-22 06:09:19 +0200

Each 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)
edit flag offensive delete link more

answered 2021-04-21 20:52:58 +0200

FrédéricC gravatar image

Look at

sage: IntegerListsLex?
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


Asked: 2021-04-21 19:12:26 +0200

Seen: 459 times

Last updated: Apr 22 '21