字符串的组合（C（m,n））

题目：有A,B,C,D,E 5个字母，从其中任选3个，要求列出所有可能的组合

 

大家一定还记得高中的时候学过的组合C（m,n）算法吧。。那么我们就用这个算法来做这道题吧。

 

其实做出这道题有俩种方法，一种是递归的。比较容易一点。另外一种是非递归的。

 

递归的代码如下：

 

/*
 * 主要是利用递归来来实现。主要思想是把一个字符串分为俩段来处理，首先取出第一个字符串，然后用后面的字符来与它进行拼凑。
 */
import java.util.Scanner;

public class Zuhe {
	private static String str = "ABCDE";// 字符串
	private static int n = 3;// 选择的个数
	private static int count = 0;//组合的个数

	public static void main(String[] args) {
		new Zuhe();
	}

	Zuhe() {
		Scanner input = new Scanner(System.in);
		System.out.println("请输入要选择的个数（要少于" + str.length() + "个）");
		n = Integer.parseInt(input.nextLine());

		find("", 0);
		System.out.println("共有"+count+"种组合");

	}
/*
 *第一个参数是代表第一个字符，第二个参数代表开始寻找点的位置
 */
	public static void find(String s, int i) {
		// 保存上一次的字符串
		String temp = s;
		//判断是否符合要求
		if (s.length() == n) {
			count++;

			System.out.print(s + " ");
			if (count % 10 == 0)
				System.out.println();
			return;
		}
		//从寻找点开始循环，
		for (int k =i; k < str.length(); k++) {
			s = temp;
			s += str.charAt(k);
			find(s, k+1);
		}

	}

}

 

 非递归的代码如下：

/*
 * 采用了图的广度优先算法。也可以说利用队列来实现。先进先出。首先取出第一个字母。然后入队、。
 * 开始循环，出队。循环的结束条件的只要队列还有元素就就循环没有结束。进入循环之后，先判断元素是否符合
 * 要求，如果符合就输出。如果不符合，就给它追加一个字母，开始点是由它的最后一个字符来决定。
 * 比如说：是A就从0开始，是B就从1开始。（这里是难点。）一直找到字符串的末尾。找完之后就
 * 去除取出来的这个元素。以此类推。。。
 */
import java.util.ArrayList;
import java.util.Scanner;

public class Zuhe {
	public static void main(String[] args) {
		String str = "ABCDE";// 字符串
		int n = 2;// 选择的个数
		int count = 0;// 组合的总数
		Scanner input = new Scanner(System.in);
		System.out.println("请输入要选择的个数（要少于" + str.length() + "个）");
		n = Integer.parseInt(input.nextLine());
		ArrayList<String> arr = new ArrayList<String>();//模拟队列
		for (int k = 0; k < str.length(); k++) {
			//取出首节点
			String s = str.charAt(k) + "";
			//入队
			arr.add(s);
			//开始循环
			while (arr.size() > 0) {
				//出队
				String ss = arr.get(0);
				//判断是否符合要求
				if (ss.length() == n) {
					System.out.print(ss + "  ");
					count++;
					if (count % 10 == 0)
						System.out.println();
				}
				//追加字符。
				for (int i = str.indexOf(ss.charAt(ss.length() - 1))+1; i < str.length(); i++) { 					if (ss.length() < n) {
						String m = ss + str.charAt(i);
						arr.add(m);
					}				
				}
				//去除取出来的节点。
				arr.remove(0);
			}
		}
		System.out.println("共有" + count + "种组合");
	}

}

 结果的输出效果：

请输入要选择的个数（要少于5个）
3
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
共有10种组合