CODEWITHSUNDEEP
javaalgorithm
giulio
giulio

Reputation: 659

Permutations of a string with no duplicates

I read solutions to the problem of generating all the permutations of a string (solution).

Can anyone explain how perm2 is different from perm1? (I feel the only difference is that perm1 tries to put each element in the first position while perm2 in the last one)

// print N! permutation of the characters of the string s (in order)
public  static void perm1(String s) { perm1("", s); }
private static void perm1(String prefix, String s) {
    int N = s.length();
    if (N == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < N; i++)
           perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
    }

}

 // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s) {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }

Also, if some letters are the same in the string, then some permutations will be the same? The only way I can think of to prevent this is to save the result in a hashset so as to keep only one instance of a permutation. Is there a better solution?

Upvotes: 0

Views: 2074

Answers (1)

sprinter
sprinter

Reputation: 27996

I expect that the justification for the second solution is efficiency. It uses character arrays rather than String objects and swaps characters at each step rather than creating a new String via concatenation.

In terms of functionality the only difference between the two solutions is the order in which the results will be output.

You are correct that this does not guarantee unique solutions if there are some duplicate characters in the input. Storing the results and checking uniqueness (by using a Set or directly via contains) would be the easiest way to avoid this if required.

An alternative, in the second solution, would be to check if a character has already been handled. This would avoid the overhead of storing a result set (which could be significant for long strings).

In second perm2 function:

if (n == 1) {
    System.out.println(a);
    return;
}
for (int i = n; i < a.length; i++) {
    if (a[i] == a[n-1])
        return;
}
for (int i = 0; i < n; i++) {
    boolean duplicate = false;
    for (int j = 0; !duplicate && j < i; j++)
        duplicate = a[i] == a[j];
    if (!duplicate) {
        swap(a, i, n-1);
        perm2(a, n-1);
        swap(a, i, n-1);
    }
}

Upvotes: 1

Related Questions