Generating all permutations of a given string

Based on Mark Byers' answer i came up with this solution:

JAVA

public class Main { public static void main(String[] args) { myPerm("ABCD", 0); } private static void myPerm(String str, int index) { if (index == str.length()) System.out.println(str); for (int i = index; i < str.length(); i++) { char prefix = str.charAt(i); String suffix = str.substring(0,i) + str.substring(i+1); myPerm(prefix + suffix, index + 1); } } } 

C#

I also wrote the function in C# using the new C# 8.0 range operator

 class Program { static void Main(string[] args) { myPerm("ABCD", 0); } private static void myPerm(string str, int index) { if (index == str.Length) Console.WriteLine(str); for (int i = index; i < str.Length; i++) { char prefix = str[i]; string suffix = str[0..i] + str[(i + 1)..]; myPerm(prefix + suffix, index + 1); } } 

We just put every letter at the beginning and then permute.
The first iteration looks like this:

/* myPerm("ABCD",0) prefix = "A" suffix = "BCD" myPerm("ABCD",1) prefix = "B" suffix = "ACD" myPerm("BACD",2) prefix = "C" suffix = "BAD" myPerm("CBAD",3) prefix = "D" suffix = "CBA" myPerm("DCBA",4) Console.WriteLine("DCBA") */ 

public class StringPermutation { // Function to print all the permutations of str static void printPermutn(String str, String ans) { // If string is empty if (str.length() == 0) { System.out.print(ans + " "); return; } for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // Recurvise call printPermutn(ros, ans + ch); } } public static void main(String[] args) { String s = "ABC"; printPermutn(s, ""); } } 

/* * eg: abc =>{a,bc},{b,ac},{c,ab} * =>{ca,b},{cb,a} * =>cba,cab * =>{ba,c},{bc,a} * =>bca,bac * =>{ab,c},{ac,b} * =>acb,abc */ public void nonRecpermute(String prefix, String word) { String[] currentstr ={prefix,word}; Stack<String[]> stack = new Stack<String[]>(); stack.add(currentstr); while(!stack.isEmpty()) { currentstr = stack.pop(); String currentPrefix = currentstr[0]; String currentWord = currentstr[1]; if(currentWord.equals("")) { System.out.println("Word ="+currentPrefix); } for(int i=0;i<currentWord.length();i++) { String[] newstr = new String[2]; newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i)); newstr[1] = currentWord.substring(0, i); if(i<currentWord.length()-1) { newstr[1] = newstr[1]+currentWord.substring(i+1); } stack.push(newstr); } } } 

This can be done iteratively by simply inserting each letter of the string in turn in all locations of the previous partial results.

We start with [A], which with B becomes [BA, AB], and with C, [CBA, BCA, BAC, CAB, etc].

The running time would be O(n!), which, for the test case ABCD, is 1 x 2 x 3 x 4.

In the above product, the 1 is for A, the 2 is for B, etc.

Dart sample:

void main() { String insertAt(String a, String b, int index) { return a.substring(0, index) + b + a.substring(index); } List<String> Permute(String word) { var letters = word.split(''); var p_list = [ letters.first ]; for (var c in letters.sublist(1)) { var new_list = [ ]; for (var p in p_list) for (int i = 0; i <= p.length; i++) new_list.add(insertAt(p, c, i)); p_list = new_list; } return p_list; } print(Permute("ABCD")); } 

Here is a java implementation:

/* All Permutations of a String */ import java.util.*; import java.lang.*; import java.io.*; /* Complexity O(n*n!) */ class Ideone { public static ArrayList<String> strPerm(String str, ArrayList<String> list) { int len = str.length(); if(len==1){ list.add(str); return list; } list = strPerm(str.substring(0,len-1),list); int ls = list.size(); char ap = str.charAt(len-1); for(int i=0;i<ls;i++){ String temp = list.get(i); int tl = temp.length(); for(int j=0;j<=tl;j++){ list.add(temp.substring(0,j)+ap+temp.substring(j,tl)); } } while(true){ String temp = list.get(0); if(temp.length()<len) list.remove(temp); else break; } return list; } public static void main (String[] args) throws java.lang.Exception { String str = "abc"; ArrayList<String> list = new ArrayList<>(); list = strPerm(str,list); System.out.println("Total Permutations : "+list.size()); for(int i=0;i<list.size();i++) System.out.println(list.get(i)); } } 

