5
$\begingroup$

Given a set of distinct numbers, say, {1, 2, 3, 4, 5, 6}, find all permutations containing 3 numbers. All the permutations have to be in ascending order.

For e.g., some correct permutations would be {1, 2, 3}, {2, 4, 6}, etc. {2, 3, 1} would be incorrect because it is not in ascending order.

How does one go about solving these kinds of questions? Say, instead of choosing 3 numbers, we had to choose 4 or 5, or maybe the given set would be different, what would be the general appraach?

Thanks.

P.S.: You don't just have to tell the number of possible permutations, but also list them.

$\endgroup$
  • $\begingroup$ IF the elements are different, picking lists in ascending order is the same as picking unordered sets. So you are simply asking for combinations en.wikipedia.org/wiki/Combination $\endgroup$ – leonbloy Oct 19 '13 at 18:24
6
$\begingroup$

Since all the numbers in the set are distinct hence the permutations containing 3 numbers in ascending order are: $$^6C_3$$ The reason is that any selection of 3 numbers from the set can be arranged in ascending order in only 1 way.
Hence the permutations containing 4 numbers in ascending order are: $$^6C_4$$ Also the permutations containing 5 numbers in ascending order are: $$^6C_5$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But how will you go about listing all those permutations? $\endgroup$ – J.P. Oct 18 '13 at 17:22
  • $\begingroup$ I think you can do that on your own if you know the total permutations. $\endgroup$ – iajnr Oct 18 '13 at 17:24
  • $\begingroup$ {1,2,3},{1,2,4},{1,2,5} and so on. $\endgroup$ – iajnr Oct 18 '13 at 17:24
4
$\begingroup$

To print a list of all increasing permutations consisting of three elements from the set $\{1,2,3,\ldots,n\},$ use a nested loop:

for i = 1 to n-2 {
  for j = i+1 to n-1 {
    for k = j+1 to n {
      print {i,j,k}
    }
  }
}

For $k$ elements, you could hold the permutation in an array $p$ of length $k:$

for i = 1 to k {p[i] = i};   /* initialize p to {1,2,...,k} */
repeat {
  print p;
  i = k;
  /* find the rightmost incrementable element.  p[i] can't exceed n+i-k. */
  while i > 0 and p[i] == n+i-k {
    i = i - 1
  };
  if i > 0 {    /* if there exists an incrementable element... */
    p[i] = p[i] + 1;     /* increment it */
    for j = i + 1 to k {    /* and set all subsequent elts to their min values */
      p[j] = p[j-1] + 1
    } 
  }
} until i == 0

If the set consists of distinct elements other than $1,\ 2,\ \ldots, n,$ then sort the elements: $a_1< a_2<\ldots< a_n.$ Use the above algorithm, but instead of printing $p,$ print the elements indexed by $p,$ that is $a_{p_1},\ a_{p_2},\ \ldots, a_{p_k}.$

Multisets: If the elements are not distinct, that is, if we are given a multiset rather than a set, then the algorithm above cannot be used as is, since it will produce duplicates. Assume once again that we have sorted the elements: $a_1\le a_2\le\ldots\le a_n.$

Given the multiset $\{3,5,5,5,6,6\},$ for example, we have $a_1=3,$ $a_2=a_3=a_4=5,$ $a_5=a_6=6.$ We would not, for instance, want to print both $a_1a_2a_3a_5$ and $a_1a_2a_4a_6,$ since they are the same thing: $3556.$ The fix for this is to require that if we include two of $a_2,\ a_3,\ a_4,$ we include the two of least index, namely $a_2$ and $a_3,$ rather than $a_2$ and $a_4$ or $a_3$ and $a_4.$ Likewise, if we include one of $a_5,\ a_6,$ we include the one of least index: $a_5$ rather than $a_6.$

To this end, we modify the algorithm above by defining a least increment for each of the $n$ sorted elements of the multiset: $r_1=1,$ $r_2=3,$ $r_3=2,$ $r_4=1,$ $r_5=2,$ $r_6=1.$ The modified algorithm is the following:

/* assume the elements a[1], a[2], ..., a[n] to be sorted in ascending order */
/* compute least increments */
r[n] = 1;
for i = n-1 downto 1 {
  if a[i] == a[i+1] {r[i] = r[i+1] + 1} else {r[i] = 1}
};
/* initialize p to {1,2,...,k} */
for i = 1 to k {p[i] = i};
repeat {
  for j = 1 to k {print a[p[j]]};
  print <newline>;
  i = k;
  /* find the rightmost incrementable element.  p[i] can't exceed n+i-k. */
  while i > 0 and p[i]+r[p[i]] > n+i-k {
    i = i - 1
  };
  if i > 0 {    /* if there exists an incrementable element... */
    p[i] = p[i] + r[p[i]];     /* increment it */
    for j = i + 1 to k {    /* and set all subsequent elts to their min values */
      p[j] = p[j-1] + 1
    } 
  }
} until i == 0
| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

The following algorithm is taken directly from Donald Knuth's The Art of Computer Programming: Pre-Fascicle 2B: A Draft of 7.2.1.2: Generating All Permutations. You say you want your items permuted and listed in increasing order; the more general description of increasing order is called lexicographic order. Here is Knuth's Algorithm L which generates the desired permutations in lexicographic order:

Algorithm L (Lexicographic permutation generation). Given a sequence of $n$ elements $a_1a_2\dots a_n$, initially sorted so that $a_1 \leq a_2 \leq \cdots \leq a_n$, this algoritm generates all permutations of {$a_1,a_2,\dots, a_n$}, visiting them in lexicographic order.

For example, the permutations of {1,2,2,3} are

1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221,

