使用迭代的字符串排列

Question

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

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. i.e: 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. i.e: 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<String> results = new ArrayList<String>();
    String test_str = "abcd";
    char[] chars = test_str.toCharArray();
    results.add(new String("" + chars[0]));
    for(int j=1; j<chars.length; j++) {
        char c = chars[j];
        int cur_size = results.size();
        //create new permutations combing char 'c' with each of the existing permutations
        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));
            }
        }
    }
    System.out.println("Number of Permutations: " + results.size());
    System.out.println(results);

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

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<chars.length; j++) {
    char c = chars[j];
     ....
     ....
}

这使我们从“ ba”和“ cab”获得“ cba”，“ bca”，“ bac”，从“ ab”获得“ acb”和“ abc”