Suppose I have a list of numbers consisting of numbers 1 through 5, where some numbers repeat. Define a set of numbers to be "complete" if it consists of each of the numbers 1-5 exactly once. Now, I want to pull out as many possible complete, sorted (lowest to highest) sets from this list. How can I do this (efficiently)?
Here is the solution I have in mind so far. Traverse through the list, and place each number into a pile of numbers that is the same number. For example, place all the 1s into a pile, all the 2s into a pile, and so on. Then, go through all of the piles and determine the minimum number of elements in a pile. For example, if the pile of 2s has five 2s and all other piles have greater than or equal to five elements, then 5 is the minimum number of elements. This minimum, call it min, will give us the number of complete sets in the list. Finally, go through the piles in order and pull out the elements one by one until you form a complete set, and again to form another complete set, and so on until min number of complete sets. Tada! You now have pulled out as many possible complete, sorted sets from this list.
Here is an example:
Let’s say the list is 3 2 1 2 2 3 4 5 5 4 4 3 4 1 1 2 5. We traverse the list and put them into piles:
333 2222 111 4444 555
The minimum number of elements in a pile is 3, so we have 3 complete sets. Now just go through the piles in order and pick up elements one by one:
12345 12345 12345
And tada! We have pulled out as many complete, sorted sets as possible.
Where I am lacking in my solution is figuring out how to efficiently go through the piles in order or make an efficient way of ordering the piles so that I can easily go through them in order.
I’d love to hear any feedback, especially other algorithms you might devise or ways to go about ordering. Thanks!