# Subset, Permutation, Combination — continued

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

# 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.

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 result2. initialize m to 0 (number of processed elements)3. m = 04. result = [] `

Lets consider the element ‘1’

`5. select 16. increment m by 17. m = 18. 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 lists11. index '0' is the only valid index12. insert '1' to '0'th index13. cloned = 14. replace result with cloned15. result = cloned16. result = `

Lets take the next element ‘2’

`17. select 218. increment m by 119. m = 220. clone every list in the result "m" times (here there is only 1 list in result = )21. cloned = , 22. insert the current element at incremental indexes in the cloned lists23. index 0 and 1 are the valid indexes24. insert '2' to '0'th index in the first clone25. cloned = [2, 1], 26. insert '2' to '1'st index in the second clone27. cloned = [2, 1], [1, 2]28. replace result with cloned29. result = cloned30. result = [2, 1], [1, 2]`

Lets take the next element ‘3’

`31. select 332. increment m by 133. m = 334. 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 lists38. index '0', '1', and '2' are the valid indexes39. insert '3' to the '0'th index of the 1st list in clone40. cloned = [3, 2, 1], [2, 1], [2, 1]41. insert '3' to the '1'st index of the 2nd list in clone42. cloned = [3, 2, 1], [2, 3, 1], [2, 1]43. insert '3' to the '2'nd index of the 3rd list in clone44. 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 lists48. insert '3' to the '0'th index of the 1st list in clone49. another_cloned = [3, 1, 2], [1, 2], [1, 2]50. insert '3' to the '1'st index of the 2nd list in clone51. another_cloned = [3, 1, 2], [1, 3, 2], [1, 2]52. insert '3' to the '2'nd index of the 3rd list in clone54. another_cloned = [3, 1, 2], [1, 3, 2], [1, 2, 3]55. replace result with cloned lists56. result = cloned + another_cloned57. 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 14. [1², 2, 1¹] - same as 26. [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