Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

Hi, Im tryin to figure out a way to match M distinct objects with another N not neccesarily distinct objects. For example lets say I have M distinct objects {A,B,C,D,E,F}. I can have N objects {1,1,2,3,}. A proper match would be {(A,1),(B,1),(C,2),(D,3)}. If I had N objects {1,1,1,1,1,1}, then there would be only one way to match and that is {(A,1),(B,1),(C,1),(D,1),(E,1),(F,1)}.

I need to know the number of ways I can do this and a possible algorithm for actually doing it. Thanks,

I need to know the number of ways I can do this and a possible algorithm for actually doing it. Thanks,

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialSo what we end up with is a calculation like this: ('n' ways to do A)('n' ways to do B)(etc). So we end up with 'm' terms with a value of 'n', or:

------

x = n^m; where x is 'n' to the 'm'th power.

------

Example: Say we have m=20 cars all with distinct vin numbers, that can be painted any of n=5 colors.

x = 5^20 (approx. 9.53 x 10^13)

I would play the computer...

1) assign the first group of n1 elements of N to n1 members of M. There are M! / (n1! (M-n1)!) ways to do that, which leaves us with M-n1 non matched members in M.

2) assign the second group of n2 elements of N to n2 members of M-n1. There are (M-n1!) / (n2! (M-n1-n2)!) ways to do that, leaving M-n1-n2 non matched members in M.

going on to k, we have

M! / (n1! (M-n1!)) * (M-n1!) / (n2! (M-n1-n2)!) * ... * (M-n1-n2-...n(k-1) ) / (nk! (M-n1-n2-...nk)!)

ways to do it. Simplifying we stay with

M! / n1! n2! ... nk! (M-N)!

Since this happens to *be* GwynforWeb's solution, I must have missed something...

And that something is that (s)he computed order *independant* arrangements for M, which makes my point moot.

Good Job!

Anyway, I played around with this a little, and looked around a little and it is easy to write or find code to generate the sequences. Let k = min (elements(m), elements(n))

First generate the k-COMBINATIONS of the M set (note if k == m, this is 1). I have some javascript code for this if you want it, or there is c-code available at http://www.theory.csc.uvic.ca/~cos/inf/comb/CombinationsInfo.html (note I would use Combinations in lexicographic order, since it is easier to visually check, unless performance is a real problem, then transposition code would be better)

Note that combinations is another term for order independent.

Second generate the k-PERMUTATIONS of the N multi set using code available from http://www.theory.csc.uvic.ca/~cos/inf/mult/Multiset.html (same comment about lexical but vs. grey code order this time)