http://ideone.com/nWPb3k

This is a C solution:

#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> char* addLetter(char* string, char *c) { char* result = malloc(sizeof(string) + 2); strcpy(result, string); strncat(result, c, 1); return result; } char* removeLetter(char* string, char *c) { char* result = malloc(sizeof(string)); int j = 0; for (int i = 0; i < strlen(string); i++) { if (string[i] != *c) { result[j++] = string[i]; } } result[j] = '\0'; return result; } void makeAnagram(char *anagram, char *letters) { if (*letters == '\0') { printf("%s\n", anagram); return; } char *c = letters; while (*c != '\0') { makeAnagram(addLetter(anagram, c), removeLetter(letters, c)); c++; } } int main() { makeAnagram("", "computer"); return 0; } 

In python anyway

def perms(in_str, prefix=""): if not len(in_str) : print(prefix) else: for i in range(0, len(in_str)): perms(in_str[:i] + in_str[i + 1:], prefix + in_str[i]) perms('ASD') 

Here is algorithm with O(n!) time complexity with pure recursion and intuitive .

public class words { static String combinations; public static List<String> arrlist=new ArrayList<>(); public static void main(String[] args) { words obj = new words(); String str="premandl"; obj.getcombination(str, str.length()-1, ""); System.out.println(arrlist); } public void getcombination(String str, int charIndex, String output) { if (str.length() == 0) { arrlist.add(output); return ; } if (charIndex == -1) { return ; } String character = str.toCharArray()[charIndex] + ""; getcombination(str, --charIndex, output); String remaining = ""; output = output + character; remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2); getcombination(remaining, remaining.length() - 1, output); } 

}

Using Set operations to model "selections depending on other selections" is much easier to understand dependent permutations
With dependent permutation, available selections reduce as positions are filled with selected characters from left to right. Terminal condition for recursive calls is to test if the set of available selections is empty. When terminal condition is met, a permutation is complete and it is stored to 'results' List.

public static List<String> stringPermutation(String s) { List<String> results = new ArrayList<>(); Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet()); stringPermutation(charSet, "", results); return results; } private static void stringPermutation(Set<Character> charSet, String prefix, List<String> results) { if (charSet.isEmpty()) { results.add(prefix); return; } for (Character c : charSet) { Set<Character> newSet = new HashSet<>(charSet); newSet.remove(c); stringPermutation(newSet, prefix + c, results); } } 

The code can be generalized to find permutations for a set of objects. In this case, I use a set of colors.

public enum Color{ ORANGE,RED,BULE,GREEN,YELLOW; } public static List<List<Color>> colorPermutation(Set<Color> colors) { List<List<Color>> results = new ArrayList<>(); List<Color> prefix = new ArrayList<>(); permutation(colors, prefix, results); return results; } private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) { if (set.isEmpty()) { results.add(prefix); return; } for (T t : set) { Set<T> newSet = new HashSet<>(set); List<T> newPrefix = new ArrayList<>(prefix); newSet.remove(t); newPrefix.add(t); permutation(newSet, newPrefix, results); } } 

Code for tests.

public static void main(String[] args) { List<String> stringPerm = stringPermutation("abcde"); System.out.println("# of permutations:" + stringPerm.size()); stringPerm.stream().forEach(e -> System.out.println(e)); Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet()); List<List<Color>> colorPerm = colorPermutation(colorSet); System.out.println("# of permutations:" + colorPerm.size()); colorPerm.stream().forEach(e -> System.out.println(e)); } 

Adding a more detailed NcK/NcR for both permutations and combinations

