Algorithm to generate all possible permutations of a list?

Below are two classic kotlin implementations of recursive and non recursive Heap algorithm implementations:

Non recursive:

fun <T> permutationsHeapNonRecursive(list: List<T>): List<List<T>> {
    val result = mutableListOf<List<T>>()
    val c = Array(list.size) {0}
    result.add(list.toList())

    val tempList = list.toMutableList()
    var i = 1
    while (i < list.size) {
        if (c[i] < i) {
            if (i % 2 == 0)
                tempList[0] = tempList[i].also { tempList[i] = tempList[0] }
            else
                tempList[c[i]] = tempList[i].also { tempList[i] = tempList[c[i]] }
            result.add(tempList.toList())
            c[i] += 1
            i = 1
        }
        else {
            c[i] = 0
            i += 1
        }
    }
    return result
}

and, recursive:

private fun <T> permutationsHeapRecursiveInternal(k: Int, list: MutableList<T>, outList: MutableList<List<T>>) {
    if (k == 1) {
        outList.add(List<T>(list.size) {list[it]})
    }
    else {
        permutationsHeapRecursiveInternal(k - 1, list, outList)
        for (i in 0 until k-1) {
            if (k % 2 == 0)
                list[i] = list[k-1].also{ list[k-1] = list[i] }
            else
                list[0] = list[k-1].also{ list[k-1] = list[0] }
            permutationsHeapRecursiveInternal(k - 1, list, outList)
        }
    }
}

fun <T> permutationsHeapRecursive(list: List<T>): List<List<T>> {
    val result = mutableListOf<List<T>>()
    if (list.isNotEmpty()) {
        val tempList = MutableList<T>(list.size) { i -> list[i] }
        permutationsHeapRecursiveInternal(tempList.size, tempList, result)
    }
    return result
}

I have profiled non recursive version and after some tweaking with limiting memory allocations it is faster than recursive one.

As a C# Extension Method:

• Avoids inserting at position zero into List() (assumed backed by Array).
• Replaces the list.Count == 2 with a simpler list.Count == 0 check.
• Disadvantage, uses an extra arg during recursion.

Usage:

List<List<string>> permutations = new List<string> { "A", "BB", "CCC" }.Permutations();

Debug.WriteLine(String.Join("; ", permutations.Select(p => string.Join(", ", p))));

Output:

A, BB, CCC; A, CCC, BB; BB, A, CCC; BB, CCC, A; CCC, A, BB; CCC, BB, A

Method:

static public List<List<T>> Permutations<T>(this List<T> list, List<T> prefillOpt = null) 
{
    List<List<T>> result = new List<List<T>>();

    if (list.Count == 0)
    {
        if (prefillOpt?.Any() == true)
            result.Add(prefillOpt.ToList()); // make a copy, owned by caller
    }
    else
    {
        prefillOpt = prefillOpt ?? new List<T>();

        for (int i = 0; i < list.Count; i++)
        {                    
            prefillOpt.Add(list[i]);

            int j = 0;
            result.AddRange(Permutations(list.Where(moot => j++ != i).ToList(), prefillOpt));
                    
            prefillOpt.RemoveAt(prefillOpt.Count - 1);
        }
    }
    return result;
}

The following is the generic implementation of Heap's algorithm (works with int, char, etc):

void generate<T>(int k, List<T> A, List<List<T>> result)
{
    if (k == 1)
    {
        result.Add(new List<T>(A)); 
        return;
    }
    for (int i = 0; i < k; i++)
    {
        generate(k - 1, A, result);
        if (k % 2 == 0)
            (A[i], A[k - 1]) = (A[k - 1], A[i]);
        else
            (A[0], A[k - 1]) = (A[k - 1], A[0]);
    }
}

To use it:

var permutations = new List<List<char>>();
List<char> A = new List<char>() { 'a', 'b', 'c', 'd'};
generate<char>(A.Count, A, permutations);
// The output is in permutations
int c = 0;
foreach (var item in permutations)
{
    c++;
    Console.Write(c + ". ");
    foreach (var element in item)
    {
        Console.Write(element);
    }
    Console.WriteLine();

}

Here's something i just came up with:

def permute(elements):
        permutations=[]
        for i in range(999999):
            tmp_elements = elements.copy()
            candidate = []
            while len(tmp_elements)>0:
                index = random.randint(0,len(tmp_elements)-1)
                candidate.append(tmp_elements[index])
                tmp_elements.pop(index)
            if candidate not in permutations:
                permutations.append(candidate)
        permutations.sort()
        return permutations

Bourne shell solution - in a total of four lines (without test for no param case):

test $# -eq 1 && echo "$1" && exit
for i in $*; do
  $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done

This produces them one-at-time without making a list - the same end result as Marios Choudary's answer (or simply calling C++'s nextPermute, as Anders answer notes). But this is Heap's algorithm (the non-recursive version) re-arranged and a class to save context. Used as:

P5=new genPermutes_t(5); // P5.P is now [0,1,2,3,4]
while(!P5.isDone()) {
  // use P5.P here
  P5.next();
}

Code is in C# without being an endorsement. Variables are as-is from Heap's pseudocode, to which the comments also refer:

public class genPermutes_t {
  public int[] P; // the current permuation

  private int n, i; // vars from the original algorithm
  private int[] c; // ditto

  public genPermutes_t(int count) {
    // init algorithm:
    n=count;
    i=0;
    c=new int[n];
    for(int j=0;j<n;j++) c[j]=0;

    // start current permutation as 0,1 ... n-1:
    P=new int[n];
    for(int j=0;j<n;j++) P[j]=j;
  }

  public bool isDone() {
    return i>=n; // condition on the original while loop
  }

  public void next() {
    // the part of the loop that spins until done or ready for next permute:
    while(i<n && c[i]>=i) {
      c[i]=0;
      i++;
    }
    // pulled from inside loop -- the part that makes next permute:
    if(i<n) { // if not done
      if(i%2==0) swap(0,i);
      else swap(c[i], i);
      // "print P" removed. User will simply examine it
      c[i]+=1;
      i=0;
    }
  }

  private void swap(int i1, int i2) {int tmp=P[i1]; P[i1]=P[i2]; P[i2]=tmp;}
}