java实现字符串排列组合问题

java实现字符串排列组合问题

本文为大家介绍了java实现字符串排列组合问题，供大家参考，具体内容如下

import java.util.ArrayList;

import java.util.Collections;

/**

* 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,

* bca,cab和cba。

*

* @author pomay

*

*/

public class Solution_stringarrange

{

public ArrayList Permutation(String str)

{

if (str == null)

return null;

ArrayvbJrKhzList list = new ArrayList();

char[] pStr = str.toCharArray();

Permutation(pStr, 0, list);

Collections.sort(list);

return list;

}

static void Permutation(char[] str, int i, ArrayList list)

{

// 如果为空

if (str == null)

return;

// 如果i指向了最后一个字符

if (i == str.length - 1)

{

if (list.contains(String.valueOf(str)))

return;

list.add(String.valueOf(str));

} else

{

// i指向当前我们做排列操作的字符串的第一个字符

for (int j = i; j < str.length; j++)

{

// 把做排列操作的字符串的第一个字符和后面的所有字符交换

char temp = str[j];

str[j] = str[i];

str[i] = temp;

// 交换后对i后面的字符串递归做排列操作

Permutation(str, i + 1, list);

// 每一轮结束后换回来进行下一轮排列操作

temp = str[j];

str[j] = str[i];

str[i] = temp;

}

}

}

public static void main(String[] args)

{

String str = "aab";

Solution_stringarrange changestring = new Solution_stringarrange();

ArrayList list = changestring.Permutation(str);

for (int i = 0; i < list.size(); i++)

{

System.out.print(list.get(i) + " ");

}

}

}

组合：

要么选择长度为n的字符串中的第一个字符，那么要在其余的长度n-1的字符串中选择m-1个字符

要么不选择长度为n的字符串中的第一个字符，那么要在其余的长度n-1的字符串中选择m个字符

import java.util.ArrayList;

import java.util.List;

/**

* 输入一个字符串,按字典序打印出该字符串中字符的所有组合。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串a,b,c,ab,ac,bc

* ,abc 。 求n个字符组成长度为m的组合问题

*

* @author pomay

*

*/

public class Solution_stringcombination

{

// 求字符串中所有字符的组合abc>a,b,c,ab,ac,bc,abc

public static void perm(String s)

{

List result = new ArrayList();

// 从一个开始

for (int i = 1; i <= s.length(); i++)

{

combination(s, i, result);

}

}

// 从字符串s中选择m个字符

public static void combination(String s, int m, List result)

{

// 如果m==0，则递归结束。输出当前结果

if (m == 0)

{

for (int i = 0; i < result.size(); i++)

{

System.out.print(result.get(i));

}

System.out.print("、");

return;

}

if (s.length() != 0)

{

// 选择当前元素

result.add(s.charAt(0) + "");

// substring用法，截取出从1开始到n结束的字符串

combination(s.substring(1, s.length()), m - 1, result);

result.remove(result.size() - 1);

// 不选当前元素

combination(s.substring(1, s.length()), m, result);

}

}

public static void main(String[] args)

{

String str = "abc";

perm(str);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。