Dynamic Nested for loop using recursion (All Permutations)

Question

I was trying to implement something like this.

I have bunch of lists.

Each list has certain numbers.

A - 1,2,3    
B - 4,5    
C - 6,7,8

I want to find all permutations of A, B, C list That is:

1,4,6    
1,4,7    
1,4,8    
1,5,6    
1,5,7    
1,5,8    
2,4,6
and so on...

I could have done this using for loop, but the number of lists are not static.

So I tried using recursion.

Here is what I tried: Calling :

nested(number_of_lists,0, array list of array, current_permutation);

And the function:

static void nested(int depth, int index, ArrayList< ArrayList<Integer> > list, ArrayList<Integer> curr)
{

    if(depth==0)
    {


        ArrayList <Integer> x = new ArrayList<>();
        int i;
        for( i=0;i<curr.size();i++)
        {
            System.out.println(curr.get(i));

            x.add(curr.get(i));
        }
        global.add(x);

        curr.remove(curr.size()-1);

    }
    else
    {

        for(int i=0;i<list.get(index).size();i++)
        {

            curr.add(list.get(index).get(i));

            nested(depth-1, index+1, list, curr);

            if( curr.size()==list.get(index).size())
            {
                curr.remove(curr.size()-1);
            }

            if(index==0 &&(curr.size()-1) == i)
                curr = new ArrayList<>();


        }
    }

}

Global is new array list of array list which had all permutations stored.

But, after two permutations with A, I get wrong answer

and so on..

Where is the code doing wrong. My first two permutations with two elements of A are perfectly fine. Sorry for such a long explanation. Some help would be appreciated.

Paul Boddington · Accepted Answer · 2015-11-26 02:23:55Z

1

You appear to be making this more complicated than it actually is. I have managed to correct this just by commenting out some of your lines.

static void nested(int depth, int index, ArrayList< ArrayList<Integer> > list, ArrayList<Integer> curr)
{

    if(depth==0)
    {


        ArrayList <Integer> x = new ArrayList<>();
        int i;
        for( i=0;i<curr.size();i++)
        {
            System.out.println(curr.get(i));

            x.add(curr.get(i));
        }
        global.add(x);

        //curr.remove(curr.size()-1);

    }
    else
    {

        for(int i=0;i<list.get(index).size();i++)
        {

            curr.add(list.get(index).get(i));

            nested(depth-1, index+1, list, curr);

            //if (curr.size()==list.get(index).size())
            //{
                curr.remove(curr.size()-1);
            //}

            //if(index==0 &&(curr.size()-1) == i)
            //    curr = new ArrayList<>();


        }
    }

}

answered Nov 26, 2015 at 2:23

Paul Boddington

37.8k10 gold badges69 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jay Patel Over a year ago

Thanx a lot. Any other way to do or is this is the best way?

Paul Boddington Over a year ago

There are a few improvements you can make. For example, you don't need both index and depth because they always add up to list.size(). Also, the whole section involving x can just be replaced with global.add(new ArrayList<>(curr));. Finally, try to avoid global variables. Instead, just add global as aa parameter to the method.

Collectives™ on Stack Overflow

Dynamic Nested for loop using recursion (All Permutations)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related