This discussion is archived
7 Replies Latest reply: Jun 18, 2010 9:10 AM by 843789 RSS

All possible combinations given a 2D Array

843789 Newbie
Currently Being Moderated
Hi all,

I have a 2D array String[][] stringarray.
I use the 2D array like this: String [num of items][values of items]. Num of items means the number of unique items, and values of items is its possible values.

I want to find out all the possible combinations of it. For example, given a 2D array with num of items = 3 and value of items = 2:

[0] [0] and [1] [0] and [2] [0]
[0] [0] and [1] [0] and [2] [1]

[0] [0] and [1] [1] and [2] [0]
[0] [0] and [1] [1] and [2] [1]

[0] [1] and [1] [0] and [2] [0]
[0] [1] and [1] [0] and [2] [1]

[0] [1] and [1] [1] and [2] [0]
[0] [1] and [1] [1] and [2] [1]

I currently am using recursion however, I am having difficulty in finding the correct way to do it.

Please help me, this is driving me crazy!

Thank you very much!
  • 1. Re: All possible combinations given a 2D Array
    699554 Newbie
    Currently Being Moderated
    Waterborne wrote:
    I want to find out all the possible combinations of it.
    Permutations.
    I currently am using recursion however, I am having difficulty in finding the correct way to do it.
    Can't say I can help unless you explain to us the difficulties your facing, possibly post your initial attempts.

    Mel
  • 2. Re: All possible combinations given a 2D Array
    843789 Newbie
    Currently Being Moderated
    Melanie_Green wrote:
    Waterborne wrote:
    I want to find out all the possible combinations of it.
    Permutations.
    At least the example shows combinations. The are 2^3 = 8 of them. If you look at the second index on each row, it goes like this,

    0 0 0
    0 0 1
    0 1 0
    0 1 1
    1 0 0
    1 0 1
    1 1 0
    1 1 1

    These are the 8 combinations of 2 values (0 and 1) in 3 positions.

    The first index goes like this on every row,

    0 1 2

    representing the 3 positions.

    From what I can see everything here can be easily generated using nested loops. The loops can be fixed if their number is known beforehand, or called recursively to the required nested depth if not.
  • 3. Re: All possible combinations given a 2D Array
    843789 Newbie
    Currently Being Moderated
    Hi Melanie and Wastrel, thanks for replying:

    Yes, I am using recursion since the num of items and possible values may change.

    I am having trouble with iterating the third:

    Let's say it looks like this:

    [0, 0]
    -> [1, 0]
    -> [2, 0]
    -> [2, 1]
    ->[1, 1]
    -> [2, 0]
    -> [2, 1]

    Since I am adding them into only 1 String (ex. string input = [0,0] + [1,0] + [2,0]), I am returning the final. Problem is, my looping of the 2nd and 3rd iterations exit because I return. Therefore I do not get [2,1] and [1,1].

    Thank you.
  • 4. Re: All possible combinations given a 2D Array
    843789 Newbie
    Currently Being Moderated
    Waterborne wrote:
    Hi Melanie and Wastrel, thanks for replying:

    Yes, I am using recursion since the num of items and possible values may change.
    I suggest you first develop an iterative solution based on nested loops. Each position will be one nesting and the loops will iterate the number of values. Then you generalize this to a recursive solution.

    The recursive function will have one loop only. Each recursive call will represent one level down the loop nesting in the iterative solution.
  • 5. This Thread is now moved
    DarrylBurke Guru Moderator
    Currently Being Moderated
    Note: This thread was originally posted in the [Java Programming|http://forums.sun.com/forum.jspa?forumID=31] forum, but moved to this forum for closer topic alignment.
  • 6. Re: All possible combinations given a 2D Array
    843789 Newbie
    Currently Being Moderated
    Hi again, thanks for the reply.

    I have no problem making it in iteration: Given a 2D array of [3] [index], I just do this:
            int m = 0;
            for(int a = 0; a < index; a++)
            {
                for(int b = 0; b < index; b++)
                {
                    for(int c = 0; c < index; c++)
                    {
                        System.out.println("TEST: " + possibledecrypted[m][a] + " " +  possibledecrypted[m+1] + " " + possibledecrypted[m+2][c]);
    }
    }
    }
    I picture this in recursion as:
    String PrintKey(String[][] possibledecrypted, int m, int maxnumber, int index)
    {

    if(m == maxnumber)
    {
    return possibledecrypted[m][curindex];
    }
    else
    {
    for(int m = 0; m < index; m++)
    {
    System.out.println("TEST: " + possibledecrypted[m][a] + " " + PrintKeyAgain(possibledecrypted, m + 1, maxnumber, index));
    }
    }

    }
    Problem is, the above code does not work properly at all. It does not get all the proper combinations. Also, it just prints 2 number of items.
    
    Please help me, recursions always blow my head off!
    
    Thank you!                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
  • 7. Re: All possible combinations given a 2D Array
    843789 Newbie
    Currently Being Moderated
    Hi all,

    I finally solved this problem. Here is the recursive printing of the values:
    public static void PrintPossibleKeys(String[][] possibledecrypted, int i, int j, int max, int index, String curstring)
        {
            if((i+1) == max)
            {
                for(int c = 0; c < index; c++)
                {
                    System.out.println("Test: " + curstring + " " + possibledecrypted[i][c]);
                }
            }
            else
            {
                for(int b = 0; b < index; b++)
                {
                    PrintPossibleKeys(possibledecrypted, (i+1), 0, max, index, (curstring) + " " + possibledecrypted);
    }
    }

    }
    The main idea I used is to collectively collect the strings traversed and pass it as a parameter then print everything out once it reaches the final.
    
    Special thanks to wastrel for giving me tips on how to create recursions (first try iterative solution).
    
    Thank you all!