Listing All Permutations of a String/Integer

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:

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

In human language:

In short:
The permutation of 1 element is one element.
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
  }
}

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);
    }
}

All permutations of a list

Try these extension methods on for size:

public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> sequence)
{
    if (sequence == null)
    {
        yield break;
    }

    var list = sequence.ToList();

    if (!list.Any())
    {
        yield return Enumerable.Empty<T>();
    }
    else
    {
        var startingElementIndex = 0;

        foreach (var startingElement in list)
        {
            var index = startingElementIndex;
            var remainingItems = list.Where((e, i) => i != index);

            foreach (var permutationOfRemainder in remainingItems.Permute())
            {
                yield return permutationOfRemainder.Prepend(startingElement);
            }

            startingElementIndex++;
        }
    }
}

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)

Generating permutations of a set (most efficiently)

Update 2018-05-28:
A new multithreaded version (lot faster) is available below as another answer.
Also an article about permutation: Permutations: Fast implementations and a new indexing algorithm allowing multithreading

A little bit too late...

According to recent tests (updated 2018-05-22)

Fastest is mine BUT not in lexicographic order
For fastest lexicographic order, Sani Singh Huttunen solution seems to be the way to go.

Performance test results for 10 items (10!) in release on my machine (millisecs):

Ouellet : 29
SimpleVar: 95
Erez Robinson : 156
Sani Singh Huttunen : 37
Pengyang : 45047

Performance test results for 13 items (13!) in release on my machine (seconds):

Ouellet : 48.437
SimpleVar: 159.869
Erez Robinson : 327.781
Sani Singh Huttunen : 64.839

Advantages of my solution:

Heap's algorithm (Single swap per permutation)
No multiplication (like some implementations seen on the web)
Inlined swap
Generic
No unsafe code
In place (very low memory usage)
No modulo (only first bit compare)

My implementation of Heap's algorithm:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;

namespace WpfPermutations
{
    /// <summary>
    /// EO: 2016-04-14
    /// Generator of all permutations of an array of anything.
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// </summary>
    public static class Permutations
    {
        /// <summary>
        /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
        /// </summary>
        /// <param name="items">Items to permute in each possible ways</param>
        /// <param name="funcExecuteAndTellIfShouldStop"></param>
        /// <returns>Return true if cancelled</returns> 
        public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
        {
            int countOfItem = items.Length;

            if (countOfItem <= 1)
            {
                return funcExecuteAndTellIfShouldStop(items);
            }

            var indexes = new int[countOfItem];
            
            // Unecessary. Thanks to NetManage for the advise
            // for (int i = 0; i < countOfItem; i++)
            // {
            //     indexes[i] = 0;
            // }

            if (funcExecuteAndTellIfShouldStop(items))
            {
                return true;
            }

            for (int i = 1; i < countOfItem;)
            {
                if (indexes[i] < i)
                { // On the web there is an implementation with a multiplication which should be less efficient.
                    if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                    {
                        Swap(ref items[i], ref items[indexes[i]]);
                    }
                    else
                    {
                        Swap(ref items[i], ref items[0]);
                    }

                    if (funcExecuteAndTellIfShouldStop(items))
                    {
                        return true;
                    }

                    indexes[i]++;
                    i = 1;
                }
                else
                {
                    indexes[i++] = 0;
                }
            }

            return false;
        }

        /// <summary>
        /// This function is to show a linq way but is far less efficient
        /// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });

            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

        /// <summary>
        /// Swap 2 elements of same type
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <param name="b"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            T temp = a;
            a = b;
            b = temp;
        }