public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) { if (chooseCount == 0) resultList.add(prefix); else { for (int i = 0; i < inputList.size(); i++) combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList); // Finally print once all combinations are done if (prefix.equalsIgnoreCase("")) { resultList.stream().map(str -> str.substring(1)).forEach(System.out::println); } } } public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) { for (int count = 0; count < inputList.size(); count++) { permNcK(inputList, "", chooseCount, resultList); resultList = new ArrayList<String>(); Collections.rotate(inputList, 1); System.out.println("-------------------------"); } } public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) { if (chooseCount == 0) resultList.add(prefix); else { for (int i = 0; i < inputList.size(); i++) combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList); // Finally print once all combinations are done if (prefix.equalsIgnoreCase("")) { resultList.stream().map(str -> str.substring(1)).forEach(System.out::println); } } } public static void main(String[] args) { List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" }); List<String> resultList = new ArrayList<String>(); //combinationNcK(positions, "", 3, resultList); permNcK(positions, 3, resultList); } 

This is can be easily done using bit manipulation. "As we all know there are 2N possible subsets of any given set with N elements. What if we represent each element in a subset with a bit. A bit can be either 0 or 1, thus we can use this to denote whether the corresponding element belongs to this given subset or not. So each bit pattern will represent a subset." [Copied text]

private void getPermutation(String str) { if(str==null) return; Set<String> StrList = new HashSet<String>(); StringBuilder strB= new StringBuilder(); for(int i = 0;i < (1 << str.length()); ++i) { strB.setLength(0); //clear the StringBuilder for(int j = 0;j < str.length() ;++j){ if((i & (1 << j))>0){ // to check whether jth bit is set strB.append(str.charAt(j)); } } if(!strB.toString().isEmpty()) StrList.add(strB.toString()); } System.out.println(Arrays.toString(StrList.toArray())); } 

This is a faster solution as it doesn't suffer for string concatenation computation complexity O(n^2). On the other hand its loop free, fully recursive

public static void main(String[] args) { permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); } private static void permutation(String str) { char[] stringArray = str.toCharArray(); printPermutation(stringArray, 0, stringArray.length, 0, 1); } private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) { // Stop condition if (loopCounter == length) return; /* When reaching the end of the array: 1- Reset loop indices. 2- Increase length counter. */ if (indexTo == length) { indexFrom = 0; indexTo = 1; ++loopCounter; } // Print. System.out.println(string); // Swap from / to indices. char temp = string[indexFrom]; string[indexFrom] = string[indexTo]; string[indexTo] = temp; // Go for next iteration. printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo); } 

Simple python solution using recursion.

def get_permutations(string): # base case if len(string) <= 1: return set([string]) all_chars_except_last = string[:-1] last_char = string[-1] # recursive call: get all possible permutations for all chars except last permutations_of_all_chars_except_last = get_permutations(all_chars_except_last) # put the last char in all possible positions for each of the above permutations permutations = set() for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last: for position in range(len(all_chars_except_last) + 1): permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:] permutations.add(permutation) return permutations 

Based on the answer of Mark Byers, my python implementation:

def permutations(string): if len(string) == 1: return [string] permutations=[] for i in range(len(string)): for perm in permutations(string[:i]+string[i+1:]): permutations.append(string[i] + perm) return permutations 

Recursive Python solution

def permute(input_str): _permute("", input_str) def _permute(prefix, str_to_permute): if str_to_permute == '': print(prefix) else: for i in range(len(str_to_permute)): _permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:]) if __name__ == '__main__': permute('foobar') 

A generic implementation of the Countdown Quickperm algorithm, representation #1 (scalable, non-recursive).

/** * Generate permutations based on the * Countdown <a href="http://quickperm.org/">Quickperm algorithm</>. */ public static <T> List<List<T>> generatePermutations(List<T> list) { List<T> in = new ArrayList<>(list); List<List<T>> out = new ArrayList<>(factorial(list.size())); int n = list.size(); int[] p = new int[n +1]; for (int i = 0; i < p.length; i ++) { p[i] = i; } int i = 0; while (i < n) { p[i]--; int j = 0; if (i % 2 != 0) { // odd? j = p[i]; } // swap T iTmp = in.get(i); in.set(i, in.get(j)); in.set(j, iTmp); i = 1; while (p[i] == 0){ p[i] = i; i++; } out.add(new ArrayList<>(in)); } return out; } private static int factorial(int num) { int count = num; while (num != 1) { count *= --num; } return count; } 

It needs Lists since generics don't play well with arrays.

A simple recursive C++ implementation would look like this:

#include <iostream> void generatePermutations(std::string &sequence, int index){ if(index == sequence.size()){ std::cout << sequence << "\n"; } else{ generatePermutations(sequence, index + 1); for(int i = index + 1 ; i < sequence.size() ; ++i){ std::swap(sequence[index], sequence[i]); generatePermutations(sequence, index + 1); std::swap(sequence[index], sequence[i]); } } } int main(int argc, char const *argv[]) { std::string str = "abc"; generatePermutations(str, 0); return 0; } 

Output:

abc acb bac bca cba cab 

UPDATE

If you want to store the results, you can pass a vector as the third argument to the function call. Furthermore, if you only want the unique permutations, you can use a set.

#include <iostream> #include <vector> #include <set> void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){ if(index == sequence.size()){ //std::cout << sequence << "\n"; v.push_back(sequence); } else{ generatePermutations(sequence, index + 1, v); for(int i = index + 1 ; i < sequence.size() ; ++i){ std::swap(sequence[index], sequence[i]); generatePermutations(sequence, index + 1, v); std::swap(sequence[index], sequence[i]); } } } int main(int argc, char const *argv[]) { std::string str = "112"; std::vector <std::string> permutations; generatePermutations(str, 0, permutations); std::cout << "Number of permutations " << permutations.size() << "\n"; for(const std::string &s : permutations){ std::cout << s << "\n"; } std::set <std::string> uniquePermutations(permutations.begin(), permutations.end()); std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n"; for(const std::string &s : uniquePermutations){ std::cout << s << "\n"; } return 0; } 

Output:

Number of permutations 6 112 121 112 121 211 211 Number of unique permutations 3 112 121 211 

public class Permutation { public static void main(String[] args) { String str = "ABC"; int n = str.length(); Permutation permutation = new Permutation(); permutation.permute(str, 0, n-1); } /** * permutation function * @param str string to calculate permutation for * @param l starting index * @param r end index */ private void permute(String str, int l, int r) { if (l == r) System.out.println(str); else { for (int i = l; i <= r; i++) { str = swap(str,l,i); permute(str, l+1, r); str = swap(str,l,i); } } } /** * Swap Characters at position * @param a string value * @param i position 1 * @param j position 2 * @return swapped string */ public String swap(String a, int i, int j) { char temp; char[] charArray = a.toCharArray(); temp = charArray[i] ; charArray[i] = charArray[j]; charArray[j] = temp; return String.valueOf(charArray); } } 

simple solution utilizing feature of swift language that array is value type.

func permutation(chrs: [String], arr: [String], result: inout [[String]]) { if arr.count == chrs.count { result.append(arr) return } for chr in chrs { var arr = arr if !arr.contains(chr) { arr.append(chr) permutation(chrs: chrs, arr: arr, result: &result) } } } func test() { var result = [[String]]() let chrs = ["a", "b", "c", "d"] permutation(chrs: chrs, arr: [], result: &result) } 

complexity O(n * n!)

I am defining two strings left and right. In the beginning, the left is input string and he right is “”. I recursively choose all possible chars from left and add it to the end of the right. Then, I call the recursive function on left-charAt(i) and right+charAt(i). I am defining a class to keep track of the generated permutations.

import java.util.HashSet; import java.util.Set; public class FindPermutations { static class Permutations { Set<String> permutations = new HashSet<>(); } /** * Building all the permutations by adding chars of left to right one by one. * * @param left The left string * @param right The right string * @param permutations The permutations */ private void findPermutations(String left, String right, Permutations permutations) { int n = left.length(); if (n == 0) { permutations.permutations.add(right); } for (int i = 0; i < n; i++) { findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations); } } /** * Gets all the permutations of a string s. * * @param s The input string * @return all the permutations of a string s */ public Permutations getPermutations(String s) { Permutations permutations = new Permutations(); findPermutations(s, "", permutations); return permutations; } public static void main(String[] args) { FindPermutations findPermutations = new FindPermutations(); String s = "ABC"; Permutations permutations = findPermutations.getPermutations(s); printPermutations(permutations); } private static void printPermutations(Permutations permutations) { for (String p : permutations.permutations) { System.out.println(p); } } } 

I hope it helps.

As a Python generator, with modern type hints:

from typing import Iterator def permutations(string: str, prefix: str = '') -> Iterator[str]: if len(string) == 0: yield prefix for i, character in enumerate(string): yield from permutations(string[:i] + string[i + 1:], prefix + character) for p in permutations('abcd'): print(p) 

I have been learning to think recursively and the first natural solution that struck me is as follows. A problem one step simpler would be to find permutations of a string that is one letter shorter. I will assume, and believe with every fiber of my being, that my function can correctly find permutations of a string that is one letter shorter than the one I am currently trying to.

Given a string say 'abc', break it into a subproblem of finding permutations of a string one character less which is 'bc'. Once we have permutations of 'bc' we need to know how to combine it with 'a' to get the permutations for 'abc'. This is the core of recursion. Use the solution of a subproblem to solve the current problem. By observation, we can see that inserting 'a' in all the positions of each of the permutations of 'bc' which are 'bc' and 'cb' will give us all the permutations of 'abc'. We have to insert 'a' between adjacent letters and at the front and end of each permutation. For example

For 'bc' we have

'a'+'bc' = 'abc'

'b'+'a'+'c' = 'bac'

'bc'+'a' = 'bca'

For 'cb' we have

'a'+'cb' = 'acb'

'c'+'a'+'b' = 'cab'

'cb'+'a' = 'cba'

The following code snippet will clarify this. Here is the working link for the snippet.

def main(): result = [] for permutation in ['bc', 'cb']: for i in range(len(permutation) + 1): result.append(permutation[:i] + 'a' + permutation[i:]) return result if __name__ == '__main__': print(main()) 

The complete recursive solution will be. Here is the working link for the complete code.

def permutations(s): if len(s) == 1 or len(s) == 0: return s _permutations = [] for permutation in permutations(s[1:]): for i in range(len(permutation) + 1): _permutations.append(permutation[:i] + s[0] + permutation[i:]) return _permutations def main(s): print(permutations(s)) if __name__ == '__main__': main('abc') 

My Implementation based on Heap's algorithm :

import java.util.ArrayList; import java.util.List; public class PermutationString { public static List<String> permute(char[] str, int n) { List<String> permutations = new ArrayList<>(); if (n == 1) { permutations.add(new String(str)); } else { for (int i = 0; i < n; i++) { permutations.addAll(permute(str, n-1)); if (n % 2 == 0) { swap(str, i, n-1); } else { swap(str, 0, n-1); } } } return permutations; } public static void swap(char[] str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } public static void main(String[] args) { List<String> permutations = permute("abcdefgh".toCharArray(), 8); System.out.println(permutations); } } 

Time Complexity would be O(n! * n) with O(n) as space complexity.

//Loop thro' the entire character array and keep 'i' as the basis of your permutation and keep finding the combination like you swap [ab, ba]

public class Permutation { //Act as a queue private List<Character> list; //To remove the duplicates private Set<String> set = new HashSet<String>(); public Permutation(String s) { list = new LinkedList<Character>(); int len = s.length(); for(int i = 0; i < len; i++) { list.add(s.charAt(i)); } } public List<String> getStack(Character c, List<Character> list) { LinkedList<String> stack = new LinkedList<String>(); stack.add(""+c); for(Character ch: list) { stack.add(""+ch); } return stack; } public String printCombination(String s1, String s2) { //S1 will be a single character StringBuilder sb = new StringBuilder(); String[] strArr = s2.split(","); for(String s: strArr) { sb.append(s).append(s1); sb.append(","); } for(String s: strArr) { sb.append(s1).append(s); sb.append(","); } return sb.toString(); } public void printPerumtation() { int cnt = list.size(); for(int i = 0; i < cnt; i++) { Character c = list.get(0); list.remove(0); List<String> stack = getStack(c, list); while(stack.size() > 1) { //Remove the top two elements String s2 = stack.remove(stack.size() - 1); String s1 = stack.remove(stack.size() - 1); String comS = printCombination(s1, s2); stack.add(comS); } String[] perms = (stack.remove(0)).split(","); for(String perm: perms) { set.add(perm); } list.add(c); } for(String s: set) { System.out.println(s); } } } 

Improved Code for the same

 static String permutationStr[]; static int indexStr = 0; static int factorial (int i) { if (i == 1) return 1; else return i * factorial(i-1); } public static void permutation(String str) { char strArr[] = str.toLowerCase().toCharArray(); java.util.Arrays.sort(strArr); int count = 1, dr = 1; for (int i = 0; i < strArr.length-1; i++){ if ( strArr[i] == strArr[i+1]) { count++; } else { dr *= factorial(count); count = 1; } } dr *= factorial(count); count = factorial(strArr.length) / dr; permutationStr = new String[count]; permutation("", str); for (String oneStr : permutationStr){ System.out.println(oneStr); } } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0) { for (int i = 0; i < indexStr; i++){ if(permutationStr[i].equals(prefix)) return; } permutationStr[indexStr++] = prefix; } else { for (int i = 0; i < n; i++) { permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)); } } } 

