I've got a situation I've set up in a story as follows (simplified for the sake of asking this question):
I've got an irregularly-shaped three-dimensional object which has been shattered into a large number of pieces and my character has to reassemble it. The only method he has is to take one piece, and then randomly select a second piece and see if it fits the first. If it does, great, he attaches it, if not, he discards it. Select a third piece, etc.
My questions are: (1) for a total number of pieces N, is there a way to calculate how many comparisons he's going to have to make to reassemble the entire object? (2) Does the job speed up linearly with additional people working on it (for example, if he gets three buddies to work on it with him, will they finish in a quarter of the time?)
I've tried to reason this out logically, but I keep getting stuck at the realization that more than one piece is a match for any given piece, i.e. if the first piece is a cube, there could be as many as six other pieces that fit with it. My brain starts trickling out of my ears when I hit that point.
And let me make one thing clear here: I am NOT looking for suggestions for more efficient algorithms. There are story reasons why he has to use this approach. I'm just trying to get a feel for how long the job will take given the resources he can throw at it.
Thanks in advance!
I've got an irregularly-shaped three-dimensional object which has been shattered into a large number of pieces and my character has to reassemble it. The only method he has is to take one piece, and then randomly select a second piece and see if it fits the first. If it does, great, he attaches it, if not, he discards it. Select a third piece, etc.
My questions are: (1) for a total number of pieces N, is there a way to calculate how many comparisons he's going to have to make to reassemble the entire object? (2) Does the job speed up linearly with additional people working on it (for example, if he gets three buddies to work on it with him, will they finish in a quarter of the time?)
I've tried to reason this out logically, but I keep getting stuck at the realization that more than one piece is a match for any given piece, i.e. if the first piece is a cube, there could be as many as six other pieces that fit with it. My brain starts trickling out of my ears when I hit that point.
And let me make one thing clear here: I am NOT looking for suggestions for more efficient algorithms. There are story reasons why he has to use this approach. I'm just trying to get a feel for how long the job will take given the resources he can throw at it.
Thanks in advance!