Algorithm to generate all possible permutations of a list?

Question

Say I have a list of n elements, I know there are n! possible ways to order these elements. What is an algorithm to generate all possible orderings of this list? Example, I have list [a, b, c]. The algorithm would return [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

I'm reading this here http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia has never been good at explaining. I don't understand much of it.

• Joren: I wrote an extensive answer to another question about generating permutations once. I think it'll be of interest to you: stackoverflow.com/questions/1506078/…
• Felix: This can solve your problem en.wikipedia.org/wiki/Heap's_algorithm
• Addem: I wrote a blog post explaining how to generate several different sorts of combinatorial functions. axiomtutor.com/new-blog/2022/8/3/…

Answer 1

Basically, for each item from left to right, all the permutations of the remaining items are generated (and each one is added with the current elements). This can be done recursively (or iteratively if you like pain) until the last item is reached at which point there is only one possible order.

So with the list [1,2,3,4] all the permutations that start with 1 are generated, then all the permutations that start with 2, then 3 then 4.

This effectively reduces the problem from one of finding permutations of a list of four items to a list of three items. After reducing to 2 and then 1 item lists, all of them will be found.
Example showing process permutations using 3 coloured balls:
Red, green and blue coloured balls ordered permutations image (from https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)

• fent: I thought about this at first too but then the current element wouldn't get put in between some of the following. So not all permutations would be generated.
• WhirlWind: @LLer sorry, updated my answer from "folllowing" to "remaining" to clarify. It works fine though. Check it by writing the code and verifying that you get 4! different results.
• Somesh: int permutations(int n, vector<int> a) { static int num_permutations=0; if (n==(a.size() - 1)) { for (int i=0; i<a.size(); i++) cout<<a[i]<<" "; cout<<"\n"; num_permutations++; } else { for (int i=n+1; i<=a.size(); i++) { permutations(n+1, a); if (i<a.size()) int temp=a[n], a[n]=a[i], a[i]=temp; } } return num_permutations; } int main(void) { vector<int> v; v.push_back(1); ... return permutations(0, v); }
• Somesh: Oops - not sure how to format the code in a comment ... Tested the code with 7 and got 5040. Thanks to @WhirlWind for the suggestion.
• Alexander Mills: doesnt this algo change if you can have 2 or 3 red #1 balls, instead of only 1 of each color?

Answer 2

Here is an algorithm in Python that works by in place on an array:

def permute(xs, low=0):
 if low + 1 >= len(xs):
 yield xs
 else:
 for p in permute(xs, low + 1):
 yield p 
 for i in range(low + 1, len(xs)): 
 xs[low], xs[i] = xs[i], xs[low]
 for p in permute(xs, low + 1):
 yield p 
 xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
 print p

You can try the code out for yourself here: http://repl.it/J9v

• Agniswar Bakshi: Can you please explain the yield part ? I could not dry run the code. Thanks in advance.
• Edward: The Stack Overflow question at stackoverflow.com/questions/104420/… states there is a standard library module in versions 2.6 onwards and has an answer providing a 6 line solution in a function to get list permutations.
• MSS: @Agniswar At a glance, the yield statement is used to define generators, replacing the return of a function to provide a result to its caller without destroying local variables. Unlike a function, where on each call it starts with new set of variables, a generator will resume the execution where it was left off. pythoncentral.io/python-generators-and-yield-keyword
• KaiserKatze: This solution won't work when handling a list of identical entries.
• Sam: Thanks for sharing. This is intuitive and efficient, though the output is not in lexicographical order.

Answer 3

There is already plenty of good solutions here, but I would like to share how I solved this problem on my own and hope that this might be helpful for somebody who would also like to derive his own solution.

After some pondering about the problem I have come up with two following conclusions:

1. For the list L of size n there will be equal number of solutions starting with L₁, L₂ ... L_n elements of the list. Since in total there are n! permutations of the list of size n, we get n! / n = (n-1)! permutations in each group.
2. The list of 2 elements has only 2 permutations => [a,b] and [b,a].

Using these two simple ideas I have derived the following algorithm:

permute array
 if array is of size 2
 return first and second element as new array
 return second and first element as new array
 else
 for each element in array
 new subarray = array with excluded element
 return element + permute subarray

Here is how I implemented this in C#:

public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
 if (input.Count == 2) // this are permutations of array of size 2
 {
 yield return new List<T>(input);
 yield return new List<T> {input[1], input[0]}; 
 }
 else
 {
 foreach(T elem in input) // going through array
 {
 var rlist = new List<T>(input); // creating subarray = array
 rlist.Remove(elem); // removing element
 foreach(List<T> retlist in Permutate(rlist))
 {
 retlist.Insert(0,elem); // inserting the element at pos 0
 yield return retlist;
 }
 }
 }
}

