Pseudocode for view the combinations .

Question

Can you help me please with a program which can calculate the number of combinations and to view it ? A pseudocode ? Is there something like a code - to program it ?

thanks :)

Answer 1

Well, I will not provide you with the pseudocode, but instead I will show you how to construct a bijection between the set $\{1,2,\dots,\binom mn\}$ and the set

$$A_{m,n}=\bigl\{(c_1,\dots,c_n)\in\mathbb N^n: 1\leq c_j<c_{j+1}\leq m\ \style{font-family:inherit;}{\text{for}}\ j=1,\dots,n-1\bigr\}\,;$$

I am sure that the method of proof can be easily translated into a pseudocode. In other words, what follows is a pseudopseudocode ;-) .

For $j,r\in\mathbb Z$ define

$$a_j(r)=\binom{m-r}{n-j+1}\,,$$

with the usual convention $\binom pq=0$ if $q<0$ or $p<q$.

Lemma: For each $j$ between $1$ and $n$ we have

$$a_{j\,}(t)=0\ \ \style{font-family:inherit;}{\text{for all}}\ t\geq m-n+j\,;\ 0\leq a_{j\,}(s)<a_{j\,}(s-1)\ \ \style{font-family:inherit;}{\text{for all}}\ \ s\leq m-n+j\,.$$

The proof is left to you.

Proposition: For each $k\in\bigl\{1,2,\dots,\binom mn\bigr\}$ there is a unique tuple $(b_1,\dots,b_n)\in A_{m,n}$ such that, for $1\leq j\leq n\,:$ $$a_{j\,}(b_j)<k-\sum_{i=1}^{j-1}a_i(b_i)\leq a_{j\,}(b_j-1)\,.\quad\boldsymbol{(*)}$$

Proof: If $1\leq j\leq n$, then for each integer $c$ there is at most one integer $s$ such that

$$a_{j\,}(s)<c\leq a_{j\,}(s-1)\,;$$

moreover, such integer $s$ exists if $c>0$, and in that case we will have $s\leq m-n+j$. This argument shows that if $(b_1,\dots,b_n)\in A_{m,n}$ satisfies $\boldsymbol{(*)}$, then each $b_j$ is uniquely determined by $\ k,b_1,b_2,\dots,b_{j-1}$, which settles the unicity.

Now we will show existence: since $k>0$, there is a unique integer $b_1$ such that

$$\color{blue}{a_1(b_1)<k\leq a_1(b_1-1)}\,,$$

and $b_1\leq m-n+1$. In particular $a_1(b_1)<\binom mn=a_1(0)$, so necessarily we have $b_1\geq1$.

Let $\ell$ between $2$ and $n$ and suppose that there are positive integers $b_1<b_2<\cdots<b_{\ell-1}\leq m$ such that $\boldsymbol{(*)}$ holds $j=1,\dots,\ell-1$. Taking $j=\ell-1$ in $\boldsymbol{(*)}$ we get

$$\begin{align*} 0<k-\sum_{i=1}^{\ell-1} a_i(b_i)=&\,\Biggl(k-\sum_{i=1}^{\ell-2}a_i(b_i)\Biggr)-a_{\ell-1}(b_{\ell-1})\\[2mm] \leq&\,a_{\ell-1}(b_{\ell-1}-1)-a_{\ell-1}(b_{\ell-1})\\[2mm] =&\,\binom{m-b_{\ell-1}+1}{n-\ell+2}-\binom{m-b_{\ell-1}}{n-\ell+2}\\[2mm] =&\,\binom{m-b_{\ell-1}}{n-\ell+1}\\[2mm] =&\,a_\ell(b_{\ell-1})\,. \end{align*} $$

Thus, the lemma implies that there is a unique integer $b_\ell$ such that

$$\color{blue}{a_\ell(b_\ell)<k-\sum_{i=1}^{\ell-1}a_i(b_i)\leq a_\ell(b_\ell-1)}$$

and $b_\ell\leq m-n+\ell\leq m$. Moreover, $b_\ell>b_{\ell-1}$ because $a_\ell(b_\ell)<a_\ell(b_{\ell-1})$. This finishes the proof.

I highlighted in blue what you need to implement in a program. I am assuming $m>n>1$ (otherwise the result is trivial).

ADDENDUM

The inverse of the mapping $k\mapsto (b_1,\dots,b_n)$ is given by

$$(b_1,\dots,b_n)\mapsto1+\sum_{i=1}^na_i(b_i)$$

(just believe me, or else try to prove it!).

(ANOTHER) ADDENDUM

Regarding the set $S_n$ of permutations of the set $[n]=\{1,\dots,n\}$, we would like to define a explicit mapping $[n!]\to S_n$. If you write the permutations as $n$-tuples, then exactly $(n-1)!$ of these tuples end with the number $i$, for each $i$ between $1$ and $n$. Let $1\leq k\leq n!$, and let $(b_1,\dots,b_n)$ the permutation associated with $k$. A first approach can be

$$b_n=i,\ \style{font-family:inherit;}{\text{whenever}}\ (i-1)(n-1)!<k\leq i(n-1)!\,.$$

In other words, you are detecting in which $(n-1)!$-block is located your number $k$. Now we concentrate in this subblock of size $(n-1)!$. Ignoring the last entry of these tuples, you actually have all the permutations of the set $\{1,\dots,n\}\setminus\{i\}=\{i_1<i_2<\cdots<i_{n-1}\}\,.$ Now we repeat the reasoning: divide this block into $n-1$ subblocks of size $(n-2)!$, obtaining

$$b_{n-1}=i_\ell,\ \text{whenever}\ (i-1)(n-1)!+(i_\ell-1)(n-2)!<k\leq(i-1)(n-1)!+i_\ell(n-2)!\,.$$

Continuing in this way you can construct explicitly the $k$-th permutation (with respect to the lexicographical order? I am not sure, but at least this was my intention). I barely remember programming stuff, but I think that what you need is to start with an array $a=[1\ 2\ \cdots\ n]$, and removing in each step the element $b_r$ obtained.

Answer 2

To compute all the permutations of a set $X$, you operate recursively:

• If $X$ is empty, $X=\emptyset$, then the set of permutations is $\{\emptyset\}$.
• If $X$ is not empty, then take each element $x\in X$, and adjoin it to the set of permutations of $X$ without the element $x$.

Writing this in Haskell is a straightforward translation of the above algorithm. First we import a function to let us delete elements from a list:

import Data.List (delete)

then the function that compute all permutations is simply:

perms [] = [[]]
perms xs = [ x : ps | x <- xs, ps <- perms (delete x xs) ]

Checking it works:

> perms "abc"
["abc", "acb", "bac", "bca", "cab", "cba"]