ordered lexicographically. An auxiliary element element $a_0$ is assumed to be present for convenience; $a_0$ must be strictly less than the larget element $a_n$.

L1. [Visit.] Visit the permutation $a_1a_2\dots a_n$.

L2. [Find $j$.] Set $j \leftarrow n - 1$. If $a_j \geq a_{j+1}$, decrease $j$ by 1 repeatedly until $a_j < a_{j+1}$. Terminate the algorithm if $j=0$. (At this point $j$ is the smallest subscript such that we have already visited all permutations beginning with $a_1 \dots a_j$. Therefore the lexicographically next permutation will increase the value of $a_j$.)

L3.[Increase $a_j$.] Set $l \leftarrow n$. If $a_j \geq a_l$, decrease $l$ by 1 repeatedly until $a_j < a_l$. Then interchange $a_j \leftrightarrow a_l$. (Since $a_{j+1} \geq \cdots \geq a_n$, element $a_l$ is the smallest element greater than $a_j$ that can legitimately follow $a_1 \dots a_{j-1}$ in a permutation. Before the interchange we had $a_{j+1} \geq \cdots \geq a_{l-1} \geq a_l > a_j \geq a_{l+1} \geq \cdots \geq a_n$; after the interchange, we have $a_{j+1} \geq \cdots \geq a_{l-1} \geq a_j > a_l \geq a_{l+1} \geq \cdots \geq a_n$.)

L4. [Reverse $a_{j+1} \cdots a_n$.] Set $k \leftarrow j + 1$ and $l \leftarrow n$. Then, if $k<l$, interchange $a_k \leftrightarrow a_l$, set $k \leftarrow k+1$, $l \leftarrow l-1$, and repeat until $k \geq l$. Return to L1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wonderful as this answer is, it seems to answer something different from the question asked in the original post. The poster wanted permutations containing only three of the six elements. Also, the elements in the permutation are supposed to be in ascending order (not the permutations themselves). So the question is really asking for combinations, with the elements of each combination listed in ascending order. Given the title of the post, one could be forgiven for imagining it was going to ask something else. $\endgroup$ – Will Orrick Oct 19 '13 at 16:58
1
$\begingroup$

IMHO you are not asking for permutations but for combinations. If I am right, then the answer given about Knuth's Algorithm L doesn't cover your problem.

Assuming that you are asking indeed for combinations: there are 20 of them and here they come.

 1  1 2 3
 2  1 2 4
 3  1 2 5
 4  1 2 6
 5  1 3 4
 6  1 3 5
 7  1 3 6
 8  1 4 5
 9  1 4 6
10  1 5 6
11  2 3 4
12  2 3 5
13  2 3 6
14  2 4 5
15  2 4 6
16  2 5 6
17  3 4 5
18  3 4 6
19  3 5 6
20  4 5 6
I have software for doing the same in more general cases. The gist of the coding is a nested loop, as follows (in Pascal).

Program loops;
var
  tel, k1, k2, k3 : integer;
begin
  tel := 0;
  for k1 := 1 to 6 do
  begin
    for k2 := k1+1 to 6 do
    begin
      for k3 := k2+1 to 6 do
      begin
        tel := tel + 1;
        Writeln(tel:2,'  ',k1,' ',k2,' ',k3);
      end;
    end;
  end;
end.
The following is the more general (recursive) program as mentioned, with the same output, though.

Program recursie;
procedure combi(n,k : integer); { Combinations k out of n } var t : integer; loper : array of integer;
procedure loops(var tel : integer; diep : integer); { Recursive nested loops } var d : integer;
procedure PRINT; var i : integer; begin Write(tel+1:3,' '); for i := 1 to k do Write(loper[i],' '); Writeln; end;
begin if diep = k then begin PRINT; tel := tel + 1; end else begin for d := loper[diep]+1 to n do begin loper[diep+1] := d; loops(tel,diep+1); end; end; end;
begin t := 0; SetLength(loper,k+1); loper[0] := 0; loops(t,0); end; { procedure test; var k : integer; begin for k := 0 to 6 do begin combi(6,k); Writeln; end; end; } begin combi(6,3); end.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The same algorithm (I think) in more folksy form, to find the next (in lexicographic sense) permutation :

Consider finding the next permutation of the numbers $(1,2,3,4,5,6,7,8)$, following after, as an example, $(2,6,8,7,4,5,3,1)$

Find the right-most adjacent pair of numbers in the current permutation that are in lexicographic order. If no such pair exists, you are already at the last permutation. In this case, that pair is $(4,5)$

EDIT:

Call the first number $A$

Starting with the second number in the pair, find the right-most number that is greater than $A$; it could be the second number in the pair, as in this example. Call this number $B$.

Swap A and B. In this case, we now have $(2,6,8,7,5,4,3,1)$

Finally, take the numbers following B and arrange them in lexicographic order. In this case, we take $(...4,3,1)$, re-arrange to get $(...1,3,4)$, and have as the next permutation $(2,6,8,7,5,1,3,4)$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The comment to Xoque55's answer applies here as well. Also, a comment about your example in relation to Knuth's algorithm: what about a permutation like $(2,6,8,4,7,5,3,1)?$ In this case the rightmost pair in lexicographic order would be $(4,7),$ but Knuth's algorithm would require swapping $4$ and $5$ rather than $4$ and $7$. This gives $(2,6,8,5,7,4,3,1).$ Then everything to the right of $5$ gets reversed: $(2,6,8,5,1,3,4,7).$ $\endgroup$ – Will Orrick Oct 19 '13 at 17:05
  • $\begingroup$ @WillOrrick: Thanks; corrected now, I hope. It would probably be good to check my memory with more than one example... $\endgroup$ – DJohnM Oct 19 '13 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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