Answer 4

Wikipedia's answer for "lexicographic order" seems perfectly explicit in cookbook style to me. It cites a 14th century origin for the algorithm!

I've just written a quick implementation in Java of Wikipedia's algorithm as a check and it was no trouble. But what you have in your Q as an example is NOT "list all permutations", but "a LIST of all permutations", so wikipedia won't be a lot of help to you. You need a language in which lists of permutations are feasibly constructed. And believe me, lists a few billion long are not usually handled in imperative languages. You really want a non-strict functional programming language, in which lists are a first-class object, to get out stuff while not bringing the machine close to heat death of the Universe.

That's easy. In standard Haskell or any modern FP language:

-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms [] = [ [] ]

and

-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits [] = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]

Answer 5

As WhirlWind said, you start at the beginning.

You swap cursor with each remaining value, including cursor itself, these are all new instances (I used an int[] and array.clone() in the example).

Then perform permutations on all these different lists, making sure the cursor is one to the right.

When there are no more remaining values (cursor is at the end), print the list. This is the stop condition.

public void permutate(int[] list, int pointer) {
 if (pointer == list.length) {
 //stop-condition: print or process number
 return;
 }
 for (int i = pointer; i < list.length; i++) {
 int[] permutation = (int[])list.clone();.
 permutation[pointer] = list[i];
 permutation[i] = list[pointer];
 permutate(permutation, pointer + 1);
 }
}

Answer 6

Recursive always takes some mental effort to maintain. And for big numbers, factorial is easily huge and stack overflow will easily be a problem.

For small numbers (3 or 4, which is mostly encountered), multiple loops are quite simple and straight forward. It is unfortunate answers with loops didn't get voted up.

Let's start with enumeration (rather than permutation). Simply read the code as pseudo perl code.

$foreach $i1 in @list
 $foreach $i2 in @list 
 $foreach $i3 in @list
 print "$i1, $i2, $i3\n"

Enumeration is more often encountered than permutation, but if permutation is needed, just add the conditions:

$foreach $i1 in @list
 $foreach $i2 in @list 
 $if $i2==$i1
 next
 $foreach $i3 in @list
 $if $i3==$i1 or $i3==$i2
 next
 print "$i1, $i2, $i3\n"

Now if you really need general method potentially for big lists, we can use radix method. First, consider the enumeration problem:

$n=@list
my @radix
$for $i=0:$n
 $radix[$i]=0
$while 1
 my @temp
 $for $i=0:$n
 push @temp, $list[$radix[$i]]
 print join(", ", @temp), "\n"
 $call radix_increment
subcode: radix_increment
 $i=0
 $while 1
 $radix[$i]++
 $if $radix[$i]==$n
 $radix[$i]=0
 $i++
 $else
 last
 $if $i>=$n
 last

Radix increment is essentially number counting (in the base of number of list elements).

Now if you need permutaion, just add the checks inside the loop:

subcode: check_permutation
 my @check
 my $flag_dup=0
 $for $i=0:$n
 $check[$radix[$i]]++
 $if $check[$radix[$i]]>1
 $flag_dup=1
 last
 $if $flag_dup
 next

Edit: The above code should work, but for permutation, radix_increment could be wasteful. So if time is a practical concern, we have to change radix_increment into permute_inc:

subcode: permute_init
 $for $i=0:$n
 $radix[$i]=$i
subcode: permute_inc 
 $max=-1 
 $for $i=$n:0 
 $if $max<$radix[$i] 
 $max=$radix[$i] 
 $else 
 $for $j=$n:0 
 $if $radix[$j]>$radix[$i] 
 $call swap, $radix[$i], $radix[$j] 
 break 
 $j=$i+1 
 $k=$n-1 
 $while $j<$k 
 $call swap, $radix[$j], $radix[$k] 
 $j++ 
 $k-- 
 break 
 $if $i<0 
 break 

Of course now this code is logically more complex, I'll leave for reader's exercise.

Answer 7

If anyone wonders how to be done in permutation in javascript.

Idea/pseudocode

1. pick one element at a time
2. permute rest of the element and then add the picked element to the all of the permutation

for example. 'a'+ permute(bc). permute of bc would be bc & cb. Now add these two will give abc, acb. similarly, pick b + permute (ac) will provice bac, bca...and keep going.

now look at the code

function permutations(arr){
 var len = arr.length, 
 perms = [],
 rest,
 picked,
 restPerms,
 next;
 //for one or less item there is only one permutation 
 if (len <= 1)
 return [arr];
 for (var i=0; i<len; i++)
 {
 //copy original array to avoid changing it while picking elements
 rest = Object.create(arr);
 //splice removed element change array original array(copied array)
 //[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
 picked = rest.splice(i, 1);
 //get the permutation of the rest of the elements
 restPerms = permutations(rest);
 // Now concat like a+permute(bc) for each
 for (var j=0; j<restPerms.length; j++)
 {
 next = picked.concat(restPerms[j]);
 perms.push(next);
 }
 }
 return perms;
}

Take your time to understand this. I got this code from (pertumation in JavaScript)

• BisonAVC: I was thinking of something similar but should you not be adding the picked element both to the front and end of the restParams? In this case, for 'abc', if you pick out a, then 'bc' permutations are 'bc' and 'cb'. When you add 'a' back to the list, shouldn't you add it to the front as 'a+bc' + 'a+cb' but also at the end as 'bc+a' + 'cb+a' of the list?
• Ryan O'Neill: You'll get those permutations when you permute starting with 'b' and 'c' respectively. (i.e. the second and third runs of the outer 'for' loop)

Answer 8

I have written this recursive solution in ANSI C. Each execution of the Permutate function provides one different permutation until all are completed. Global variables can also be used for variables fact and count.

#include <stdio.h>
#define SIZE 4
void Rotate(int vec[], int size)
{
 int i, j, first;
 first = vec[0];
 for(j = 0, i = 1; i < size; i++, j++)
 {
 vec[j] = vec[i];
 }
 vec[j] = first;
}
int Permutate(int *start, int size, int *count)
{
 static int fact;
 if(size > 1)
 {
 if(Permutate(start + 1, size - 1, count))
 {
 Rotate(start, size);
 }
 fact *= size;
 }
 else
 {
 (*count)++;
 fact = 1;
 }
 return !(*count % fact);
}
void Show(int vec[], int size)
{
 int i;
 printf("%d", vec[0]);
 for(i = 1; i < size; i++)
 {
 printf(" %d", vec[i]);
 }
 putchar('\n');
}
int main()
{
 int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
 int count = 0;
 do
 {
 Show(vec, SIZE);
 } while(!Permutate(vec, SIZE, &count));
 putchar('\n');
 Show(vec, SIZE);
 printf("\nCount: %d\n\n", count);
 return 0;
}

Answer 9

Another one in Python, it's not in place as @cdiggins's, but I think it's easier to understand

def permute(num):
 if len(num) == 2:
 # get the permutations of the last 2 numbers by swapping them
 yield num
 num[0], num[1] = num[1], num[0]
 yield num
 else:
 for i in range(0, len(num)):
 # fix the first number and get the permutations of the rest of numbers
 for perm in permute(num[0:i] + num[i+1:len(num)]):
 yield [num[i]] + perm
for p in permute([1, 2, 3, 4]):
 print p

Answer 10

I was thinking of writing a code for getting the permutations of any given integer of any size, i.e., providing a number 4567 we get all possible permutations till 7654...So i worked on it and found an algorithm and finally implemented it, Here is the code written in "c". You can simply copy it and run on any open source compilers. But some flaws are waiting to be debugged. Please appreciate.

Code:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
 //PROTOTYPES
int fact(int); //For finding the factorial
void swap(int*,int*); //Swapping 2 given numbers
void sort(int*,int); //Sorting the list from the specified path
int imax(int*,int,int); //Finding the value of imax
int jsmall(int*,int); //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm(); //All the important tasks are done in this function
int n; //Global variable for input OR number of digits
void main()
{
int c=0;
printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}
void perm(int c){
int *p; //Pointer for allocating separate memory to every single entered digit like arrays
int i, d; 
int sum=0;
int j, k;
long f;
n = 0;
while(c != 0) //this one is for calculating the number of digits in the entered number
{
 sum = (sum * 10) + (c % 10);
 n++; //as i told at the start of loop
 c = c / 10;
}
f = fact(n); //It gives the factorial value of any number
p = (int*) malloc(n*sizeof(int)); //Dynamically allocation of array of n elements
for(i=0; sum != 0 ; i++)
{
 *(p+i) = sum % 10; //Giving values in dynamic array like 1234....n separately
 sum = sum / 10;
}
sort(p,-1); //For sorting the dynamic array "p"
for(c=0 ; c<f/2 ; c++) { //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)
 for(k=0 ; k<n ; k++)
 printf("%d",p[k]); //Loop for printing one of permutations
 printf("\n");
 i = d = 0;
 i = imax(p,i,d); //provides the max i as per algo (i am restricted to this only)
 j = i;
 j = jsmall(p,j); //provides smallest i val as per algo
 swap(&p[i],&p[j]);
 for(k=0 ; k<n ; k++)
 printf("%d",p[k]);
 printf("\n");
 i = d = 0;
 i = imax(p,i,d);
 j = i;
 j = jsmall(p,j);
 swap(&p[i],&p[j]);
 sort(p,i);
}
free(p); //Deallocating memory
}
int fact (int a)
{
long f=1;
while(a!=0)
{
 f = f*a;
 a--;
}
return f;
}
void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}
void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
 for(j=i+1 ; j<n ; j++)
 {
 if(*(p+i) > *(p+j))
 {
 temp = *(p+i);
 *(p+i) = *(p+j);
 *(p+j) = temp;
 }
 }
}
}
int imax(int *p, int i , int d)
{
 while(i<n-1 && d<n-1)
{
 if(*(p+d) < *(p+d+1))
 { 
 i = d;
 d++;
 }
 else
 d++;
}
return i;
}
int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
 if (p[i]<small && p[i]>p[k])
 { 
 small = p[i];
 j = i;
 }
}
return j;
}

Answer 11

void permutate(char[] x, int i, int n){
 x=x.clone();
 if (i==n){
 System.out.print(x);
 System.out.print(" ");
 counter++;}
 else
 {
 for (int j=i; j<=n;j++){
 // System.out.print(temp); System.out.print(" "); //Debugger
 swap (x,i,j);
 // System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
 permutate(x,i+1,n);
 // swap (temp,i,j);
 }
 }
}
void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}

I created this one. based on research too permutate(qwe, 0, qwe.length-1); Just so you know, you can do it with or without backtrack

Answer 12

Here's a toy Ruby method that works like #permutation.to_a that might be more legible to crazy people. It's hella slow, but also 5 lines.

def permute(ary)
 return [ary] if ary.size <= 1
 ary.collect_concat.with_index do |e, i|
 rest = ary.dup.tap {|a| a.delete_at(i) }
 permute(rest).collect {|a| a.unshift(e) }
 end
end

Answer 13

Java version

/**
 * @param uniqueList
 * @param permutationSize
 * @param permutation
 * @param only Only show the permutation of permutationSize,
 * else show all permutation of less than or equal to permutationSize.
 */
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
 if (permutation == null) {
 assert 0 < permutationSize && permutationSize <= uniqueList.size();
 permutation = new ArrayList<>(permutationSize);
 if (!only) {
 System.out.println(Arrays.toString(permutation.toArray()));
 }
 }
 for (int i : uniqueList) {
 if (permutation.contains(i)) {
 continue;
 }
 permutation.add(i);
 if (!only) {
 System.out.println(Arrays.toString(permutation.toArray()));
 } else if (permutation.size() == permutationSize) {
 System.out.println(Arrays.toString(permutation.toArray()));
 }
 if (permutation.size() < permutationSize) {
 my_permutationOf(uniqueList, permutationSize, permutation, only);
 }
 permutation.remove(permutation.size() - 1);
 }
}

E.g.

public static void main(String[] args) throws Exception { 
 my_permutationOf(new ArrayList<Integer>() {
 {
 add(1);
 add(2);
 add(3);
 }
 }, 3, null, true);
}

output:

 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

Answer 14

in PHP

$set=array('A','B','C','D');
function permutate($set) {
 $b=array();
 foreach($set as $key=>$value) {
 if(count($set)==1) {
 $b[]=$set[$key];
 }
 else {
 $subset=$set;
 unset($subset[$key]);
 $x=permutate($subset);
 foreach($x as $key1=>$value1) {
 $b[]=$value.' '.$value1;
 }
 }
 }
 return $b;
}
$x=permutate($set);
var_export($x);

Answer 15

this is a java version for permutation

public class Permutation {
 static void permute(String str) {
 permute(str.toCharArray(), 0, str.length());
 }
 static void permute(char [] str, int low, int high) {
 if (low == high) {
 System.out.println(str);
 return;
 }
 for (int i=low; i<high; i++) {
 swap(str, i, low);
 permute(str, low+1, high);
 swap(str, low, i);
 }
 }
 static void swap(char [] array, int i, int j) {
 char t = array[i];
 array[i] = array[j];
 array[j] = t;
 }
}

Answer 16

Here is the code in Python to print all possible permutations of a list:

def next_perm(arr):
 # Find non-increasing suffix
 i = len(arr) - 1
 while i > 0 and arr[i - 1] >= arr[i]:
 i -= 1
 if i <= 0:
 return False
 # Find successor to pivot
 j = len(arr) - 1
 while arr[j] <= arr[i - 1]:
 j -= 1
 arr[i - 1], arr[j] = arr[j], arr[i - 1]
 # Reverse suffix
 arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
 print arr
 return True
def all_perm(arr):
 a = next_perm(arr)
 while a:
 a = next_perm(arr)
 arr = raw_input()
 arr.split(' ')
 arr = map(int, arr)
 arr.sort()
 print arr
 all_perm(arr)

I have used a lexicographic order algorithm to get all possible permutations, but a recursive algorithm is more efficient. You can find the code for recursive algorithm here: Python recursion permutations

Answer 17

public class PermutationGenerator
{
 private LinkedList<List<int>> _permutationsList;
 public void FindPermutations(List<int> list, int permutationLength)
 {
 _permutationsList = new LinkedList<List<int>>();
 foreach(var value in list)
 {
 CreatePermutations(value, permutationLength);
 }
 }
 private void CreatePermutations(int value, int permutationLength)
 {
 var node = _permutationsList.First;
 var last = _permutationsList.Last;
 while (node != null)
 {
 if (node.Value.Count < permutationLength)
 {
 GeneratePermutations(node.Value, value, permutationLength);
 }
 if (node == last)
 {
 break;
 }
 node = node.Next;
 }
 List<int> permutation = new List<int>();
 permutation.Add(value);
 _permutationsList.AddLast(permutation);
 }
 private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
 {
 if (permutation.Count < permutationLength)
 {
 List<int> copyOfInitialPermutation = new List<int>(permutation);
 copyOfInitialPermutation.Add(value);
 _permutationsList.AddLast(copyOfInitialPermutation);
 List<int> copyOfPermutation = new List<int>();
 copyOfPermutation.AddRange(copyOfInitialPermutation);
 int lastIndex = copyOfInitialPermutation.Count - 1;
 for (int i = lastIndex;i > 0;i--)
 {
 int temp = copyOfPermutation[i - 1];
 copyOfPermutation[i - 1] = copyOfPermutation[i];
 copyOfPermutation[i] = temp;
 List<int> perm = new List<int>();
 perm.AddRange(copyOfPermutation);
 _permutationsList.AddLast(perm);
 }
 }
 }
 public void PrintPermutations(int permutationLength)
 {
 int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
 Console.WriteLine("The number of permutations is " + count);
 }
}

• Ayaz Alifov: it is a useful answer

Answer 18

In Scala

 def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)
def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {
 var result: List[List[Int]] = Nil
 for (i ← n if (!(acc contains (i))))
 if (acc.size == n.size-1)
 result = (i :: acc) :: result
 else
 result = result ::: permutationeAcc(n, i :: acc)
 result
}

Answer 19

Here's an implementation for ColdFusion (requires CF10 because of the merge argument to ArrayAppend() ):

public array function permutateArray(arr){
 if (not isArray(arguments.arr) ) {
 return ['The ARR argument passed to the permutateArray function is not of type array.']; 
 }
 var len = arrayLen(arguments.arr);
 var perms = [];
 var rest = [];
 var restPerms = [];
 var rpLen = 0;
 var next = [];
 //for one or less item there is only one permutation 
 if (len <= 1) {
 return arguments.arr;
 }
 for (var i=1; i <= len; i++) {
 // copy the original array so as not to change it and then remove the picked (current) element
 rest = arraySlice(arguments.arr, 1);
 arrayDeleteAt(rest, i);
 // recursively get the permutation of the rest of the elements
 restPerms = permutateArray(rest);
 rpLen = arrayLen(restPerms);
 // Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
 for (var j=1; j <= rpLen; j++) {
 // for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
 next = arraySlice(arguments.arr, i, 1);
 arrayAppend(next, restPerms[j], true);
 arrayAppend(perms, next);
 }
 }
 return perms;
}

Based on KhanSharp's js solution above.

• Richard: Some explanation of the overall strategy of your algorithm would be a good way to improve this answer.
• earachefl: So why the downvote? This is a working implementation.
• earachefl: @Richard, the overall strategy has been explained above by Whirlwind and others. I don't see your comment on all the other answers posted as implementations without explanations.

Answer 20

I know this a very very old and even off-topic in today's stackoverflow but I still wanted to contribute a friendly javascript answer for the simple reason that it runs in your browser.

I've also added the debugger directive breakpoint so you can step through the code (chrome required) to see how this algorithm works. Open up your dev console in chrome (F12 in windows or CMD + OPTION + I on mac) and then click "Run code snippet". This implements the same exact algorithm that @WhirlWind presented in his answer.

Your browser should pause execution at the debugger directive. Use F8 to continue code execution.

Step through the code and see how it works!

function permute(rest, prefix = []) {
 if (rest.length === 0) {
 return [prefix];
 }
 return (rest
 .map((x, index) => {
 const oldRest = rest;
 const oldPrefix = prefix;
 // the `...` destructures the array into single values flattening it
 const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
 const newPrefix = [...prefix, x];
 debugger;
 const result = permute(newRest, newPrefix);
 return result;
 })
 // this step flattens the array of arrays returned by calling permute
 .reduce((flattened, arr) => [...flattened, ...arr], [])
 );
}
console.log(permute([1, 2, 3]));

Answer 21

In the following Java solution we take advantage over the fact that Strings are immutable in order to avoid cloning the result-set upon every iteration.

The input will be a String, say "abc", and the output will be all the possible permutations:

abc
acb
bac
bca
cba
cab

Code:

public static void permute(String s) {
 permute(s, 0);
}
private static void permute(String str, int left){
 if(left == str.length()-1) {
 System.out.println(str);
 } else {
 for(int i = left; i < str.length(); i++) {
 String s = swap(str, left, i);
 permute(s, left+1);
 }
 }
}
private static String swap(String s, int left, int right) {
 if (left == right)
 return s;
 String result = s.substring(0, left);
 result += s.substring(right, right+1);
 result += s.substring(left+1, right);
 result += s.substring(left, left+1);
 result += s.substring(right+1);
 return result;
}

Same approach can be applied to arrays (instead of a string):

public static void main(String[] args) {
 int[] abc = {1,2,3};
 permute(abc, 0);
}
public static void permute(int[] arr, int index) {
 if (index == arr.length) {
 System.out.println(Arrays.toString(arr));
 } else {
 for (int i = index; i < arr.length; i++) {
 int[] permutation = arr.clone();
 permutation[index] = arr[i];
 permutation[i] = arr[index];
 permute(permutation, index + 1);
 }
 }
}

Answer 22

It's my solution on Java:

public class CombinatorialUtils {
 public static void main(String[] args) {
 List<String> alphabet = new ArrayList<>();
 alphabet.add("1");
 alphabet.add("2");
 alphabet.add("3");
 alphabet.add("4");
 for (List<String> strings : permutations(alphabet)) {
 System.out.println(strings);
 }
 System.out.println("-----------");
 for (List<String> strings : combinations(alphabet)) {
 System.out.println(strings);
 }
 }
 public static List<List<String>> combinations(List<String> alphabet) {
 List<List<String>> permutations = permutations(alphabet);
 List<List<String>> combinations = new ArrayList<>(permutations);
 for (int i = alphabet.size(); i > 0; i--) {
 final int n = i;
 combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
 }
 return combinations;
 }
 public static <T> List<List<T>> permutations(List<T> alphabet) {
 ArrayList<List<T>> permutations = new ArrayList<>();
 if (alphabet.size() == 1) {
 permutations.add(alphabet);
 return permutations;
 } else {
 List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
 T addedElem = alphabet.get(0);
 for (int i = 0; i < alphabet.size(); i++) {
 for (List<T> permutation : subPerm) {
 int index = i;
 permutations.add(new ArrayList<T>(permutation) {{
 add(index, addedElem);
 }});
 }
 }
 }
 return permutations;
 }
}

Answer 23

You can't really talk about solving a permultation problem in recursion without posting an implementation in a (dialect of) language that pioneered the idea. So, for the sake of completeness, here is one of the ways that can be done in Scheme.

(define (permof wd)
 (cond ((null? wd) '())
 ((null? (cdr wd)) (list wd))
 (else
 (let splice ([l '()] [m (car wd)] [r (cdr wd)])
 (append
 (map (lambda (x) (cons m x)) (permof (append l r)))
 (if (null? r)
 '()
 (splice (cons m l) (car r) (cdr r))))))))

calling (permof (list "foo" "bar" "baz")) we'll get:

'(("foo" "bar" "baz")
 ("foo" "baz" "bar")
 ("bar" "foo" "baz")
 ("bar" "baz" "foo")
 ("baz" "bar" "foo")
 ("baz" "foo" "bar"))

I won't go into the algorithm details because it's been explained enough in other posts. The idea is the same.

However, recursive problems tend to be much harder to model and think about in destructive medium like Python, C, and Java, while in Lisp or ML it can be concisely expressed.

Answer 24

Had come up with these two ways (one iterative and the other recursive) during my freshman year at college. They are implemented in Python3:

Efficient Iterative Algorithm:

input_string = input("Enter a string: ")
size = len(input_string)
count = 1
next_permutation = sorted(list(input_string))
while (True):
 print(count, "".join(next_permutation))
 pivot_idx = -2
 while (pivot_idx >= -size and next_permutation[pivot_idx] >= next_permutation[pivot_idx + 1]):
 pivot_idx -= 1
 if (not pivot_idx < -size):
 count += 1
 crnt_sctn = sorted(next_permutation[pivot_idx:])
 crnt_sctn_size = len(crnt_sctn)
 pivot = next_permutation[pivot_idx]
 new_pivot_idx = -sorted(crnt_sctn, reverse = True).index(pivot)
 new_pivot = crnt_sctn.pop(new_pivot_idx)
 new_sctn = [new_pivot,]
 new_sctn.extend(crnt_sctn)
 next_permutation[pivot_idx:] = new_sctn
 else:
 break

Much Less Efficient Recursive Algorithm:

x = input("Enter the string: ")
count = 1
for i in permute_recursively(sorted(list(x))):
 print(count, ''.join(i))
 count += 1
def permute_recursively(inp_list):
 if (len(inp_list) == 1):
 return [inp_list]
 else:
 x = permute_recursively(inp_list[1:])
 a = inp_list[0]
 z = []
 for i in x:
 for k in range(len(i) + 1):
 z.append(i[:k] + [a] + i[k:])
 return(z)

Characteristics of the first, iterative algorithm:

• Very Efficient.

• Usable for inputs of literally any length (if you have enough time).

• Generates permutations in lexicographical order according to the ASCII values of the characters.

• Uses virtually no memory.

• Automatically skips over duplicates

• [The laTeX output of the HTML code snippet at the end] is the number of sequences generated, where n_t is the number of characters in the input, n_e is the number of unique characters that are repeated, and n_i is the number of repetitions of each of those unique characters respectively.

The second algorithm is recursive:

• Much less efficient.
• Cannot be used for inputs of lengths beyond a certain limit because of the practical recursion depth limitations and larger and larger memory consumption with each additional character.
• Generates duplicates
• Doesn't generate permutations in lexicographical order.
• Generates exactly n! outputs.

<!DOCTYPE html>
<html>
<head>
 <meta charset="utf-8">
 <meta name="viewport" content="width=device-width, initial-scale=1.0">
 <title>Welcome file</title>
 <link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>
<body class="stackedit">
 <div class="stackedit__html" style="font-size: 56px">
 <p><span class="katex--inline"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mrow><msub><mi>n</mi><mi>t</mi></msub><mo stretchy="false">!</mo></mrow><mrow><msubsup><mi mathvariant="normal">Π</mi><mi>i</mi><msub><mi>n</mi><mi>e</mi></msub></msubsup><mo stretchy="false">(</mo><msub><mi>n</mi><mi>i</mi></msub><mo stretchy="false">!</mo><mo stretchy="false">)</mo></mrow></mfrac></mrow><annotation encoding="application/x-tex">\frac{n_t!}{\Pi_{i}^{n_e}({n_i}!)}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 1.48845em; vertical-align: -0.59224em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.896208em;"><span class="" style="top: -2.63336em;"><span class="pstrut" style="height: 3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mtight">Π</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.7952em;"><span class="" style="top: -2.17771em; margin-left: 0em; margin-right: 0.0714286em;"><span class="pstrut" style="height: 2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="" style="top: -2.98766em; margin-right: 0.0714286em;"><span class="pstrut" style="height: 2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.23056em;"><span class="" style="top: -2.3em; margin-left: 0em; margin-right: 0.1em;"><span class="pstrut" style="height: 2.5em;"></span><span class="mord mathnormal mtight">e</span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.2em;"><span class=""></span></span></span></span></span></span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.322286em;"><span class=""></span></span></span></span></span></span><span class="mopen mtight">(</span><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.328086em;"><span class="" style="top: -2.357em; margin-left: 0em; margin-right: 0.0714286em;"><span class="pstrut" style="height: 2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.143em;"><span class=""></span></span></span></span></span></span></span><span class="mclose mtight">!)</span></span></span></span><span class="" style="top: -3.23em;"><span class="pstrut" style="height: 3em;"></span><span class="frac-line" style="border-bottom-width: 0.04em;"></span></span><span class="" style="top: -3.4101em;"><span class="pstrut" style="height: 3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.296343em;"><span class="" style="top: -2.357em; margin-left: 0em; margin-right: 0.0714286em;"><span class="pstrut" style="height: 2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mathnormal mtight">t</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.143em;"><span class=""></span></span></span></span></span></span><span class="mclose mtight">!</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.59224em;"><span class=""></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span></span></p>
 </div>
</body>
</html>

Answer 25

Here is a recursive solution in PHP. WhirlWind's post accurately describes the logic. It's worth mentioning that generating all permutations runs in factorial time, so it might be a good idea to use an iterative approach instead.

public function permute($sofar, $input){
 for($i=0; $i < strlen($input); $i++){
 $diff = strDiff($input,$input[$i]);
 $next = $sofar.$input[$i]; //next contains a permutation, save it
 $this->permute($next, $diff);
 }
}

The strDiff function takes two strings, s1 and s2, and returns a new string with everything in s1 without elements in s2 (duplicates matter). So, strDiff('finish','i') => 'fnish' (the second 'i' is not removed).

Answer 26

Here is an algorithm in R, in case anyone needs to avoid loading additional libraries like I had to.

permutations <- function(n){
 if(n==1){
 return(matrix(1))
 } else {
 sp <- permutations(n-1)
 p <- nrow(sp)
 A <- matrix(nrow=n*p,ncol=n)
 for(i in 1:n){
 A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
 }
 return(A)
 }
}

Example usage:

> matrix(letters[permutations(3)],ncol=3)
 [,1] [,2] [,3]
[1,] "a" "b" "c" 
[2,] "a" "c" "b" 
[3,] "b" "a" "c" 
[4,] "b" "c" "a" 
[5,] "c" "a" "b" 
[6,] "c" "b" "a" 

Answer 27

#!/usr/bin/env python
import time
def permutations(sequence):
 # print sequence
 unit = [1, 2, 1, 2, 1]
 if len(sequence) >= 4:
 for i in range(4, (len(sequence) + 1)):
 unit = ((unit + [i - 1]) * i)[:-1]
 # print unit
 for j in unit:
 temp = sequence[j]
 sequence[j] = sequence[0]
 sequence[0] = temp
 yield sequence
 else:
 print 'You can use PEN and PAPER'
# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']
print s
z = permutations(s)
try:
 while True:
 # time.sleep(0.0001)
 print next(z)
except StopIteration:
 print 'Done'

---

['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']

• Rahul Kadukar: The solution shows that you have not permuted the string as per the requirement. The second permutation should have been PYTHNO

Answer 28

Just to be complete, C++

#include <iostream>
#include <algorithm>
#include <string>
std::string theSeq = "abc";
do
{
 std::cout << theSeq << endl;
} 
while (std::next_permutation(theSeq.begin(), theSeq.end()));

...

abc
acb
bac
bca
cab
cba

Answer 29

Here is a non-recursive solution in C++ that provides the next permutation in ascending order, similarly to the functionality provided by std::next_permutation:

void permute_next(vector<int>& v)
{
 if (v.size() < 2)
 return;
 if (v.size() == 2)
 { 
 int tmp = v[0];
 v[0] = v[1];
 v[1] = tmp;
 return;
 }
 // Step 1: find first ascending-ordered pair from right to left
 int i = v.size()-2;
 while(i>=0)
 { 
 if (v[i] < v[i+1])
 break;
 i--;
 }
 if (i<0) // vector fully sorted in descending order (last permutation)
 {
 //resort in ascending order and return
 sort(v.begin(), v.end());
 return;
 }
 // Step 2: swap v[i] with next higher element of remaining elements
 int pos = i+1;
 int val = v[pos];
 for(int k=i+2; k<v.size(); k++)
 if(v[k] < val && v[k] > v[i])
 {
 pos = k;
 val = v[k];
 }
 v[pos] = v[i];
 v[i] = val;
 // Step 3: sort remaining elements from i+1 ... end
 sort(v.begin()+i+1, v.end());
}

Answer 30

In C, create a single matrix (unsigned char) to quickly and easily access all permutations from 1 to 6. Based on code from https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/.

void swap(unsigned char* a, unsigned char* b)
{
 unsigned char t;
 t = *b;
 *b = *a;
 *a = t;
}
void print_permutations(unsigned char a[], unsigned char n)
{
 // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
 for (int i = 0; i < n; i++)
 {
 assert(a[i] < n);
 printf("%d ", a[i]);
 }
 printf("\n");
}
// Generating permutation using Heap Algorithm 
void generate_permutations(unsigned char (**permutations)[6], unsigned char a[], int size, int n)
{
 // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
 // if size becomes 1 then prints the obtained permutation 
 if (size == 1)
 {
 memcpy(*permutations, a, n);
 *permutations += 1;
 }
 else
 {
 for (int i = 0; i < size; i++)
 {
 generate_permutations(permutations, a, size - 1, n);
 // if size is odd, swap first and last element
 if (size & 1)
 swap(a, a + size - 1);
 // If size is even, swap ith and last element
 else
 swap(a + i, a + size - 1);
 }
 }
}
int main()
{
 unsigned char permutations[720][6]; // easily access all permutations from 1 to 6
 unsigned char suit_length_indexes[] = { 0, 1, 2, 3, 4, 5 };
 assert(sizeof(suit_length_indexes) == sizeof(permutations[0]));
 unsigned char(*p)[sizeof(suit_length_indexes)] = permutations;
 generate_permutations(&p, suit_length_indexes, sizeof(suit_length_indexes), sizeof(suit_length_indexes));
 for (int i = 0; i < sizeof(permutations) / sizeof(permutations[0]); i++)
 print_permutations(permutations[i], sizeof(suit_length_indexes));
 return 0;
}