`
fx05062219
  • 浏览: 19800 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

从m中选择n个元素

    博客分类:
  • java
阅读更多
import java.util.ArrayList;
import java.util.List;

public class PickingATeam {

	public static void main(String[] args) {
		PickingATeam pick = new PickingATeam();
		List<String> ls = new ArrayList<String>();
		ls.add("A");
		ls.add("B");
		ls.add("C");
		ls.add("D");
		// ls.add("E");
		// ls.add("F");
		// ls.add("G");
		// ls.add("H");
		// ls.add("I");
		// ls.add("J");

		String[] s = ls.toArray(new String[4]);

		s = pick.pick(s, 0, ls.size(), 4);
		for (int i = 0; i < s.length; i++) {
			System.out.println(s[i]);
		}
	}

	public String[] pick(String[] ls, int start, int end, int teamNum) {

		// if the number you found is smaller than 0 ,it is invalid.
		// if the number you found is bigger than the length of collection.
		// invalidate!
		if (teamNum < 1 || teamNum > (end - start)) {
			return new String[0];
		}
		// if teamNum is 1, all the elements will be returned.
		if (teamNum == 1) {
			String[] candidate = new String[end - start];
			for (int i = 0; i < candidate.length; i++) {
				candidate[i] = ls[start + i];
			}
			return candidate;
		}
		// (n, k) = (n – 1, k – 1) + (n – 1, k);

		// in the first part, only n-1 elements will be used. the n element will
		// combin will the (n – 1, k – 1)result.

		// this is that n element which is not included when picking the team.
		String FirstElem = ls[start];
		// getting (n-1,k-1);and combin with element n;
		String[] firPart = combin(FirstElem,
				pick(ls, start + 1, end, teamNum - 1));

		// getting (n – 1, k);
		String[] secondPart = pick(ls, start + 1, end, teamNum);

		// code below are used to merge the result.
		int fristPartLength = firPart.length;
		int secondPartLength = secondPart.length;

		String[] pickingResult = new String[fristPartLength + secondPartLength];

		for (int i = 0; i < fristPartLength + secondPartLength; i++) {
			if (i < fristPartLength) {
				pickingResult[i] = firPart[i];
			} else {
				pickingResult[i] = secondPart[i - fristPartLength];
			}

		}

		return pickingResult;
	}

	/**
	 * combin(a,[b,c,d]); return[ab,ac,ad]
	 * */

	private String[] combin(String elem, String[] all) {
		String[] local = new String[all.length];
		for (int i = 0; i < all.length; i++) {
			local[i] = all[i];
		}
		for (int i = 0; i < local.length; i++) {
			local[i] = elem + local[i];
		}
		return local;
	}

}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics