找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
python实现
def getPermutation(s, prefix=''):
if len(s) == 0:
print prefix
for i in range(len(s)):
getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )
getPermutation('abcd','')
其他回答
递归Python解决方案
def permute(input_str):
_permute("", input_str)
def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)
else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])
if __name__ == '__main__':
permute('foobar')
//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合
public class Permutation {
//Act as a queue
private List<Character> list;
//To remove the duplicates
private Set<String> set = new HashSet<String>();
public Permutation(String s) {
list = new LinkedList<Character>();
int len = s.length();
for(int i = 0; i < len; i++) {
list.add(s.charAt(i));
}
}
public List<String> getStack(Character c, List<Character> list) {
LinkedList<String> stack = new LinkedList<String>();
stack.add(""+c);
for(Character ch: list) {
stack.add(""+ch);
}
return stack;
}
public String printCombination(String s1, String s2) {
//S1 will be a single character
StringBuilder sb = new StringBuilder();
String[] strArr = s2.split(",");
for(String s: strArr) {
sb.append(s).append(s1);
sb.append(",");
}
for(String s: strArr) {
sb.append(s1).append(s);
sb.append(",");
}
return sb.toString();
}
public void printPerumtation() {
int cnt = list.size();
for(int i = 0; i < cnt; i++) {
Character c = list.get(0);
list.remove(0);
List<String> stack = getStack(c, list);
while(stack.size() > 1) {
//Remove the top two elements
String s2 = stack.remove(stack.size() - 1);
String s1 = stack.remove(stack.size() - 1);
String comS = printCombination(s1, s2);
stack.add(comS);
}
String[] perms = (stack.remove(0)).split(",");
for(String perm: perms) {
set.add(perm);
}
list.add(c);
}
for(String s: set) {
System.out.println(s);
}
}
}
递归是不必要的,甚至你可以直接计算任何排列,这个解决方案使用泛型来排列任何数组。
这里有关于这个algorihtm的很好的信息。
对于c#开发人员来说,这里有更有用的实现。
public static void main(String[] args) {
String word = "12345";
Character[] array = ArrayUtils.toObject(word.toCharArray());
long[] factorials = Permutation.getFactorials(array.length + 1);
for (long i = 0; i < factorials[array.length]; i++) {
Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
printPermutation(permutation);
}
}
private static void printPermutation(Character[] permutation) {
for (int i = 0; i < permutation.length; i++) {
System.out.print(permutation[i]);
}
System.out.println();
}
该算法计算每个排列的时间和空间复杂度为O(N)。
public class Permutation {
public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
T[] permutation = generatePermutation(array, sequence);
return permutation;
}
public static <T> T[] generatePermutation(T[] array, int[] sequence) {
T[] clone = array.clone();
for (int i = 0; i < clone.length - 1; i++) {
swap(clone, i, i + sequence[i]);
}
return clone;
}
private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
int[] sequence = new int[size];
for (int j = 0; j < sequence.length; j++) {
long factorial = factorials[sequence.length - j];
sequence[j] = (int) (permutationNumber / factorial);
permutationNumber = (int) (permutationNumber % factorial);
}
return sequence;
}
private static <T> void swap(T[] array, int i, int j) {
T t = array[i];
array[i] = array[j];
array[j] = t;
}
public static long[] getFactorials(int length) {
long[] factorials = new long[length];
long factor = 1;
for (int i = 0; i < length; i++) {
factor *= i <= 1 ? 1 : i;
factorials[i] = factor;
}
return factorials;
}
}
没有递归的Java实现
public Set<String> permutate(String s){
Queue<String> permutations = new LinkedList<String>();
Set<String> v = new HashSet<String>();
permutations.add(s);
while(permutations.size()!=0){
String str = permutations.poll();
if(!v.contains(str)){
v.add(str);
for(int i = 0;i<str.length();i++){
String c = String.valueOf(str.charAt(i));
permutations.add(str.substring(i+1) + c + str.substring(0,i));
}
}
}
return v;
}
另一种简单的方法是遍历字符串,选择尚未使用的字符并将其放入缓冲区,继续循环,直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案,因为:
容易理解 容易避免重复 输出是排序的
下面是java代码:
List<String> permute(String str) {
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
Arrays.sort(chars);
helper(chars, used, sb, res);
return res;
}
void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}
// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);
helper(chars, used, sb, res);
// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
str输入:1231
输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}
注意,输出是排序的,没有重复的结果。
推荐文章
- 在流中使用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