/*
 * This file is part of Nuts Framework.
 * Copyright(C) 2009-2012 Nuts Develop Team.
 *
 * Nuts Framework is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License any later version.
 * 
 * Nuts Framework is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Nuts Framework. If not, see <http://www.gnu.org/licenses/>.
 */
package nuts.core.algorithm;

import nuts.core.lang.Strings;

/**
 */
public class Combinater {
	private int[] index;
	private long count;
	
	public Combinater() {
	}
	
	/**
	 * @return the count
	 */
	public long getCount() {
		return count;
	}

	protected boolean handle() {
		System.out.println(count + ": " + Strings.join(index, " "));
		return true;
	}

	/**
	 * C(n, m)
	 * @param n array size
	 * @param m combination number
	 */
	public long count(int n, int m) {
		long count = 1;
		for (int i = n - m + 1; i <= n; i++) {
			count *= i;
		}
		for (int i = 2; i <= m; i++) {
			count /= i;
		}
		return count;
	}
	
	/**
	 * C(n, m)
	 * @param n array size
	 * @param m combination number
	 */
	public long combinate(int n, int m) {
		index = new int[m];
		count = 0;
		_combinate(n, m);
		return count;
	}

	protected boolean _combinate(int n, int m) { 
		for (int i = n; i >= m; i--) {
			index[m - 1] = i - 1;
			if (m > 1) {
				if (!_combinate(i - 1, m - 1)) {
					return false;
				}
			} 
			else {
				count++;
				return handle();
			}
		}
		return true;
	} 
}
