欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-24 21:56:22
...
//从键盘读入一个由字母构成的串(不大于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);
		}
	}
}