Generating All Permutations of a Given String

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)

Finding all possible permutations of a given string in python

The itertools module has a useful method called permutations(). The documentation says:

itertools.permutations(iterable[, r])

Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the
iterable and all possible full-length permutations are generated.

Permutations are emitted in lexicographic sort order. So, if the input
iterable is sorted, the permutation tuples will be produced in sorted
order.

You'll have to join your permuted letters as strings though.

>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms

['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck',
'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka',
'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc',
'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka',
'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc',
'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas',
'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck',
'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc',
'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk',
'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs',
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta',
'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas',
'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta',
'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca',
'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc',
'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs',
'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast',
'kcats']

If you find yourself troubled by duplicates, try fitting your data into a structure with no duplicates like a set:

>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360

Thanks to @pst for pointing out that this is not what we'd traditionally think of as a type cast, but more of a call to the set() constructor.

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.

Algorithm to generating all permutations of a string with no adjacent characters

Here’s a fairly straightforward backtracking solution pruning the search before adding an adjacent character to the permutation.

public class PermutationsNoAdjacent {

    private char[] inputChars;
    private boolean[] inputUsed;
    private char[] outputChars;
    private List<String> permutations = new ArrayList<>();

    public PermutationsNoAdjacent(String inputString) {
        inputChars = inputString.toCharArray();
        inputUsed = new boolean[inputString.length()];
        outputChars = new char[inputString.length()];
    }

    private String[] generatePermutations() {
        tryFirst();
        return permutations.toArray(new String[permutations.size()]);
    }

    private void tryFirst() {
        for (int inputIndex = 0; inputIndex < inputChars.length; inputIndex++) {
            assert !inputUsed[inputIndex] : inputIndex;
            outputChars[0] = inputChars[inputIndex];
            inputUsed[inputIndex] = true;
            tryNext(inputIndex, 1);
            inputUsed[inputIndex] = false;
        }
    }

    private void tryNext(int previousInputIndex, int outputIndex) {
        if (outputIndex == outputChars.length) { // done
            permutations.add(new String(outputChars));
        } else {
            // avoid previousInputIndex and adjecent indices
            for (int inputIndex = 0; inputIndex < previousInputIndex - 1; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
            for (int inputIndex = previousInputIndex + 2; inputIndex < inputChars.length; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
        }
    }

    public static void main(String... args) {
        String[] permutations = new PermutationsNoAdjacent("ABCDEF").generatePermutations();
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }

}

It prints 90 permutations of ABCDEF. I’ll just quote the beginning and the end:

ACEBDF
ACEBFD
ACFDBE
ADBECF
…
FDBEAC
FDBECA

Generating all permutations of a certain length

In order to pick five characters from a string recursively, follow a simple algorithm:

Your method should get a portion filled in so far, and the first position in the five-character permutation that needs a character
If the first position that needs a character is above five, you are done; print the combination that you have so far, and return
Otherwise, put each character into the current position in the permutation, and make a recursive call

This is a lot shorter in Java:

private static void permutation(char[] perm, int pos, String str) {
    if (pos == perm.length) {
        System.out.println(new String(perm));
    } else {
        for (int i = 0 ; i < str.length() ; i++) {
            perm[pos] = str.charAt(i);
            permutation(perm, pos+1, str);
        }
    }
}

The caller controls the desired length of permutation by changing the number of elements in perm:

char[] perm = new char[5];
permutation(perm, 0, "abcdefghiklimnop");

Demo.