Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Combinations of what? Any further restrictions? What do you want to see? –  vonbrand Feb 13 '13 at 12:15
    
$\binom{n}{k}$ , permutations. all kind . I am interested if I have for example $10$ numbers to find a code which can view all the permutations. thanks –  Iuli Feb 13 '13 at 12:19
1  
Perhaps the simplest algorithm is to just run through all options for the first element, and recursively append to each all the permutations of the rest. –  vonbrand Feb 13 '13 at 12:25
    
can you help, can you indicate me a link, something like this ? thanks ! –  Iuli Feb 13 '13 at 12:26
    
Search for "generating permutations"... –  vonbrand Feb 13 '13 at 12:38

2 Answers 2

up vote 2 down vote accepted

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\ \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\ \ \text{for all}\ t\geq m-n+j\,;\ 0\leq a_{j\,}(s)<a_{j\,}(s-1)\ \ \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,\ \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.

share|improve this answer

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"]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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