import java.io.*; public class Anagram { public static void main(String[] args) { java.util.Scanner sc=new java.util.Scanner(System.in); PrintWriter p=new PrintWriter(System.out,true); p.println("Enter Word"); String a[],s="",st;boolean flag=true; int in[],n,nf=1,i,j=0,k,m=0; char l[]; st=sc.next(); p.println("Anagrams"); p.println("1 . "+st); l=st.toCharArray(); n=st.length(); for(i=1;i<=n;i++){ nf*=i; } i=1; a=new String[nf]; in=new int[n]; a[0]=st; while(i<nf){ for(m=0;m<n;m++){ in[m]=n; }j=0; while(j<n){ k=(int)(n*Math.random()); for(m=0;m<=j;m++){ if(k==in[m]){ flag=false; break; } } if(flag==true){ in[j++]=k; }flag=true; }s=""; for(j=0;j<n;j++){ s+=l[in[j]]; } //Removing same words for(m=0;m<=i;m++){ if(s.equalsIgnoreCase(a[m])){ flag=false; break; } } if(flag==true){ a[i++]=s; p.println(i+" . "+a[i-1]); }flag=true; } } } 

Here are two c# versions (just for reference): 1. Prints all permuations 2. returns all permutations

Basic gist of the algorithm is (probably below code is more intuitive - nevertheless, here is some explanation of what below code does): - from the current index to for the rest of the collection, swap the element at current index - get the permutations for the remaining elements from next index recursively - restore the order, by re-swapping

Note: the above recursive function will be invoked from the start index.

private void PrintAllPermutations(int[] a, int index, ref int count) { if (index == (a.Length - 1)) { count++; var s = string.Format("{0}: {1}", count, string.Join(",", a)); Debug.WriteLine(s); } for (int i = index; i < a.Length; i++) { Utilities.swap(ref a[i], ref a[index]); this.PrintAllPermutations(a, index + 1, ref count); Utilities.swap(ref a[i], ref a[index]); } } private int PrintAllPermutations(int[] a) { a.ThrowIfNull("a"); int count = 0; this.PrintAllPermutations(a, index:0, count: ref count); return count; } 

version 2 (same as above - but returns the permutations in lieu of printing)

private int[][] GetAllPermutations(int[] a, int index) { List<int[]> permutations = new List<int[]>(); if (index == (a.Length - 1)) { permutations.Add(a.ToArray()); } for (int i = index; i < a.Length; i++) { Utilities.swap(ref a[i], ref a[index]); var r = this.GetAllPermutations(a, index + 1); permutations.AddRange(r); Utilities.swap(ref a[i], ref a[index]); } return permutations.ToArray(); } private int[][] GetAllPermutations(int[] p) { p.ThrowIfNull("p"); return this.GetAllPermutations(p, 0); } 

Unit Tests

[TestMethod] public void PermutationsTests() { List<int> input = new List<int>(); int[] output = { 0, 1, 2, 6, 24, 120 }; for (int i = 0; i <= 5; i++) { if (i != 0) { input.Add(i); } Debug.WriteLine("================PrintAllPermutations==================="); int count = this.PrintAllPermutations(input.ToArray()); Assert.IsTrue(count == output[i]); Debug.WriteLine("=====================GetAllPermutations================="); var r = this.GetAllPermutations(input.ToArray()); Assert.IsTrue(count == r.Length); for (int j = 1; j <= r.Length;j++ ) { string s = string.Format("{0}: {1}", j, string.Join(",", r[j - 1])); Debug.WriteLine(s); } Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count); } }