# Search (java) algorithm to get all permutations of two sets

• Feb 18th 2010, 06:54 AM
pstein
Search (java) algorithm to get all permutations of two sets
Assume I have to sets of numbers e.g.:

setA: 1,2,3,4
setB: 10,11,12,13,14,15,16

Now I want to get all permutations where n (e.g.2) numbers are taken from setA and m (e.g.4) numbers are taken from setB.

Does someone have an efficient algorithm (preferable implemented in Java) which allows to generate all porssible permutations?

Peter
• Feb 20th 2010, 05:48 AM
canyiah
are they non repeating sets? can you reuse numbers in each set?

ie setA: 1,1,2,3,4 ->1's repeat
setB: 12,22,34,44
reusing numbers combination works
setA: 1,2,3,4
setB: 10,11,12,13,14,15,16
how many 2 number combos setA are they
is this valid (1,2), (1,3)? --> 1 is not removed from avaliable choices are choosen

Quote:

Originally Posted by pstein
Assume I have to sets of numbers e.g.:

setA: 1,2,3,4
setB: 10,11,12,13,14,15,16

Now I want to get all permutations where n (e.g.2) numbers are taken from setA and m (e.g.4) numbers are taken from setB.

Does someone have an efficient algorithm (preferable implemented in Java) which allows to generate all porssible permutations?

Peter

• Feb 20th 2010, 11:12 PM
pstein
Quote:

Originally Posted by canyiah
are they non repeating sets? can you reuse numbers in each set?

No, numbers cannot be drawn a second time.
So there are no duplicates.

So I am looking for all permutation like (for 2 and 4 draws like described above):

(1,2, 10,11,12,13),
(1,3, 10,11,12,13),
(1,2, 10,11,12,14),
....
• Feb 21st 2010, 12:58 AM
CaptainBlack
Quote:

Originally Posted by pstein
Assume I have to sets of numbers e.g.:

setA: 1,2,3,4
setB: 10,11,12,13,14,15,16

Now I want to get all permutations where n (e.g.2) numbers are taken from setA and m (e.g.4) numbers are taken from setB.

Does someone have an efficient algorithm (preferable implemented in Java) which allows to generate all porssible permutations?

Peter

You just need a function that will produce all permutations of n+m distinct elements. Then put that inside a loop that generates all the combinations of n distinct elements from set 1 and m distinct elements from set 2. This requires just a simple double loop.

If you regard 1, .. n+m as the indices into the array of elements of a set A of size n+m (note I am using unity based arrays here) you need only produce permutations of the index array to get your permutations of the set. There is pre-existing code out there somewhere that will produce all the permutations of [1, .. , n+m] in order.

CB