Algorithm to find if a set can be recreated

I'm finding it hard to solve the problem and was hoping that someone could help me with the solution or at least give me a search term to use for problems like this one.

The generalized problem: I have a set of numbers (e.g. `[1,2,3]`) and a an array of sets (e.g. `[1,4,5],[4,2,3],[6,7,8],[2],[1,3]`). What I need to do is to find if I can create the first set from the others by taking 1 or 0 elements from them (e.g. taking 1 from the first, 2 from the second and 3 from the last). Order of the elements doesn't matter in any of the sets.

This can be solved by computing a matching from elements in your base set, to the other sets. This is essentially checking for Hall's condition.

That is, build a bipartite graph G=(A,B,E), with A being the base set, and B being the other sets. There is an edge from x in A to some y in B if x is in y. Now compute a maximum matching (there are several algorithms for this) and you're good to go. If no matching exists, then you cannot recreate the set.

• I had a hunch that this could be done with graphs somehow. – karka91 Dec 31 '12 at 13:03

Let's say your "big" set is called `bigSet` and your array of sets is called arrayOfSets.
1. Go through all the elements of all sets in `arrayOfSets` and remember how many times you found each number from `bigSet` in those sets. Let's say you'll store this info in count (which should be a dictionary if bigSet is not ordered, which it shouldn't be by definition... or you can make your `bigSet` ordered by copying it into an array or something).
2. If you found some number zero times (that is, if `count(bigSet[i])` is 0 for some i), `bigSet` can't be generated from `arrayOfSets`.
3. Go through `arrayOfSets` again and each time you find some number from bigSet whose count in arrayOfSets is `min{count(bigSet[1]), count(bigSet[2]),..., count(bigSet[n])}`, eliminate that set from `arrayOfSets` and decrease the number of times each number from that array appears in `arrayOfSets`. If some number's count hits 0 after doing this, and if it's not the number you just found, bigSet can't be generated. "Eliminate" (delete or somehow "mark" so you know you shouldn't consider it anymore) the number you just found from `bigSet` and restart this step. Remember the set from which you took that number (if you want to recreate the solution afterwards)
4. If bigSet is empty (all the numbers from it have been eliminated), you can generate bigSet from `arrayOfSets`.
5. Repeat 3. - 4.

Example: (I'm using 1-based indexing)

``````bigSet = {10,4,8,1,7}
arrayOfSets = [{10,4}, {10,8,12,7},{1,5},{9,7},{7}]
Go through arrayOfSets and get:
count(10) = 2
count(4) = 1
count(8) = 1
count(1) = 1
count(7) = 3
min(count()) = 1 so go through arrayOfSets searching for numbers from {4,8,1}.
arrayOfSets[1] contains 4, so you delete arrayOfSets[1] from arrayOfSets, delete 4 from bigSet and decrease count for 4 and 10.
After this, you have:
bigSet = {10,8,1,7}
arrayOfSets = [{SKIPME},{10,8,12,7},{1,5},{9,7},{7}]
count(10) = 1
count(8) = 1
count(1) = 1
count(7) = 3
min(count()) = 1 so go through arrayOfSets searchinig for numbers from {10,8,1}.
arrayOfSets[2] contains 8 so, following the same procedure, you get:
bigSet = {10,1,7}
arrayOfSets = [{SKIPME},{SKIPME},{1,5},{9,7},{7}]
count(10) = 0
count(1) = 1
count(7) = 3
bigSet can't be generated from arrayOfSets because count(10) = 0.
``````
• Some comments: 1. I'm not 100% if this is correct, but I couldn't think of a counter-example. 2. If it is correct, it's probably not the best solution possible (complexity-wise) 3. I didn't worry too much about technical details, but I hope you get the main idea. 4. If my answer is any good, feel free to format it so it looks prettier, I currently don't have time for that. – iCanLearn Dec 29 '12 at 18:17
• I'm pretty 100% certain this isn't correct, but it should work unless you have really nasty sets. Like, you couldn't use it to solve a nasty sudoku. – amara Dec 30 '12 at 2:10
• @sparkleshy: Can you give a counter-example or explain why it wouldn't work on some input? – iCanLearn Dec 30 '12 at 9:27

Here's an approach that should be "ok" time complexity wise (but maybe still not optimal). The idea is to first build an index of values in the array of sets, then go through the set of numbers to see if they can be found in the index.

Definitions

Using the problem's description,

• let S be the set you are looking to rebuild
• let X be the array of sets, where X[i] is the i'th set in X
• let v=X[i,j] be the j'th value in set X[i]

To solve the problem efficiently,

• let H be a map with entries h(v,XI), where v is a value in X, and XI is a list of indexes i into X where this value was found.
• let R be the map of values corresponding to S, with entries r(i,v) where v is the value in set X[i], and i is the set where this value was taken from to rebuild S

Algorithm

1. Build the map H by reading through all sets in X. For each new value v=X[i,j], insert a corresponding entry h(v,XI) into H to remember in which set (the i'th set in X) this value was found. For values already in H, add i into the corresponding entries' XI.

2. Iterate over all values in S. For each value, look it up in H. If one is not found, abort since S cannot be rebuilt.

3. For each value in S, if the value exists in H, iterate over XI of the corresponding entry h(v,XI) to retrieve the indices i.

4. For each i in XI, try to add in R a new entry r(i,v), if and only if R does not contain another entry for the same i. If an entry for i exists already, it means that another value has already been read from the corresponding set in X, and another set i must be considered.

5. Repeat step 4 until a new entry could be added to R, or until there are no more i left. In the latter case abort as the set S cannot be rebuilt. *)

6. The values v in the entries of R should now correspond to S.

*) actually, before aborting in step 5, there could be some permutation of sets in X that would still work. For this to work, the algorithm would have to restart step 4 by trying another combination of sets in X.

Disclaimer: I did not implement the algorithm or test it.