Permutations
I was recently working on a permutation algorithm when it occurred to me that solving a permutation by hand is not intuitive let alone coding an algorithm for one. So I decided to blog about it to help anyone else who might be trying to work through a permutation.
First off, I decided to work with permutations of letters instead of numbers. When trying to write permutation code, numbers can get confused with array or list indexes.
Per the graphic, the logic essentially adds each successive letter to the permutation of the letters before it. Clear as mud, right? Let's walk through an example starting with 'A'. 'A' doesn't have any permutations before it, so just add the 'A' to the result set. Let's work with the next letter, 'B'. Copy the previous result set, which is just 'A', and add 'B' to the first position. Copy the previous result set again, and add 'B' to the second position. Now, let's work with 'C'. Copy the previous result set, and add 'C' to the first position. Copy the previous result set again, and add 'C' to the second position. Lastly, copy the previous result set, and add 'C' to the third position.
Now for the coding part. To avoid taxing stack memory, I decided to use a non-recursive/iterative algorithm. Without further ado, here is the source code, which you can also access on Git Lab.
import java.util.*; /** * Problem - https://leetcode.com/problems/permutations/description/ * Given a collection of distinct numbers, return all possible permutations. * * For example, * [1,2,3] have the following permutations: * [ * [1,2,3], * [1,3,2], * [2,1,3], * [2,3,1], * [3,1,2], * [3,2,1] * ] * * To avoid confusion with indexes, this problem is easier to think of in terms of * letters as opposed to numbers. For example, given "ABCD", the gist of the algorithm * is to start with permutations of A, then permutations of AB, then permutations of ABC, etc. * The logic goes like this: * Input: A B C D * Input Idx: 0 1 2 3 * [A] // insert input[0] to pos 0 of 1st row [] * [B A // insert input[1] to pos 0 of 1st row [A] * A B] // insert input[1] to pos 1 of 1st row [A] * [C B A // insert input[2] to pos 0 of 1st row [BA] * C A B // insert input[2] to pos 0 of 2nd row [AB] * B C A // insert input[2] to pos 1 of 1st row [BA] * A C B // insert input[2] to pos 1 of 2nd row [AB] * B A C // insert input[2] to pos 2 of 1st row [BA] * A B C] // insert input[2] to pos 2 of 2nd row [AB] * [D C B A // insert input[3] to pos 0 of 1st row [CBA] * D C A B // insert input[3] to pos 0 of 2nd row [CAB] * D B C A // insert input[3] to pos 0 of 3rd row [BCA] * … * A B C D] // insert input[3] to pos 3 of 6th row [ABC] * * @see https://discuss.leetcode.com/topic/6377/my-ac-simple-iterative-java-python-solution */ class Permutator { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums.length == 0) return result; result.add(new ArrayList<Integer>()); for (int i=0; i<nums.length; i++) { List<List<Integer>> tmpResult = new ArrayList<List<Integer>>(); for (int insertPos=0; insertPos<=i; insertPos++) { // O(rowRef.len(2rowRef.len - insertPos)) for (List<Integer> rowRef : result) { List<Integer> rowCopy = new ArrayList<Integer>(rowRef); // O(rowRef.len) rowCopy.add(insertPos,nums[i]); // O(rowRef.len-insertPos) tmpResult.add(rowCopy); // Big O Total = O(rowRef.len + rowRef.len - insertPos) // = O(2rowRef.len - insertPos) } } result = tmpResult; } return result; } public static void main(String[] args) { Permutator perm = new Permutator(); int[] input; List<List<Integer>> output; List<List<Integer>> expected = new ArrayList<List<Integer>>(); input = new int[] {1}; expected.add(Arrays.asList(1)); output = perm.permute(input); System.out.println("input<"+Arrays.toString(input)+">; permutations<"+output+">"); assert output.equals(expected) : "\nexpected<"+expected+">\n actual<"+output+">"; expected.clear(); input = new int[] {1,2}; expected.add(Arrays.asList(2,1)); expected.add(Arrays.asList(1,2)); output = perm.permute(input); System.out.println("input<"+Arrays.toString(input)+">; permutations<"+output+">"); assert output.equals(expected) : "\nexpected<"+expected+">\n actual<"+output+">"; expected.clear(); input = new int[] {1,2,3}; expected.add(Arrays.asList(3,2,1)); expected.add(Arrays.asList(3,1,2)); expected.add(Arrays.asList(2,3,1)); expected.add(Arrays.asList(1,3,2)); expected.add(Arrays.asList(2,1,3)); expected.add(Arrays.asList(1,2,3)); output = perm.permute(input); System.out.println("input<"+Arrays.toString(input)+">; permutations<"+output+">"); assert output.equals(expected) : "\nexpected<"+expected+">\n actual<"+output+">"; expected.clear(); input = new int[] {1,2,3,4}; expected.add(Arrays.asList(4,3,2,1)); expected.add(Arrays.asList(4,3,1,2)); expected.add(Arrays.asList(4,2,3,1)); expected.add(Arrays.asList(4,1,3,2)); expected.add(Arrays.asList(4,2,1,3)); expected.add(Arrays.asList(4,1,2,3)); expected.add(Arrays.asList(3,4,2,1)); expected.add(Arrays.asList(3,4,1,2)); expected.add(Arrays.asList(2,4,3,1)); expected.add(Arrays.asList(1,4,3,2)); expected.add(Arrays.asList(2,4,1,3)); expected.add(Arrays.asList(1,4,2,3)); expected.add(Arrays.asList(3,2,4,1)); expected.add(Arrays.asList(3,1,4,2)); expected.add(Arrays.asList(2,3,4,1)); expected.add(Arrays.asList(1,3,4,2)); expected.add(Arrays.asList(2,1,4,3)); expected.add(Arrays.asList(1,2,4,3)); expected.add(Arrays.asList(3,2,1,4)); expected.add(Arrays.asList(3,1,2,4)); expected.add(Arrays.asList(2,3,1,4)); expected.add(Arrays.asList(1,3,2,4)); expected.add(Arrays.asList(2,1,3,4)); expected.add(Arrays.asList(1,2,3,4)); output = perm.permute(input); System.out.println("input<"+Arrays.toString(input)+">; permutations<"+output+">"); assert output.equals(expected) : "\nexpected<"+expected+">\n actual<"+output+">"; expected.clear(); } } /* A Walk Thru an Example (The right side of the table contains Big O analysis) nums = INIT: result = [[]] result i/val tmpResult insertPos rowCopy |rowCopy-loop add-loop for-rowRef for-insertPos for-i Total [[]] 0/A [] 0 [] |0 [A] | 0-0=0 [[A]] | 1 1 1 0+0+1+1+1=3 [[A]] 1/B [] 0 [A] |1 [BA] | 1-0=1 [[BA]] | 1 3+1+1+1=6 1 [A] |1 [AB] | 1-1=0 [[BA][AB]] | 1 2 1 6+1+0+1+2+1=11 [[BA][AB]] 2/C [] 0 [BA] |2 [CBA] | 2-0=2 [[CBA]] | 1 11+2+2+1=16 [AB] |2 [CAB] | 2-0=2 [[CBA][CAB]] | 1 16+2+2+1=21 1 [BA] |2 [BCA] | 2-1=1 [[CBA][CAB][BCA]] | 1 21+2+1+1=25 [AB] |2 [ACB] | 2-1=1 [[CBA][CAB][BCA][ACB]] | 1 25+2+1+1=29 2 [BA] |2 [BAC] | 2-2=0 [[CBA][CAB][BCA][ACB][BAC]] | 1 29+2+0+1=32 [AB] |2 [ABC] | 2-2=0 [[CBA][CAB][BCA][ACB][BAC][ABC]] 1 3 1 32+2+0+1+3+1=39 */
