找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
//插入每个字符到数组列表中
static ArrayList al = new ArrayList();
private static void findPermutation (String str){
for (int k = 0; k < str.length(); k++) {
addOneChar(str.charAt(k));
}
}
//insert one char into ArrayList
private static void addOneChar(char ch){
String lastPerStr;
String tempStr;
ArrayList locAl = new ArrayList();
for (int i = 0; i < al.size(); i ++ ){
lastPerStr = al.get(i).toString();
//System.out.println("lastPerStr: " + lastPerStr);
for (int j = 0; j <= lastPerStr.length(); j++) {
tempStr = lastPerStr.substring(0,j) + ch +
lastPerStr.substring(j, lastPerStr.length());
locAl.add(tempStr);
//System.out.println("tempStr: " + tempStr);
}
}
if(al.isEmpty()){
al.add(ch);
} else {
al.clear();
al = locAl;
}
}
private static void printArrayList(ArrayList al){
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
}
其他回答
让我们以输入abc为例。
从集合(["c"])中的最后一个元素(c)开始,然后将最后第二个元素(b)添加到它的前面,末尾和中间的每个可能位置,使其["bc", "cb"],然后以同样的方式将后面的下一个元素(a)添加到集合中的每个字符串中,使其:
"a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"]
因此整个排列:
["abc", "bac", "bca","acb" ,"cab", "cba"]
代码:
public class Test
{
static Set<String> permutations;
static Set<String> result = new HashSet<String>();
public static Set<String> permutation(String string) {
permutations = new HashSet<String>();
int n = string.length();
for (int i = n - 1; i >= 0; i--)
{
shuffle(string.charAt(i));
}
return permutations;
}
private static void shuffle(char c) {
if (permutations.size() == 0) {
permutations.add(String.valueOf(c));
} else {
Iterator<String> it = permutations.iterator();
for (int i = 0; i < permutations.size(); i++) {
String temp1;
for (; it.hasNext();) {
temp1 = it.next();
for (int k = 0; k < temp1.length() + 1; k += 1) {
StringBuilder sb = new StringBuilder(temp1);
sb.insert(k, c);
result.add(sb.toString());
}
}
}
permutations = result;
//'result' has to be refreshed so that in next run it doesn't contain stale values.
result = new HashSet<String>();
}
}
public static void main(String[] args) {
Set<String> result = permutation("abc");
System.out.println("\nThere are total of " + result.size() + " permutations:");
Iterator<String> it = result.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
这对我很有效。
import java.util.Arrays;
public class StringPermutations{
public static void main(String args[]) {
String inputString = "ABC";
permute(inputString.toCharArray(), 0, inputString.length()-1);
}
public static void permute(char[] ary, int startIndex, int endIndex) {
if(startIndex == endIndex){
System.out.println(String.valueOf(ary));
}else{
for(int i=startIndex;i<=endIndex;i++) {
swap(ary, startIndex, i );
permute(ary, startIndex+1, endIndex);
swap(ary, startIndex, i );
}
}
}
public static void swap(char[] ary, int x, int y) {
char temp = ary[x];
ary[x] = ary[y];
ary[y] = temp;
}
}
public class StringPermutation {
// Function to print all the permutations of str
static void printPermutn(String str, String ans) {
// If string is empty
if (str.length() == 0) {
System.out.print(ans + " ");
return;
}
for (int i = 0; i < str.length(); i++) {
// ith character of str
char ch = str.charAt(i);
// Rest of the string after excluding
// the ith character
String ros = str.substring(0, i) + str.substring(i + 1);
// Recurvise call
printPermutn(ros, ans + ch);
}
}
public static void main(String[] args) {
String s = "ABC";
printPermutn(s, "");
}
}
基于Heap算法的我的实现:
import java.util.ArrayList;
import java.util.List;
public class PermutationString {
public static List<String> permute(char[] str, int n) {
List<String> permutations = new ArrayList<>();
if (n == 1) {
permutations.add(new String(str));
}
else {
for (int i = 0; i < n; i++) {
permutations.addAll(permute(str, n-1));
if (n % 2 == 0) {
swap(str, i, n-1);
}
else {
swap(str, 0, n-1);
}
}
}
return permutations;
}
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) {
List<String> permutations = permute("abcdefgh".toCharArray(), 8);
System.out.println(permutations);
}
}
时间复杂度为O(n!* n), O(n)为空间复杂度。
这是另一个更简单的方法来做一个字符串的排列。
public class Solution4 {
public static void main(String[] args) {
String a = "Protijayi";
per(a, 0);
}
static void per(String a , int start ) {
//bse case;
if(a.length() == start) {System.out.println(a);}
char[] ca = a.toCharArray();
//swap
for (int i = start; i < ca.length; i++) {
char t = ca[i];
ca[i] = ca[start];
ca[start] = t;
per(new String(ca),start+1);
}
}//per
}
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap