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

SaaS vs PaaS vs IaaS

What is Spliff DAO, you ask? What is our plan with all of this…

Reduce Cost and Increase Productivity with Value Added IT Services from buzinessware — {link} -

The Stack Data Structure in Python — Compucademy

A take on functional error handling in Kotlin

Web Scraping + Bookstore: notify me when a book is available

Creating an intelligent object storage system with Ceph’s Object Lifecycle Management

Finished my internship…Let’s reflect on it!

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

Antidiabetic Effect of Ethanolic Extract of Carica papaya Leaves in Alloxan-Induced Diabetic Rats |…

Jack Murphy Stadium, San Diego — 1991

Along Came Molly

AKA: Agent Molly Magdelene Coco, Boxer-Bull(?) Canine

To all the boys I thought were the one…