[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Combination/Permutation question

Posted on 2004-11-11
32
Medium Priority
?
604 Views
Last Modified: 2011-09-20
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,  
0
Comment
Question by:kayhustle
  • 7
  • 5
  • 4
  • +5
29 Comments
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 340 total points
ID: 12561170
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12564945
First make a subset of N that IS distinct. Then its a straight permute.

Paul
0
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12564954
OOps! I misread the question. Its more complicated than that isnt it.

Paul
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 1

Author Comment

by:kayhustle
ID: 12568087
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12569502
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
 
LVL 1

Author Comment

by:kayhustle
ID: 12571959
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12572104
its only a typo, thanks.
0
 
LVL 16

Assisted Solution

by:dhsindy Sparrow
dhsindy Sparrow earned 332 total points
ID: 12609560
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
 
LVL 16

Expert Comment

by:dhsindy Sparrow
ID: 12609616
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12610855
?
0
 
LVL 58

Assisted Solution

by:harfang
harfang earned 332 total points
ID: 12643346
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
 
LVL 3

Expert Comment

by:wzd3
ID: 12742552
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
 
LVL 1

Author Comment

by:kayhustle
ID: 12743354
Give me some time to check all of this out.  Thanks.
0
 
LVL 3

Expert Comment

by:wzd3
ID: 12746177
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
 
LVL 3

Expert Comment

by:wzd3
ID: 12746907
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12819820
... 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
 
LVL 16

Expert Comment

by:dhsindy Sparrow
ID: 12884601
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
 
LVL 5

Expert Comment

by:PointyEars
ID: 13290350
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
 
LVL 85

Assisted Solution

by:ozo
ozo earned 332 total points
ID: 13293215
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
 
LVL 5

Assisted Solution

by:PointyEars
PointyEars earned 332 total points
ID: 13293434
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
 
LVL 85

Expert Comment

by:ozo
ID: 13293463
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
 
LVL 5

Expert Comment

by:PointyEars
ID: 13293513
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
 
LVL 5

Expert Comment

by:PointyEars
ID: 13293740
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
 
LVL 3

Assisted Solution

by:wzd3
wzd3 earned 332 total points
ID: 13294046
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
 
LVL 85

Expert Comment

by:ozo
ID: 13296894
#!/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
 
LVL 3

Expert Comment

by:wzd3
ID: 13298566
Or see the earlier JS reference: http://home.earthlink.net/~wzd3/comb.html
0
 
LVL 3

Expert Comment

by:wzd3
ID: 13298578
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
 
LVL 1

Author Comment

by:kayhustle
ID: 13299011
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
 
LVL 3

Expert Comment

by:wzd3
ID: 13301679
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

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Aerodynamic noise is the cause of the majority of the noise produced by helicopters. The inordinate amount of noise helicopters produce is a major problem in the both a military and civilian setting. To remedy this problem the use of an aerogel coat…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses
Course of the Month17 days, 17 hours left to enroll

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question