To use it you have to restate your N array as (#of 1's, #of 2's, #of 3's, etc.) so your example data is (2,1,1) for the first case, and (6) for the second (that is two 1's, one 2, one 3, and then six 1's)

Now loop thru matching all generated combinations of M with all generated permutations of N.

I have the code that is available from the above sites , but would suggest you go to the sites since they have so much info there. The code has a free to use clause in it, as long as you keep the credit info there.

Also add my vote to the math above; it sounds right to me.

Also both of the web sites have a generator on line to run for these cases, use

http://www.theory.cs.uvic.ca/~cos/gen/comb.html for the combinations and

http://www.theory.cs.uvic.ca/~cos/gen/mult.html for permutations of a multi set

More to follow, this is fun to play with!

It implements the algorithm mentioned above -

k=min(#M, #N)

generate k-combinations of M (M is all unique)

generate k-combinations of N (N is a multi set)

generate permutations of all k-combinations of N

then generate M*N

Only tested with netscape, and not extensively, but I think it is right. It is javascript so avoid large combinations or you may have to kill your browser. But it does provide output for small numbers, to help study it.

Pull the code from the page if you like.

I do not think the code for generating the combinations is all that challenging but the number of combinations balloons exponentially as the set orders increase.

Let's say you have a bag of scrabble pieces (all unique) in a bag and another bag of billiard balls (with some duplicates).

Let's say the experiment is to draw pairs (one from each bag) until one of the bags is exhausted - does that sound like a similar experiment to yours.

For the first bag the possibilities are like mentioned before the combination of n things taking k at a time {n! divided by (n-k)! k!}; but, with the second bag the probabilities change with each draw. Going to case #2 where we had [A,B,C,D,E,F] and [1,1,2,3]

On the first draw, the first probability is 1/6 and the second probability is 1/2 for a 1, 1/4 for a 2, and 1/4 for a 3. Now,

on the second draw we get the probability of 1/5, but for the second probability we MUST know the result of the first draw for bag #2 because the bag #2 probability has changed as a result of the draw.

So you can see we need a whole set of equations based on the number of objects involved for each conditional case - solve each and total the results. I am still looking at it - but, have misplaced my probability textbook.

I don't understand the problem with what GwynforWeb calls "case 2". In the two examples of the question you have M = N and M > N. In the second example, when M > N, you use more than once some of the N objects in order to make pairs. Isn't the case with M < N symmetrical to your second example? In other words, isn't it irrelevant which one of the sets has more elements?

In fact, if the two sets have different sizes and you decide to call "M" the numer of elements in the larger set, it seems to me that your second example and GwynforWeb's case 2 are the same case.

I haven't checked GwynforWeb solution to his "case 1", but I assume that it will be correct. Then, to solve case 2 you only need to swap the names of the two sets.

Is the first set (whose elements are identified by letters) in some way "preferred" or "different" from the other set? That is, is the pairing asymetrical in some way that escapes me?

Am I missing something? It wouldn't be the first time ;-)

whereas the N objects are in k distinct groups with ni objects in the ith distinct group

When M < N, not all the groups can be fully used, and there are different ways to

take subgroups who's cardinalty sums to M, each of which contributes a different count.

Sum(m1<=n1,m2<=n2,..,mk<=n

does not appear to have a simple closed form expression.

Perhaps it would help with case 2 if we broke it down into two subcases:

2a: M >= {sum(ni) for all ni > 1}

2b: M < {sum(ni) for all ni > 1}

In case 2a, we can temporarily remove from the second set enough unique elements (i.e. those for which ni = 1) to bring the size of the second set down to M. Then, the number of combinations obtained with the first set and such reduced second set are given by:

M!/(n1!n2!..nk!)

where 1..k includes all the groups in the second set with multiplicity > 1 (and possibly some with multiplicity = 1)

We are now left with N - M elements of the second set (all unique) which we haven't used. We can take the pairings already made and replace some of the used elements of the second set with the same number of elements which were left out. The minimum number of replaceable elements is 1 and the maximum number is G = min(M, N - M).

By replacing X elements (with X between 1 and G) we obtain M!/(n1!n2!..nk!) * (N - M)!/(N - M - X)! new combinations, because we can choose the X elements from the pool of N - M left out elements in (N - M)!/(N - M - X)! ordered ways, and for each such choice we obtain M!/(n1!n2!..nk!) fresh combinations.

Now, what is sum[ M!/(n1!n2!..nk!) * (N - M)!/(N - M - X)! ] for X = 1 .. min(M, N - M) ?

By adding the value for X = 0 we also include in the same formula the initial number of combinations obtained with the reduced second set:

Total = M!/(n1!n2!..nk!) * [sum( (N - M)!/(N - M - X)! ) for X = 0 .. min(M, N - M)]

Did I make any mistake? Can anybody find any blunder?

In any case, even if my solution for 2a is correct, we are still stuck with the case 2b, in which the second set remains larger than the first one even after removing from it all unique elements...

To start, remove from the second set enough unique elements and groups to bring the size of the second set to be <= M. Then, the number of pairings is

M!/(N!(M-N)!) )*( Nr!/(n1!n2!..nk!)

with 1..k being the index covering all groups and unique elements still in the second group and Nr = the size of the second group after removing the elements. Note that it might not be possible to bring Nr to be = M.

We can replace without any problem "old" elements of the second set with unique elements initially left out. For each possible combination of replacements we would just get a fresh set of M!/(N!(M-N)!) )*( Nr!/(n1!n2!..nk!) combinations.

But we have to be careful when replacing groups. We must consider the cases in which we only replace parts of the groups we initally left out. Moreover, we cannot use non-unique elements to replace unique elements used in the initial combination. The largest possible groups should be kept inside the initial selection of the second set, but the matter becomes more complicated when there are groups of size > M.

MMmmm... I must say that I don't like all this... It's become too complicated...

k=min(#M, #N) (easy to compute)

generate k-combinations of M (M is all unique) (easy to compute)

generate k-combinations of N (N is a multi set) (harder, need to know duplicate #'s to compute)

generate permutations of all k-combinations of N (difficult to compute the "of all k-...." part)

then generate M*N (very easy)

Note that the different cases mentioned above simply result in k-comb of M being 1 when #M<#N.

sub fact{

my $f=1;

$f *= $_ for 2..$_[0];

return $f;

}

sub count{

my ($M,@n)=@_;

my @N=(0);

my $N=0;

for( @n ){

push @N,$N+=$_;

}

if( $M >= $N ){

$M = fact($M)/fact($M-$N);

$M /= fact $_ for @n;

return $M;

}

return case2(fact($M),$M,$#n,\@n,

}

sub case2{

my($F,$M,$i,$n,$N)=@_;

return $F if $i<0;

my $s=0;

my $f=1;

for( 0..$n->[$i] ){

last if $M-$_ < 0;

$f *= $_ if $_;

next if $M-$_ > $N->[$i];

$s += case2($F/$f,$M-$_,$i-1,$n,

}

return $s;

}

my @n=(3,4,5,6);

for$M(0..20){

print "count($M,(@n)) = ",count($M,@n),"\n";

}

Or see the earlier JS reference: http://home.earthlink.net/~wzd3/comb.html

However, since the question appears abandoned, the discussion is academic...

Math / Science

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

Suppose A has M distinct objects.

And suppose B has N objects with k distinct groups with ni objects in the ith distinct group. ( so sum(i=0,k){ni}=N )

Case 1

M >= N (so matches have N pairs each)

There are M!/(N!(M-N)!) order independent ways of choosing N elements from A

There are N!/(n1!n2!..nk!) order dependent ways of choosing the N elements of B

Each match will be a combination of an order independent choice of A and an order dependent choice of B

Total= ( M!/(N!(M-N)!) )*( N!/(n1!n2!..nk!) )

Case 2

M < N (so matches have N pairs each)

this is trickier and am thinking.