I have the following question:

Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$.

I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with $x\in [a..b]$ and $y \in [c..d]$.

Now, I have a new list, let's call it list_1. It consists of elements indexed by the $(x,y)$.

For example, let a=3, b=4, c=7, d=8.

Then my programm produces list=[[3,7],[3,8],[4,7],[4,8]].

Now, my list_1 is [M_{3,7},M_{3,8},M_{4,7},M_{4,8}].

I would like to have a new list, call it list_2, which has exactly the following entries.

list_2 shall contain all $r$-tuples (for $r\in\{1,...,m\}$; $m$ is the size of list_1) with the form

$(M_{i_1},...,M_{i_r})$, such that $i_j$ is an entry of list, that comes before $i_k$ for all $j<k$.

For example, $i_j=[3,8]$ comes before $i_k=[4,7]$.

In our example, list_2 looks like this:

$(M_{3,7}),(M_{3,8}),(M_{4,7}),(M_{4,8}), (M_{3,7},M_{3,8}),(M_{3,7},M_{4,7}),(M_{3,7},M_{4,8}),(M_{3,8},M_{4,7}),(M_{3,8},M_{4,8}),(M_{4,7},M_{4,8}), (M_{3,7},M_{3,8},M_{4,7}),(M_{3,7},M_{3,8},M_{4,8}),(M_{3,7},M_{4,7},M_{4,8}),(M_{3,8},M_{4,7},M_{4,8}),(M_{3,7},M_{3,8},M_{4,7},M_{4,8})$.

I would like to have this in general for arbitrary natural numbers $a,b,c,d$ with $a \leq b$ and $c\leq d$.

I would be very grateful, if somebody was able to send me a pseudo-code.

Thanks for the help!

  • 2
    $\begingroup$ Please do not post the same problem on multiple sites. $\endgroup$ – G. Bach Aug 8 '14 at 12:41
  • $\begingroup$ What do you need this for? Is it an exercise? $\endgroup$ – Yuval Filmus Aug 8 '14 at 14:36
  • 1
    $\begingroup$ This is a programming question, isn't it? (I don't see a conceptual problem going from what you have to what you want.) $\endgroup$ – Raphael Aug 8 '14 at 14:46
  • $\begingroup$ @Raphael There is a (very standard) algorithmic question here: generating all $k$-tuples. $\endgroup$ – Yuval Filmus Aug 8 '14 at 14:59

There are many ways to compute all $k$-tuples of elements in a given list $L$. One way is to use recursion and the analogue of Pascal's identity $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. $$ We can interpret this identity as follows. Write $L=x, L'$, where $x$ is the first element and $L'$ is the rest of the list. A $k$-tuple of $L$ is either a $k$-tuple of $L'$, or $x$ along with a $k-1$-tuple of $L'$. I'll let you figure out how to turn this into a solution for your problem.

Using the same idea, you can also write a function that given $m$ outputs the $m$th $k$-tuple of $L$, in lexicographic order. You can even decode such a tuple back to its index in this order.

If you don't like recursion, you can also try an iterative approach. The idea is to start with the tuple $0,1,\ldots, k-1$, and keep incrementing the tuple. To increment the tuple, start by incrementing the last position. If it's now $n$, we backtrack and increment the previous position. If that one is now $n-1$, we backtrack once more, and so on. Eventually, unless we were at the last tuple, we well have incremented some position successfully, say to the value $m$. The following position (if any) we set to $m+1$, the one after it (if any) to $m+2$, and so on. I'll let you figure out how to implement this idea.

Both approaches can be implemented so that they produce the same, lexicographic, order. There are probably other, trickier approaches, that rely on applying an intricate sequence of transpositions on the list $0,1,\ldots, n-1$, but the ones I described are general approaches applicable in many other situations. For the more magical ones, check Knuth's new volumes-in-preparation of TAOCP.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.