Page 2 of 2 FirstFirst 12
Results 21 to 24 of 24
Like Tree1Likes

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

  1. #21
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Default 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. #22
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,998
    Blog Entries
    7
    Rep Power
    19

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  3. #23
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Default 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. #24
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,998
    Blog Entries
    7
    Rep Power
    19

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

    Quote Originally Posted by Daedalus View Post
    { 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
    cenosillicaphobia: the fear for an empty beer glass

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Recursive method to sort array
    By artur in forum New To Java
    Replies: 2
    Last Post: 03-19-2012, 12:49 PM
  2. Replies: 8
    Last Post: 01-15-2011, 09:39 PM
  3. Array out of bound- Recursive Method
    By hpayandah in forum New To Java
    Replies: 2
    Last Post: 11-12-2010, 08:02 PM
  4. Recursive method using int array, help needed
    By chupalo17 in forum New To Java
    Replies: 4
    Last Post: 09-07-2009, 11:15 PM
  5. Replies: 1
    Last Post: 02-16-2008, 09:10 PM

Posting Permissions

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