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

- clone each list “m” times (m is the number of elements seen including current element)
- insert current element to incremental index positions in the cloned lists
- 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,

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

TODO