Subsets, Permutations, Combinations

Photo by Michael Dziedzic on Unsplash

Subsets

Subset can be defined in terms of presence or absence of candidate elements. So, subset is defined as a possible groupings of candidate elements. Subset does not rely on the order of the elements(with an exception during implementation). Subsets is basically a collection of all possible groupings of candidate elements(collection of subset)

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

When the input contains duplicates, subset 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

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)

--

--

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