回溯实现组合问题

[问题描述]

给定两个自然数n，r（n>r），输出从数I到n中按降序顺序取r个自然数的所有组合。例如，n=5，r=3时，输出的结果是

5 4 3

5 4 2

5 4 1

5 3 2

5 3 1

5 2 1

4 3 2

4 3 1

4 2 1

3 2 1

程序中用a₁，a₂，…a_r表示一个降序排列的r个数的组合，要求a₁≥r。为了能够穷举出全部降序排列的r个数的组合，按递减顺序调整前一个组合的部分元素生成下一个组合。调整时，当a_r=1就要回溯；另外，调整或回溯后，a_i+i≤r时，也要回溯。上例中由回溯生成下一个组合的情况，有541→532，531→521，521→432（二次回溯），431→421，421→321（二次回溯）。

上述的生成过程，当a₁=r-1时结束。

program ex002;
 var
  n,r,i,j,s:integer;
  a:array[1..20] of integer;
 begin
   writeln('N','R');
   REPEAT
    read(n,r)
   UNTIL n>r;
   i:=1;
   a[1]:=n;
   writeln('RESULT:');
   REPEAT
    if i<>r
           then if a[i]+i>r   
                   then begin
                          a[i+1]:=a[i]-1;
                          i:=i+1;
                        end
                   else begin //回溯
                            dec(i);
                            a[i]:=a[i]-1;    
                        end
    else begin
           for j:=1 to r do write(a[j]:3);
           writeln;inc(s);
           if a[r]=1 //回溯
           then begin
                    dec(i);a[i]:=a[i]-1;
                end
           else dec(a[i]);
         end
   UNTIL a[1]<r;   
writeln(s);   
 end.