Find list of all decreasing sequences of length k?

Question

I'm trying to figure out how to write a function that takes two integers, n and k, and finds all strictly decreasing sequences of length k of integers that are from 0 to n.

For example, allDecreasing(5, 3) returns

[[4,3,2], [4,3,1], [4,3,0], [4,2,1], [4,2,0], [4,1,0], [3,2,1], [3,2,0], [3,1,0], [2,1,0]]

So far, I only have:

function all-decreasing(n, k) {
    if (n > k-1) {
        all-decreasing(n-1, k);
    }
}

It's not much, since I'm not quite sure how to approach the iteration part. Permutation and subset algorithms have always been confusing for me. If anyone could give me an idea on how to get started, it would be greatly appreciated! Thank you.

Choose n integers from the range, sort. To choose each such set exactly once, there are numerous implementations, see [here](http://stackoverflow.com/questions/4504974/how-to-iteratively-generate-k-elements-subsets-from-a-set-of-size-n-in-java) for example. — G. Bach, Nov 05 '14 at 11:02

score 0 · Accepted Answer · answered Nov 05 '14 at 10:56

Delphi version. I hope you'll see the logic

procedure alldecreasing(n, k: Integer; s: string);
var
  i: Integer;
begin
  if k = 0 then
    Output(s)
  else
    for i := n - 1 downto k - 1 do
      alldecreasing(i, k - 1, s + IntToStr(i));
end;

a call:
  alldecreasing(5, 3, '');
gives:
432
431
430
421
420
410
321
320
310
210

score 0 · Answer 2 · answered Nov 05 '14 at 11:51

You should think about the problem like

Problem (5 3) - 5 numbers, 3 true, 2 false

4 3 2 1 0
--------- 
1 1 1 0 0 = 4 3 2 (flip)
1 1 0 1 0 = 4 3 1 (flip)
1 1 0 0 1 = 4 3 0 (flip)(reset 1)
1 0 1 1 0 = 4 2 1 (flip)
1 0 1 0 1 = 4 2 0 (flip)
1 0 0 1 1 = 4 1 0 (flip)(reset 2)
0 1 1 1 0 = 3 2 1 (flip)
0 1 1 0 1 = 3 2 0 (flip)
0 1 0 1 1 = 3 1 0 (flip)
0 0 1 1 1 = 2 1 0 (flip)

Basic operation you need to be able to do is:

find rightmost (1 0), flip (1 0) aka (flip)
if it was not rightmost 1, reset 1's after it aka (reset n)

This would work on ridiculously large sets very efficiently.

Find list of all decreasing sequences of length k?

2 Answers2