Find all permutations in increasing order 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.
 A: 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$$
A: 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.
A: 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

A: 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.

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