Subset, Permutation, Combination — continued

Photo by Markus Spiske on Unsplash

Permutation

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,

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Google Africa Developer Scholarship Developer Conference

10 Selenium Webdriver Tips and Tricks

LeetCode 765. Couples Holding Hands

Microservices: Building Things is Easy; Building the Right Thing is Hard

How to handle eventual consistency with S3

Geofencing in XLSForm/ODK

How to Become a Data Scientist: a Software Engineer’s Best Guess

K8s is saying goodbye to Docker.. really!?

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
Some One

Some One

More from Medium

Can Algorithms really be trusted in Clinical Medicine?

Modeling Action Potentials as an Electric Circuit

Unbounded Knapsack Problem

Graph 01 : Louvain Algorithm