All Possible 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 possible permutations of a given String?

%w[a b c].permutation.map &:join

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.

Recursively computing all possible permutations of a string Java

There are a few issues:

1. The following line: String sub = str.substring(i+1, str.length()); ignores the first character
2. The same line also treats anything after index i as a "block" of substring that is left unchanged, while in order to generate permutation we should insert the current (first) character in between any two characters of the rest of the string - and do that for each permutation
3. The line s = str.charAt(i) + s; repeats the same mistake in #2

Here's a suggested fix:

---

public static ArrayList<String> computeAllPossiblePermutations(String str) {
    ArrayList<String> perms = new ArrayList<>();
    if (str.length() == 1) {
        perms.add(str);
    } else {
        String chr = str.substring(0,1);
        String rest = str.substring(1);
        ArrayList<String> subPerms = computeAllPossiblePermutations(rest);
        for (String s : subPerms) {
            for (int j = 0; j <= s.length(); j++) {
                String newPerm = s.substring(0,j) + chr + s.substring(j);
                perms.add(newPerm);
            }
        }
    }
    return perms;
}

Generate list of all possible permutations of a string

There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)

Some pseudocode:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

you'd then need to remove all strings less than x in length, they'll be the first (x-1) * len(originalString) entries in the list.

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)

Listing all permutations of a string/integer

First of all: it smells like recursion of course!

Since you also wanted to know the principle, I did my best to explain it human language. I think recursion is very easy most of the times. You only have to grasp two steps:

1. The first step
2. All the other steps (all with the same logic)

In human language:

In short:

1. The permutation of 1 element is one element.
   
2. The permutation of a set of elements is a list each of the elements, concatenated with every permutation of the other elements.
   

Example:

If the set just has one element -->

return it.

perm(a) -> a

If the set has two characters: for
each element in it: return the
element, with the permutation of the
rest of the elements added, like so:

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> ba

Further: for each character in the set: return a character, concatenated with a permutation of > the rest of the set

perm(abc) ->

a + perm(bc) --> abc, acb

b + perm(ac) --> bac, bca

c + perm(ab) --> cab, cba

perm(abc...z) -->

a + perm(...), b + perm(....)

....

I found the pseudocode on http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C#

OK, and something more elaborate (and since it is tagged c #), from http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html :
Rather lengthy, but I decided to copy it anyway, so the post is not dependent on the original.

The function takes a string of characters, and writes down every possible permutation of that exact string, so for example, if "ABC" has been supplied, should spill out:

ABC, ACB, BAC, BCA, CAB, CBA.

Code:

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

---

Related Topics