Subset, Permutation, Combination — continued

In the previous section, we focussed on subsets. In this section, lets work on the permutations.

Photo by Markus Spiske on Unsplash

Permutation

Permutation can be defined in terms of the order of the selected elements. The order of elements is important in permutation(order was irrelevant in subset problem). So, permutation is an ordered selection of the candidate elements.

Photo by Jean-Louis Paulin on Unsplash

Lets get started with an example. The candidate elements are [1, 2]. The permutation(s) of these 2 elements are

1. {1, 2}    - select '1' and then select '2' 
2. {2, 1}    - select '2' and then select '1'

In the above permutations, we observe that permutations contains same elements in different order and they are valid. There are 2(2!) permutations.

If we choose 3 elements, say [1, 2, 3], the permutation(s) of these 3 elements will be

1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 1, 2}
6. {3, 2, 1}

In the above example, there are 6(3!) permutations. Analyzing the examples will help us understand that the number of permutations for an input of size n will be n!.

Given a permutation, exchaning any 2 elements will result in a new permutation. For n elements, there are n! ways of exchanging elements.

                          [1, 2, 3]
1. Start with empty permutation [] as result
2. initialize m to 0 (number of processed elements)
3. m = 0
4. result = [] 

Lets consider the element ‘1’

5. select 1
6. increment m by 1
7. m = 1
8. clone every list in result "m" times (here there is only 1 list in result = [])
9. cloned = []
10. insert the current element at incremental indexes in the cloned lists
11. index '0' is the only valid index
12. insert '1' to '0'th index
13. cloned = [1]
14. replace result with cloned
15. result = cloned
16. result = [1]

Lets take the next element ‘2’

17. select 2
18. increment m by 1
19. m = 2
20. clone every list in the result "m" times (here there is only 1 list in result = [1])
21. cloned = [1], [1]
22. insert the current element at incremental indexes in the cloned lists
23. index 0 and 1 are the valid indexes
24. insert '2' to '0'th index in the first clone
25. cloned = [2, 1], [1]
26. insert '2' to '1'st index in the second clone
27. cloned = [2, 1], [1, 2]
28. replace result with cloned
29. result = cloned
30. result = [2, 1], [1, 2]

Lets take the next element ‘3’

31. select 3
32. increment m by 1
33. m = 3
34. clone every list in the result "m" times (here there are 2 lists in the result = [2, 1], [1, 2]
35. clone the '1'st list in result "m" times ([2, 1])
36. cloned = [2, 1], [2, 1], [2, 1]
37. insert the current element at incremental indexes in the cloned lists
38. index '0', '1', and '2' are the valid indexes
39. insert '3' to the '0'th index of the 1st list in clone
40. cloned = [3, 2, 1], [2, 1], [2, 1]
41. insert '3' to the '1'st index of the 2nd list in clone
42. cloned = [3, 2, 1], [2, 3, 1], [2, 1]
43. insert '3' to the '2'nd index of the 3rd list in clone
44. cloned = [3, 2, 1], [2, 3, 1], [2, 1, 3]
45. now, clone the '2'nd list in the result "m" times ([1, 2])
46. another_cloned = [1, 2], [1, 2], [1, 2]
47. insert the current element at incremental indexes in the cloned lists
48. insert '3' to the '0'th index of the 1st list in clone
49. another_cloned = [3, 1, 2], [1, 2], [1, 2]
50. insert '3' to the '1'st index of the 2nd list in clone
51. another_cloned = [3, 1, 2], [1, 3, 2], [1, 2]
52. insert '3' to the '2'nd index of the 3rd list in clone
54. another_cloned = [3, 1, 2], [1, 3, 2], [1, 2, 3]
55. replace result with cloned lists
56. result = cloned + another_cloned
57. result = [3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]

We can start with the regular recursive code to compute the permutations. The recursive code will place every element at every possible index by swapping elements.

An iterative version of the same logic will resemble the flow of logic as discussed in the example

1. clone each list “m” times (m is the number of elements seen including current element)
2. insert current element to incremental index positions in the cloned lists
3. create a new result using all the cloned lists

To better understand/debug, we can enumerate and get the subsets over the stream of numbers using the following code

All the above approaches work when the input contains unique elements. If the input can contain duplicate(s), modification is required in the above solutions to produce expected permutations.

Duplicate In Input

When the input contains duplicates, permutation computation has to handle duplicate occurances to produce the correct result. Lets take the example of [1, 1, 2]. Running through the above logic, we will get incorrect(duplicates) in the output

input = [1¹, 1², 2]
permutations will be 
1. [1¹, 1², 2]
2. [1¹, 2, 1²]
3. [1², 1¹, 2]
4. [1², 2, 1¹]
5. [2, 1¹, 1²]
6. [2, 1², 1¹]

In the above result, the following are invalid(duplicates)

3. [1², 1¹, 2] - same as 1
4. [1², 2, 1¹] - same as 2
6. [2, 1², 1¹] - same as 5

The valid result is

1. [1¹, 1², 2]
2. [1¹, 2, 1²]
5. [2, 1¹, 1²]

To handle this scenario, grouping of the similar elements together will help us to skip over the duplicate permutations. One approach to group similar elements together is to sort the input list.

On a sorted input list,

1. for the very first element of a duplicate sequence, ignore the swaps with duplicates. consider only the swap with itself(like unique scenario)
2. for the subsequent duplicate elements in the sequence,

TODO