Thread: optimise recursive method that prints all possible rows in a 2D array

1. Member
Join Date
Sep 2008
Posts
14
Rep Power
0

Re: optimise recursive method that prints all possible rows in a 2D array

yes, you're right I was getting confused between permutations and combinations. I only need combinations but with one slight caveat. one or two of the numbers in the array are "required numbers" ie, each array must have at least one of them.

ie, given the array {1,2,3,4} with required number 2:

produces arrays
{1,2,3,4}
{1,2}
{2,3}
{2,4}
{2,3,4}

I don't care about the order as I sort them anyway but I can't have dupes. Instead of iterating over all results and removing dupes, I just put them in a HashSet<int[]> with a custom hash mapping based on elements (but not position of elements) rather than the default Object.hashCode();. It would be nice however to have an algorithm that did not generate them in the first place.

Thanks again
Last edited by Daedalus; 08-30-2013 at 12:47 PM.

2. Re: optimise recursive method that prints all possible rows in a 2D array

Why aren't the lists { 2 } and { 1, 2, 3 } and { 2, 4 } part of the result?

kind regards,

Jos

3. Member
Join Date
Sep 2008
Posts
14
Rep Power
0

Re: optimise recursive method that prints all possible rows in a 2D array

{ 1, 2, 3 } should be there I forgot to put it in, and {2,4} is there already. I don't need individual values only 2 or more has any use to me although there is no harm in having them, it's just that I will need to remove them again afterwards.

4. Re: optimise recursive method that prints all possible rows in a 2D array

Originally Posted by Daedalus
{ 1, 2, 3 } should be there I forgot to put it in, and {2,4} is there already. I don't need individual values only 2 or more has any use to me although there is no harm in having them, it's just that I will need to remove them again afterwards.
Suppose you want all combinations of the numbers { 1, 3, 4 } (there are eight): { }, { 1 }, { 3 }, { 1, 3 }, { 4 }, { 1, 4 }, { 3, 4 }, { 1, 3, 4 }; add 2 to each set and voila. Generating combinations of n digits (whatever they are) is easy: count in binary from 0 (inclusive) to 2^n (exclusive); it bit i equals 1 then the ith digit is a member of that particular combination.

kind regards,

Jos

Page 2 of 2 First 12

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•