From: Dan Schmidt <dfan@...>
Date: 2002-08-10T05:24:51+09:00
Subject: Re: Coding challenge (on Ruby Garden)

David Alan Black <dblack@candle.superlink.net> writes:

| As with 0001, this challenge comes with unit tests and an
| unimplemented method.  The basic idea of this challenge is:  write a
| method which takes two arguments: an array of items, and an
| array-of-arrays of items, and determines whether or not a one-to-one
| correspondence can be established, so that every item in the first
| array can be found in one of the arrays in the array-of-arrays:
| 
| This would return true:
| 
|    [1,2,3]
|    [ [1,11,111], [0,3,2], [2,4,6] ]
| 
| This would return false:
| 
|    [1,2,3]
|    [ [1,11,111], [0,3,2], [4,6,8] ]
| 
| (because 2 and 3 aren't allowed to correspond to the same array).

I just got here, but isn't this just the bipartite matching problem?
The two partitions are the two arrays, and an edge AB from partition 1
to partition 2 exists iff A is an element of B.

Dan

-- 
http://www.dfan.org