        /// <summary>
        /// Func to show how to call. It does a little test for an array of 4 items.
        /// </summary>
        public static void Test()
        {
            ForAllPermutation("123".ToCharArray(), (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            int[] values = new int[] { 0, 1, 2, 4 };

            Console.WriteLine("Ouellet heap's algorithm implementation");
            ForAllPermutation(values, (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            Console.WriteLine("Linq algorithm");
            foreach (var v in GetPermutations(values, values.Length))
            {
                Console.WriteLine(String.Join("", v));
            }

            // Performance Heap's against Linq version : huge differences
            int count = 0;

            values = new int[10];
            for (int n = 0; n < values.Length; n++)
            {
                values[n] = n;
            }

            Stopwatch stopWatch = new Stopwatch();

            ForAllPermutation(values, (vals) =>
            {
                foreach (var v in vals)
                {
                    count++;
                }
                return false;
            });

            stopWatch.Stop();
            Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");

            count = 0;
            stopWatch.Reset();
            stopWatch.Start();

            foreach (var vals in GetPermutations(values, values.Length))
            {
                foreach (var v in vals)
                {
                    count++;
                }
            }

            stopWatch.Stop();
            Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
        }
    }
}

An this is my test code:

Task.Run(() =>
            {

                int[] values = new int[12];
                for (int n = 0; n < values.Length; n++)
                {
                    values[n] = n;
                }

                // Eric Ouellet Algorithm
                int count = 0;
                var stopwatch = new Stopwatch();
                stopwatch.Reset();
                stopwatch.Start();
                Permutations.ForAllPermutation(values, (vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                    return false;
                });
                stopwatch.Stop();
                Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // Simple Plan Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
                permutations2.Permutate(1, values.Length, (int[] vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                });
                stopwatch.Stop();
                Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // ErezRobinson Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                };
                stopwatch.Stop();
                Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
            });

Usage examples:

ForAllPermutation("123".ToCharArray(), (vals) =>
    {
        Console.WriteLine(String.Join("", vals));
        return false;
    });

int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
        {
            Console.WriteLine(String.Join("", vals));
            return false;
        });

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.

Get all permutations of a List(Of List(Of String)) in VB.NET

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    Dim Obj As New List(Of List(Of String))

    Dim x As New List(Of String)
    x.Add("a")
    x.Add("b")
    x.Add("c")

    Dim y As New List(Of String)
    y.Add("d")
    y.Add("e")

    Obj.Add(x)
    Obj.Add(y)

    For Each outputString As String In createPermutations(0, Obj)
        System.Console.WriteLine(outputString)
    Next

End Sub

Function createPermutations(level As Integer, listOfLists As List(Of List(Of String)))
    Dim retval As New List(Of String)

    If (level = listOfLists.Count) Then
        retval.Add("")
        Return retval
    End If

    For Each y As String In listOfLists(level)
        For Each x2 As String In createPermutations(level + 1, listOfLists)
            retval.Add(y + " " + x2)
        Next
    Next
    Return retval
End Function

Listing all permutations of a given set of values

You can choose between performance, particular distribution and simplicity. By a particular distribution I mean, whether you care about some particular order, such as lexicographic, of the output.

The best performing algorithm to my knowledge is the Steinhaus algorithm. It is optimal up to a multiplicative constant in the sense that only a constant number of processor instructions are necessary to generate one permutation (not counting the instructions necessary to print it out which is not always needed).

There is also a very simple algorithm that produces the permutations in the lexicographic order that you will probably be able to reinvent as a recursive procedure yourself, and whose performance is O(n.log(n).log(n)), therefore roughly the same as generating the list by any other method and sorting it.

Edit: here is pseudocode of the simple algorithm:

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

Initially call this with an empty permutationPrefix and rest holding the full set; if this set is a sorted data structure, the permutations will be output in the lexicographic order.

Note that we are copying and modifying the set at each recursive call, which is the most expensive operation of the whole algorithm, possibly together with the print method. The cost of a single set copy is logarithmic in the total number of permutations n; and because the depth of the recursive call stack is also logarithmic, the O(n.log(n).log(n)) performance estimate follows.

(This algorithm is also suitable for conversion into a well behaved random permutation generator.)

Listing permutations of different combination of characters

Use this code:

public static List<string> GenerateCombinations(char[][] characters)
{
    var combinations = new List<string>();
    GenerateCombinations(0, characters, new char[characters.GetLength(0)], combinations);
    return combinations;
}

private static void GenerateCombinations(int level, char[][] characters, char[] current, List<string> combinations)
{
    if (level == characters.GetLength(0))
    {
        combinations.Add(new string(current));
        return;
    }

    foreach (var character in characters[level])
    {
        current[level] = character;
        GenerateCombinations(level + 1, characters, current, combinations);
    }
}

Example of using it:

public static void Main()
{
    var characters = new[]
                     {
                         new[] { 'a', 'b' },
                         new[] { 'a', 'b' },
                         new[] { '1', '2' }
                     };

    var combinations = GenerateCombinations(characters);
    foreach (var combination in combinations)
    {
        Console.WriteLine(combination);
    }
}

Output:

aa1
aa2
ab1
ab2
ba1
ba2
bb1
bb2

Listing All Permutations of a String/Integer