Subset, Permutation, Combination — continued

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
1. {1, 2}    - select '1' and then select '2' 
2. {2, 1} - select '2' and then select '1'
1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 1, 2}
6. {3, 2, 1}
                          [1, 2, 3]
1. Start with empty permutation [] as result
2. initialize m to 0 (number of processed elements)
3. m = 0
4. result = []
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]
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]
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]
  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
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¹]
3. [1², 1¹, 2] - same as 1
4. [1², 2, 1¹] - same as 2
6. [2, 1², 1¹] - same as 5
1. [1¹, 1², 2]
2. [1¹, 2, 1²]
5. [2, 1¹, 1²]
  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,

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store