Combination/Permutation question

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,
LVL 1
Who is Participating?
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.

Commented:
here is a start:-

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.

0

Experts Exchange Solution brought to you by

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

Commented:
First make a subset of N that IS distinct. Then its a straight permute.

Paul
0
Commented:
OOps! I misread the question. Its more complicated than that isnt it.

Paul
0
Author Commented:
Yeah it is.  Gwynforwebs answer for case 1 makes a lot of sense.  Case 2, is definitely more difficult.  I'm doing this for a program and case 2, while rare will show up at times.  If you can figure out case 2 then you are the man.
0
Commented:
kayhustle, I have given the second part some thought and I do not see a simple formula, (which does not mean there is not one).
0
Author Commented:
I noticed for case 2 you wrote so that they have N pairs each.  That is true for case 1, but for case 2 they should have M pairs each since there can be no repeats.  Maybe this was a copy and paste mistake or a typo, but I'm just checking to make sure that this is not the case you are trying to solve.  If anything I will keep this question open for a few days and see if anybody can figure out case 2 also.  Thanks, kayhustle
0
Commented:
its only a typo, thanks.
0
Retired considering supplemental income.Commented:
If I understand the question correctly, it looks to me that you have a finite number of objects in M (let's call them 'm') and you want to assign a object from N (let's call them 'n').  The only thing we need to know is how may distinct members are in N.

So 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)
0
Retired considering supplemental income.Commented:
I forgot to explicitly state that 'n' is a subset of N and each member is distinct.  It doesn't matter if a member of 'n' is used more than once or not used at all - we just need to know how many unique menbers there are.
0
Commented:
?
0
Commented:
I have a doubt about GwynforWeb's solution, even for case one... For example, order {A,B,C,D,E,F} is one permutation of M, and {1,1,2,3} one of the permuations of N. But, given the multiplication, {C,A,B,D,E,F} and {2,1,1,3} are separate cases, but they yield the same pairs. Based on that, one could conclude that the total must be divided again by the permutations of M, but that looks strange.

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!
0
Commented:
re: Algorithms to do this.  Knuth was the book I used to use for stuff like this, but mine disappeared years ago from my office :-(

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
0
Author Commented:
Give me some time to check all of this out.  Thanks.
0
Commented:
I notice that the "k-PERMUTATIONS of the N multi set" does not work, but if M>N then the code works for PERMUTATIONS of the N multi set.   I did stumble across the statement that there is no general formula for the number of "k-PERMUTATIONS of the N multi set", with a challenge to prove it....  There is sure to be an algorithm floating around.  I think one could put the algorithm to generate "k-sets of an N multi set "and the algorithm for "PERMUTATIONS of the N multi set".

More to follow, this is fun to play with!
0
Commented:
Ok, take a look at http://home.earthlink.net/~wzd3/comb.html

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.

0
Commented:
... it is gratifying to here that other can not find a formula for part 2.  In attempting it I reduced it to the solution of some partition problems that I was fairly sure (but not certain) did not have known formulea.

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.
0
Retired considering supplemental income.Commented:
The way you restated the problem this becomes a conditional probability problem.

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.
0
Commented:
Let me see whether I understand it correctly: you have two sets of M and N objects and you want to pair them.

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  ;-)
0
Commented:
The difference is that the M objects are distinct,
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<=nk,m1+m2+..mk=M){M!/(m!m2!..mk!)}
does not appear to have a simple closed form expression.
0
Commented:
Sorry, I should have read everything more carefully.  I see the point.

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...
0
Commented:
In 2a, it looks like you have left out the case where some non-unique ni are removed to bring the size of the second set down to M.
0
Commented:
That's 2b.  The definition of 2a is precisely M >= {sum(ni) for all ni > 1}.  That is, you don't need to remove non-unique elements.
0
Commented:
Perhaps the reasoning I applied to case 2a can be extended to 2b.

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...
0
Commented:
Yes, it seems to be computationally difficult.  However the apparently abandoned question asks for a possible algorithim as well.  I think the general proceedure stated above with computational difficulty (i.e. general equation case) is:

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.

0
Commented:
#!/bin/perl
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,\@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,\$N);
}
return \$s;
}

my @n=(3,4,5,6);
for\$M(0..20){
print "count(\$M,(@n)) = ",count(\$M,@n),"\n";
}
0
Commented:
Or see the earlier JS reference: http://home.earthlink.net/~wzd3/comb.html
0
Commented:
But the counting you do is probably a lot quicker than generate and count.

However, since the question appears abandoned, the discussion is academic...
0
Author Commented:
The original project I was using this for was put on hold, but the question hasn't been abandoned.  This is a lot of info to digest right now but I am still going through each one of everybodys answers.
0
Commented:
ok, sorry about the wrong assumption.   No comment for 2 months usually means that, but I'm glad to hear you are still reviewing it.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
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.