//按字典次序生成集合的r子集
//一个有n个不重复元素的集合的r子集按字典次序排列，它的第一个排列是：123...r
//最后一个排列是(n-r+1)...n,从它的第一个排列开始，下一个排列是比当前排列大，
//并且是这些大于当前排列中的最小排列，按此规则直到生成最后一个排列为止。
//算法具体为：
//1)从123...r开始
//2)找到增值位置
//3)增值位置的原有值+1
//4)增值位置的右边的第一个位置的值为增值位置的新值+1，或描述为增值位右边的各位置的值从左到右为其左边相邻位置的值+1。
//这样做的原因是可以得到一个比原排列大并且是最小的一个排列。
//找增值位置的方法：
//2.1)由于是按字典次序，所以增值位应尽可能找权位低的位置，那么就需要从排列的右边向左找
//2.2)由于最后一个排列是(n-r+1)...n,那么表示这个r排列各位上的最大值分别是：(n-r+1)...n.
//那么详细的处理方法是：将r个位置从左向右标注为r,r-1,...1
//r位是最高权位，1是最低权位
//设位置i从位置1开始向r位找增值位，当i位置上的值<这个位置的最大值n-i+1时位置i上的值在原有值上+1,i-1至1位的值为其左边相邻值+1
//当位置i上的值=这个位置的最大值n-i+1时，i向左再移一位，然后再按本规则进行直到找到增值位。
//下面的代码中数组是从0开始，上面的算法是从1开始，另外数组0位置的权位最低，r-1位置权位最高。所以上面的算法需要反向来看。
public class CombinationR
{
public static void main(String[] args)
{
//指定集合的元素个数N,和子集长度r
int N=Integer.parseInt(args[0]);
int r=Integer.parseInt(args[1]);
//使用一个长度为r的一维数组来表示这个排列
int[] a=new int[r];
//初值为123...r
for(int i=0;i<r;i++)
a[i]=r-i;
show(a);
//
int i;
//当前排列不是最后一个排列时就继续生成下一个排列
while(!(a[r-1]==N-r+1 && a[0]==N))
{
//从低位向高位找增值位，
for(i=0;i<=r && a[i]==N-i;i++);
//增位值+1
a[i]++;
//增位右边值=增位值+1
for(i=i;i>0;i--)
a[i-1]=a[i]+1;
show(a);
}
}
//显示这个数组中的值
private static void show(int[] a)
{
for(int i=a.length-1;i>=0;i--)
StdOut.printf("%d",a[i]);
StdOut.println();
}
}