- package com.itheima;
- import java.util.ArrayList;
- import java.util.Stack;
- public class Test7 {
-
- /**
- * 7.编程列出一个字符串的全字符组合情况,原始字符串中没有重复字符,例如:
- * 原始字符串是"abc",打印得到下列所有组合情况:
- * "a" "b" "c"
- * "ab" "bc" "ca" "ba" "cb" "ac"
- * "abc" "acb" "bac" "bca" "cab" "cba"
- *思路:
- *1.先求字符串的所有组合情况
- *2.求各组合子串的所有排列情况
- *
- *
- */
- //保存字符串的所有组合情况
- public static ArrayList<char[]> list =new ArrayList<char[]>();
- //保存字符串的全字符组合
- public static ArrayList<String> list2 = new ArrayList<String>();
-
- /*
- * 获得字符串 str 的全部组合情况
- * 例如 "abc" ---> "abc" "ab" "a" "ac" "bc" "b" "c"
- * 并把全部组合情况保存到 ArrayList list中
- *
- */
- public static void selectChar(char[] str,int begin,int m,Stack<Character>select){
- //递归出口
- if(m == 0){
- //将集合转数组,并写上转型
- Object[] Ochars = select.toArray();
- //定义一个数组容器,长度为集合的长度
- char []chars = new char[Ochars.length];
- for(int i = 0;i < Ochars.length;i++){
- //赋值
- chars[i] = (Character)Ochars[i];
- }
- list.add(chars);
- return;
- }
- //元素进栈
- select.push(str[begin]);
- //递归调用,从下一个位置获取m-1个元素
- selectChar(str,begin + 1,m - 1,select);
- //元素出栈
- select.pop();
- selectChar(str,begin + 1 ,m - 1 ,select);
- }
- /**
- * 求一个字符串的所有排列情况
- *
- */
- public static void permutation(char[] str,int begin,int end){
- if(begin == end){
- list2.add(new String(str));
- return;
- }
- for(int j=begin;j<=end;j++){
- //元素交换
- swap(str,begin,j);
- //递归调用
- permutation(str,begin + 1,end);
- //回溯
- swap(str,begin,j);
- }
-
- }
- //元素的交换
- public static void swap(char[]str,int i,int j){
- char temp = str[i];
- str[i] = str[j];
- str[j] = temp;
- }
- public static void main(String[] args) {
- String str = "abc";
- Stack<Character> s = new Stack<Character>();
- //获得元素所有组合
- selectChar(str.toCharArray(),0,str.length(),s);
- //实现组合字符串的所有排列
- for(int i = 0;i<list.size();i++){
- //取得所有排列组合的子串
- char[] c = list.get(i);
- //将子串排列
- permutation(c,0,c.length - 1);
- }
- for(int j = 0;j<list2.size();j++){
- System.out.print("'"+list2.get(j)+"'"+" ");
- }
- }
- }
复制代码
|