使用迭代的字符串排列

我试图找到给定字符串的排列，但我想使用迭代。 我在网上找到的递归解决方案，我确实理解它，但将其转换为迭代解决方案实际上并没有成功。 下面我附上了我的代码。 我真的很感激帮助：

public static void combString(String s) { char[] a = new char[s.length()]; //String temp = ""; for(int i = 0; i < s.length(); i++) { a[i] = s.charAt(i); } for(int i = 0; i < s.length(); i++) { String temp = "" + a[i]; for(int j = 0; j < s.length();j++) { //int k = j; if(i != j) { System.out.println(j); temp += s.substring(0,j) + s.substring(j+1,s.length()); } } System.out.println(temp); } } 

Answer 1

关注我的相关问题评论，这是一个Java实现，使用Counting QuickPerm算法执行您想要的操作：

 public static void combString(String s) { // Print initial string, as only the alterations will be printed later System.out.println(s); char[] a = s.toCharArray(); int n = a.length; int[] p = new int[n]; // Weight index control array initially all zeros. Of course, same size of the char array. int i = 1; //Upper bound index. ie: if string is "abc" then index i could be at "c" while (i < n) { if (p[i] < i) { //if the weight index is bigger or the same it means that we have already switched between these i,j (one iteration before). int j = ((i % 2) == 0) ? 0 : p[i];//Lower bound index. ie: if string is "abc" then j index will always be 0. swap(a, i, j); // Print current System.out.println(join(a)); p[i]++; //Adding 1 to the specific weight that relates to the char array. i = 1; //if i was 2 (for example), after the swap we now need to swap for i=1 } else { p[i] = 0;//Weight index will be zero because one iteration before, it was 1 (for example) to indicate that char array a[i] swapped. i++;//i index will have the option to go forward in the char array for "longer swaps" } } } private static String join(char[] a) { StringBuilder builder = new StringBuilder(); builder.append(a); return builder.toString(); } private static void swap(char[] a, int i, int j) { char temp = a[i]; a[i] = a[j]; a[j] = temp; } 

Answer 2

  List results = new ArrayList(); String test_str = "abcd"; char[] chars = test_str.toCharArray(); results.add(new String("" + chars[0])); for(int j=1; j=0; i--) { String str = results.remove(i); for(int l=0; l<=str.length(); l++) { results.add(str.substring(0,l) + c + str.substring(l)); } } } System.out.println("Number of Permutations: " + results.size()); System.out.println(results); 

示例：如果我们有3个字符串，例如“abc”，我们可以形成如下所示的permations。

1）构造一个带有第一个字符的字符串，例如'a'，并将其存储在结果中。

  char[] chars = test_str.toCharArray(); results.add(new String("" + chars[0])); 

2）现在接受字符串中的下一个字符（即'b'）并将其插入到结果中先前被包含的字符串的所有可能位置。 由于此时我们在结果中只有一个字符串（“a”），这样做会给我们2个新字符串'ba'，'ab'。 在结果中插入这些新构造的字符串并删除“a”。

  for(int i=cur_size-1; i>=0; i--) { String str = results.remove(i); for(int l=0; l<=str.length(); l++) { results.add(str.substring(0,l) + c + str.substring(l)); } } 

3）对给定字符串中的每个字符重复2）。

 for(int j=1; j 

这给了我们“cba”，“bca”，“bac”来自“ba”和“cab”，“acb”和“abc”来自“ab”

Answer 3

工作队列允许我们为此问题创建一个优雅的迭代解决方案。

 static List permutations(String string) { List permutations = new LinkedList<>(); Deque workQueue = new LinkedList<>(); // We need to permutate the whole string and haven't done anything yet. workQueue.add(new WorkUnit(string, "")); while (!workQueue.isEmpty()) { // Do we still have any work? WorkUnit work = workQueue.poll(); // Permutate each character. for (int i = 0; i < work.todo.length(); i++) { String permutation = work.done + work.todo.charAt(i); // Did we already build a complete permutation? if (permutation.length() == string.length()) { permutations.add(permutation); } else { // Otherwise what characters are left? String stillTodo = work.todo.substring(0, i) + work.todo.substring(i + 1); workQueue.add(new WorkUnit(stillTodo, permutation)); } } } return permutations; } 

保存部分结果的辅助类非常简单。

 /** * Immutable unit of work */ class WorkUnit { final String todo; final String done; WorkUnit(String todo, String done) { this.todo = todo; this.done = done; } } 

您可以通过将它们包装在此类中来测试上面的代码。

 import java.util.*; public class AllPermutations { public static void main(String... args) { String str = args[0]; System.out.println(permutations(str)); } static List permutations(String string) { ... } } class WorkUnit { ... } 

通过编译和运行来尝试它。

 $ javac AllPermutations.java; java AllPermutations abcd 

通过使用LIFO工作堆而不是FIFO队列，也可以轻松地调整以下实现以反向顺序返回排列列表。

Answer 4

 import java.util.List; import java.util.Set; import java.util.ArrayList; import java.util.HashSet; public class Anagrams{ public static void main(String[] args) { String inpString = "abcd"; Set combs = getAllCombs(inpString); for(String comb : combs) { System.out.println(comb); } } private static Set getAllCombs(String inpString) { Set combs = new HashSet(); if( inpString == null | inpString.isEmpty()) return combs; combs.add(inpString.substring(0,1)); Set tempCombs = new HashSet(); for(char a : inpString.substring(1).toCharArray()) { tempCombs.clear(); tempCombs.addAll(combs); combs.clear(); for(String comb : tempCombs) { combs.addAll(getCombs(comb,a)); } } return combs; } private static Set getCombs(String comb, char a) { Set combs = new HashSet(); for(int i = 0 ; i <= comb.length(); i++) { String temp = comb.substring(0, i) + a + comb.substring(i); combs.add(temp); //System.out.println(temp); } return combs; } } 

Answer 5

只是发布我对问题的处理方法：

 import java.util.ArrayDeque; import java.util.Queue; public class PermutationIterative { public static void main(String[] args) { permutationIterative("abcd"); } private static void permutationIterative(String str) { Queue currentQueue = null; int charNumber = 1; for (char c : str.toCharArray()) { if (currentQueue == null) { currentQueue = new ArrayDeque<>(1); currentQueue.add(String.valueOf(c)); } else { int currentQueueSize = currentQueue.size(); int numElements = currentQueueSize * charNumber; Queue nextQueue = new ArrayDeque<>(numElements); for (int i = 0; i < currentQueueSize; i++) { String tempString = currentQueue.remove(); for (int j = 0; j < charNumber; j++) { int n = tempString.length(); nextQueue.add(tempString.substring(0, j) + c + tempString.substring(j, n)); } } currentQueue = nextQueue; } charNumber++; } System.out.println(currentQueue); } } 

Answer 6

 // Java program to print all permutations of a // given string. public class Permutation { public static void main(String[] args) { String str = "ABC"; int n = str.length(); Permutation permutation = new Permutation(); permutation.permute(str, 0, n-1); } /** * permutation function * @param str string to calculate permutation for * @param s starting index * @param e end index */ private void permute(String str, int s, int e) { if (s == e) System.out.println(str); else { for (int i = s; i <= s; i++) { str = swap(str,l,i); permute(str, s+1, e); str = swap(str,l,i); } } } /** * Swap Characters at position * @param a string value * @param i position 1 * @param j position 2 * @return swapped string */ public String swap(String a, int i, int j) { char temp; char[] charArray = a.toCharArray(); temp = charArray[i] ; charArray[i] = charArray[j]; charArray[j] = temp; return String.valueOf(charArray); } }