This question already has answers here:
Generating all permutations of a given string
(49个答案)
我有一个数组:
我想用上面的所有组合形成数组。
说吧。,
一百二十三
132个
二百一十三
231个
321个
三百一十二
有谁能告诉我如何在java中找到所需的数组数量和逻辑?
我正在研究如何用所有可能的组合遍历数组。假设我第一次用123迭代,下一次我应该迭代132和213,以此类推。。。
(49个答案)
我有一个数组:
String wordArr[]=new String[3];
[1 2 3]
我想用上面的所有组合形成数组。
说吧。,
一百二十三
132个
二百一十三
231个
321个
三百一十二
有谁能告诉我如何在java中找到所需的数组数量和逻辑?
我正在研究如何用所有可能的组合遍历数组。假设我第一次用123迭代,下一次我应该迭代132和213,以此类推。。。
最佳答案
将backtracking应用于置换的实现是有用的。基本思想是,对于从0到数组长度的indexloc
,枚举所有可能的pick forarr[loc]
我已经用Java实现了以下内容,但它可以用任何语言实现。
import java.util.*;
public class PermutationTest{
private static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void permutations(char[] arr, int loc, int len, ArrayList<String> result) {
if (loc == len) {
result.add(new String(arr));
return;
}
// Pick the element to put at arr[loc]
permutations(arr, loc + 1, len, result);
for (int i = loc + 1; i < len; i++) {
// Swap the current arr[loc] to position i
swap(arr, loc, i);
permutations(arr, loc + 1, len, result);
// Restore the status of arr to perform the next pick
swap(arr, loc, i);
}
}
public static ArrayList<String> permutations(String str) {
ArrayList<String> result = new ArrayList<String>();
if (str.length() == 0) { return result; }
permutations(str.toCharArray(), 0, str.length(), result);
return result;
}
public static void main(String []args){
ArrayList<String> result = permutations("123");
for (String str : result) {
System.out.println(str);
}
}
}