Placing Marbles in Jars
Here's my problem:
I have a number of marbles of different colors, 4 black, 5 blue, 4 green etc. I also have a number of jars. Each jar will only accept certain types of marbles, ie. Jar1 takes only black and blue, Jar2 takes only blue and green, Jar 3 takes any, Jar4 takes only green, etc. Each jar can only contain one marble.
The question: assuming that there IS a solution in which every marble has been placed in a jar, and every jar has exactly one marble, how do you find it?
I can't figure out anything other than an exhaustive search - I can't even figure out a decent heuristic that would make this run in an acceptable amount of time for even a relatively small number of marble-colors/jars. Can anyone help me out?
[763 byte] By [
BlueRaja] at [2007-11-20 11:38:54]
# 1 Re: Placing Marbles in Jars
You can find maximal pairing using the Ford-Fulkerson algorithm (http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm).
Represent the marbles and jars as a weighted graph in the following way:
1. Each marble is represented by a vertex.
2. Each jar is represented by a vetex.
3. Each marble that can be inserted into a specific jar will be connected to it by an edge.
4. Create another 2 vertices called "Source" and "Sink"
5. Connect all the marble vertices to the Source vertex.
6. Connect all the jar vertices to the Sink vertex.
7. Give ALL edges in the graph a weight of 1.
You'll end up with a grpah like the image attached to this post.
Now you just need to run the F.F. algorithm and at the end check which edges between the marble group and the jar group have a flow higher than 0. This set of edges represent which marble should go to which jar.
Runtime for the F.F algorithm (which does most of the work) is O(E*n) where E is the number of edges in the graph and n is the number of marbles.
Zachm at 2007-11-10 3:52:28 >
# 2 Re: Placing Marbles in Jars
Wow that's really ingenious... I have a few questions with regards to that, though
1. I'm rather new to the concept of flow networks - since all five green marbles (or whathave you) are the same, wouldn't the algorithm perform faster if, instead of having five individual green marbles each connected to the source with capacity 1, we connected one node representing all five marbles to the source and set the capacity of the edge to 5 (still keeping all the edges connected to each jar at capacity 1)?
2. Say we know that there is more than one solution to problem; do you know of any way to quickly generate *all* the solutions?
I've been wracking my brain all evening for this one, but it seems I have much yet to learn about algorithm theory...
# 3 Re: Placing Marbles in Jars
wouldn't the algorithm perform faster if, instead of having five individual green marbles each connected to the source with capacity 1, we connected one node representing all five marbles to the source and set the capacity of the edge to 5 (still keeping all the edges connected to each jar at capacity 1)?
Yes, you are right, I regarded each marble as unique, while it is not necessarily so. Therefore mapping the colors to the jars seems like a wiser choise and will reduce the runtime.
Good observation :thumb: !!!
As for #2, I don't have an answer for that, because you mentioned the word "quickly" :).
Zachm at 2007-11-10 3:54:22 >
