Subsets, Permutations, Combinations

Photo by Michael Dziedzic on Unsplash

Subsets

Photo by Paul Bergmeir on Unsplash
1. {}        - select none
2. {1} - select only '1'
3. {2} - select only '2'
4. {1, 2} - select '1' and '2' in any order (same as {2, 1})
                             [1, 2]
1. Start with {}
2. Add '1' to a copy of the current state ({})
2.1 Updated state is {}, {1}
3. Add '2' to a copy of the current state ({}, {1})
3.1 Updated state is {}, {1}, {2}, {1, 2}
  1. one will be empty set = {}
  2. one will a complete set = {complete input}
  3. remaining (2^n) - 2 will be partial sets
  1. existing subsets will not contain the current element
  2. clone all the existing subsets and add the current element to each of the cloned subset
  3. add the cloned subsets back to the total subsets
  4. proceed with next element

Duplicate in Input

1. {}        - select none
2. {1} - select only first '1'
3. {1} - select only second '1'
4. {2} - select only the '2'
5. {1, 1} - select '1' and '1' in any order (same as {1, 1})
6. {1, 2} - select first '1' and '2'
7. {1, 2} - select second 1' and '2'
8. {1, 1, 2} - select both '1'’s and '2'
3. {1}       - select only second '1'
7. {1, 2} - select second 1' and '2'
1. {}        - select none
2. {1} - select only the first '1'
3. {2} - select only the '2'
4. {1, 1} - select '1' and '1' in any order (same as {1, 1})
5. {1, 2} - select first '1' and '2'
6. {1, 1, 2} - select both '1'’s and '2'
1. Identify duplicate elements by remembering the previous value (sorted input)
2. If current element different from previous element in the sorted input, then process the element as per the above unique solution case (clone and append to every existing set)
3. If current element is same as previous element in the sorted input, then consider only sets that has the previous element (clone and append only to those sets)
The rationale behind considering only the sets that has the previous element is: don't duplicate the work done by previous element
1. sort the input
2. input = [1¹, 1², 2] (either increasing or decreasing)
3. initialize result = {}
4. initialize previous = INFINITY
5. compare current element with previous element
6. compare 1¹ with INFINITY
7. 1¹ != INFINITY, so clone the complete result
8. cloned = {}
9. insert 1¹ to each of the cloned set (in this case only 1)
10. cloned = {1¹}
11. add cloned sets to existing result
12. result = {}, {1¹}
13. assign current element to previous
14. previous = 1¹
15. compare current element with previous element
16. compare 1² with 1¹
17. 1² == 1¹, so consider only the sets containing previous element(1¹) as candidate sets.
18. clone the candidate sets
19. cloned = {1¹}
20. insert 1² to each of the cloned set
21. cloned = {1¹, 1²}
22. add cloned sets to existing result
23. result = {}, {1¹}, {1¹, 1²}
24. assign current element to previous
25. previous = 1²
26. compare current element with previous element
27. compare 2 with 1²
28. 2 != 1², so clone the complete result
29. cloned = {}, {1¹}, {1¹, 1²}
30. insert 2 to each of the cloned set
31. cloned = {2}, {1¹, 2}, {1¹, 1², 2}
32. Add cloned sets to existing result
33. result = {}, {1¹}, {1¹, 1²}, {2}, {1¹, 2}, {1¹, 1², 2}
34. assign current element to previous
35. previous = 2
  1. current element is seen for the first time
  2. current element is same as previously added element
  1. current element is seen for the first time, then clone the complete subsets and add current element and remember the count of cloned subsets
  2. current element is same as previous element, then clone only the subsets containing the previous element (use the remembered count)

--

--

--

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

Recommended from Medium

Popular misconception about CSS position absolute

Solving N-queens with Bitwise Operators

Next Journey

Pair Programming Antipatterns: XPerience

Strings Builder — Golang

Stream Editor — Part II

Scaling Openshift UPI Clusters Using Central Infrastructure Management

‘I learned to code part-time. Here’s how you can do the same.’

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

Chapter 10 — Numbers Matter

The M4 Sherman

Offshore freshwater aquifers — the planet’s secret reserve?

World War II