Are There Any Better Methods to Do Permutation of String

Are there any better methods to do permutation of string?

Here is a non-recursive algorithm in C++ from the Wikipedia entry for unordered generation of permutations. For the string s of length n, for any k from 0 to n! - 1 inclusive, the following modifies s to provide a unique permutation (that is, different from those generated for any other k value on that range). To generate all permutations, run it for all n! k values on the original value of s.

#include <algorithm>

void permutation(int k, string &s) 
{
    for(int j = 1; j < s.size(); ++j) 
    {
        std::swap(s[k % (j + 1)], s[j]); 
        k = k / (j + 1);
    }
}

Here swap(s, i, j) swaps position i and j of the string s.

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

complexity of recursive string permutation function

Ignoring the print, the recurrence relation satisfied is

T(n) = n*T(n-1) + O(n)

If G(n) = T(n)/n! we get

G(n) = G(n-1) + O(1/(n-1)!)

which gives G(n) = Theta(1).

Thus T(n) = Theta(n!).

Assuming that the print happens exactly n! times, we get the time complexity as

Theta(n * n!)

Faster string permutation

There are existing algorithms for generating permutations which may be slightly more efficient than the one you're using, so you could take a look at one of those. I've used the Johnson-Trotter algorithm in the past, which gets a slight speed up by making the minimum change possible to get the next permutation each time. I don't know what kind of constraints you have to work within, but if you don't have to use Java it might be better not to. It simply won't be the fastest for this. Especially if your algorithm is using recursion. As someone else has suggested, if you're sticking with this algorithm you might be best served to move away from the recursive approach and try using a loop.

All permutations of a given string - complexity

There exists O(n!) permutations of a string of length n.

In generating each string in the permutation, you are doing O(n) operation by having a for loop of O(string.length) = O(n)

It might not be obvious why there's n!, but you are recursively calling permutation(..) function with remaining string, so the string length will be n * (n - 1) * (n - 2) * (n - 3) * ... * 1.

Thus, the time complexity of your algorithm is O(n * n!).

Other popular known solutions (swap-based, which is similar to yours, and next-permutation-based) have the same time complexity.

Possible permutations of string based on LinkedHashMap?

Try this.

static List<String> possiblePermutations(Map<String, String> map) {
    int size = map.size();
    List<Entry<String, String>> list = new ArrayList<>(map.entrySet());
    List<String> result = new ArrayList<>();
    new Object() {
        void perm(int i, String s) {
            if (i >= size) {
                result.add(s);
                return;
            }
            Entry<String, String> entry = list.get(i);
            perm(i + 1, s + entry.getKey());
            perm(i + 1, s + entry.getValue());
        }
    }.perm(0, "");
    return result;
}

public static void main(String[] args) {
    Map<String, String> map = new LinkedHashMap<>();
    map.put("a", "ab");
    map.put("b", "c");
    map.put("x", "y");
    List<String> result = possiblePermutations(map);
    System.out.println(result);
}

output:

[abx, aby, acx, acy, abbx, abby, abcx, abcy]

---

Related Topics