/**
  * <PRe>
  * 求m取n的所有組合。
  * m個數分別為0,1,2...m-1.
  * 算法簡述：
  *   二個組合，若僅有元素順序不同，視其為同一個組合。
  *   左位系低位，右位系高位。
  *   按自然的取法取第一個組合(各數位分別是:0,1,2...n-1)，以后的所有組合都經上一個組合變化而來:
  *   從右至左，找到有增量空間的位,將其加1,使高于該位的所有位，均比其左鄰位大1，從而形成新的組合。
  *   若所有位均無增量空間，說明所有組合均已被遍歷。
  *   使用該方法所生成的組合數中：對任意組合int[] c,下標小的數必定小于下標大的數.
  * </pre>
  */
 public class Combination {
  int n, m;
  int[] pre;//previous combination.

  public Combination(int n, int m) {
   this.n = n;
   this.m = m;
  }

  /**
   * 取下一個組合。可避免一次性返回所有的組合(數量巨大，浪費資源)。
   * if return null,所有組合均已取完。
   */
  public int[] next() {
   if (pre == null) {//取第一個組合，以后的所有組合都經上一個組合變化而來。
    pre = new int[n];
    for (int i = 0; i < pre.length; i++) {
     pre[i] = i;
    }
    int[] ret = new int[n];
    System.arraycopy(pre, 0, ret, 0, n);
    return ret;
   }
   int ni = n - 1, maxNi = m - 1;
   while (pre[ni] + 1 > maxNi) {//從右至左，找到有增量空間的位。
    ni--;
    maxNi--;
    if (ni < 0)
     return null;//若未找到，說明了所有的組合均已取完。
   }
   pre[ni]++;
   while (++ni < n) {
    pre[ni] = pre[ni - 1] + 1;
   }
   int[] ret = new int[n];
   System.arraycopy(pre, 0, ret, 0, n);
   return ret;
  }

 }