使用二进制替代解决全排列问题 博客分类： java算法 算法全排列字符串二进制

//从键盘读入一个由字母构成的串（不大于30个字符）。
//
//从该串中取出3个不重复的字符，求所有的取法。
//
//取出的字符，要求按字母升序排列成一个串。
//
//不同的取法输出顺序可以不考虑。
//
//例如：
//输入：
//abc
//则输出：
//abc
//
//输入：
//abcd
//则输出：
//abc
//abd
//acd
//bcd
//
//输入：
//abcaa
//则输出：
//abc

/*
* 首先去掉用户输入的重复的 ， 然后就是对剩下的字符进行排列
*
* */

package 高职2011决赛真题;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Title3 {

	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		String a = input.nextLine();

		/*  获取新得到的字符  */
		String newX = repair(a);

		/* 对剩下的字符进行排列 */
		range(newX);
		
		/* 进行数据显示 */
		print(newX, range(newX));
	}

	/*  去掉重复的   */
	public static String repair(String a){
		String x = "";

		for(int i=0;i<a.length();i++){
			String temp = String.valueOf(a.charAt(i));

			if(!x.contains(temp)){
				x = x+temp;
			}
		}

		return x;
	}

	/* 对字符串进行取字符 ， range */
	public static ArrayList<String> range(String x){
		//	a	d	b	c	s	e
		//	1	1	1	0	0	0
		//	1	1	1	1	1	1
		//  1 0 表示提取与不提取，

		ArrayList<String> list = new ArrayList<String>();
		for(int i=0;i<=Math.pow(2, x.length());i++){
			BigInteger a = BigInteger.valueOf((long)i);

			String newX = a.toString(2);

			int count = 0;
			for(int j=0;j<newX.length();j++){
				if(newX.charAt(j) == '1'){
					count++;
				}
			}

			/*  不满足三个值的时候结束本次循环  */
			if(count==3){
				
				if(newX.length()!=x.length()){
					for(;;){
						if(newX.length()==x.length()){
							break;
						}
						newX="0"+newX;
					}
				}

				/* 保存符合条件的   */
				if(!list.contains(newX)){
					list.add(newX);
				}				
			}
		}
		return list;
	}

	/* 打印输出进行显示  */
	public static void print(String x,ArrayList<String> list){
		
		// 保存为字节数组
		char[] arr = x.toCharArray();
		
		for(int i=0;i<list.size();i++){
			String temp = list.get(i);
			
			String result = "";
			for(int k=0;k<temp.length();k++){
				if(temp.charAt(k)=='1'){
					//K 的下标对应了
					result+=arr[k];
				}
			}
			System.out.println(result);
		}
	}
}