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

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• 08-30-2013, 12:39 PM
Daedalus
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
• 08-30-2013, 12:58 PM
JosAH
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
• 08-30-2013, 01:22 PM
Daedalus
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.
• 08-30-2013, 04:31 PM
JosAH
Re: optimise recursive method that prints all possible rows in a 2D array
Quote:

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
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12