List of Lists keeping same value in the for loop Java-CodePudding

class Solution {
    public void nextPermutation(int[] nums) {
      List<List<Integer>> list = new ArrayList<List<Integer>>();
        List<Integer> tempList = new ArrayList<Integer>();
        int temp=0;
        for(int i : nums)
        {
            tempList.add(i);
        }
        List<Integer> list2 = new ArrayList<Integer>();
        
        list.add(tempList);
        System.out.println(tempList);
         for(int i=0;i<nums.length;i  )
            for(int j=0;j<nums.length-1;j  )
            {
                temp = tempList.get(j);
                tempList.set(j,tempList.get(j 1));
                tempList.set(j 1,temp);
                
                System.out.println(" \n*" tempList " *\n");
                
                list.add(tempList);
            }

        System.out.println(list);
    }
}

Output: [1, 2, 3]

*[2, 1, 3] *

*[2, 3, 1] *

*[3, 2, 1] *

*[3, 1, 2] *

*[1, 3, 2] *

*[1, 2, 3] *

[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

why the list is not getting updated tempList value though it's updating in SOP

CodePudding user response：

The problem in your code is that you're using the same tempList instance at every iteration.

What you're doing is simply taking a List, sorting it in a specific order, adding it to the result list and then still working on the same instance already added into the final List.

That very element that you keep working on is being sorted from outside but it's the same list contained inside the final List and added multiple times. In fact, if you'd print your general list too at each iteration you will see each of its elements changing according to the last permutation.

To achieve what you're trying to do, you should create a brand-new instance of tempList based on its previous permutation.

public static void nextPermutation(int[] nums) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    int temp = 0;

    //Generating the first permutation equals to the array
    List<Integer> listTemp = new ArrayList<>(Arrays.stream(nums).collect(ArrayList<Integer>::new, ArrayList::add, ArrayList::addAll));

    for (int i = 0; i < nums.length; i  ) {
        for (int j = 0; j < nums.length - 1; j  ) {
            //Generating a new list instance with the elements of the previous permutation
            listTemp = new ArrayList<>(listTemp);

            //Permutation
            temp = listTemp.get(j);
            listTemp.set(j, listTemp.get(j   1));
            listTemp.set(j   1, temp);

            System.out.println("*"   listTemp   " *");

            //Adding the new reference to the final list
            list.add(listTemp);
        }
    }
    System.out.println(list);
}

CodePudding user response：

at the time of

System.out.println(" \n*" tempList " *\n"); in side inner loop you are using printing the updated list,and same templist is being added to list object,so the list is containing 9 copies of same object and hence whatever the last value tempList has will be printed 9 times , to correct it , you will need to make new copy of the templist or say last entry of list and then perform modificaiton of it,here is the updated code

        import java.util.*;
        class Solution {
            public static void nextPermutation(int[] nums) {
              List<List<Integer>> list = new ArrayList<List<Integer>>();
            List<Integer> tempList = new ArrayList<Integer>();
            int temp=0;
            for(int i : nums)
            {
                tempList.add(i);
            }
            List<Integer> list2 = new ArrayList<Integer>();
            
            list.add(tempList);
            List<Integer> curList;
            System.out.println(tempList);
             for(int i=0;i<nums.length;i  ){
               //create a new list for calculation,and copy last list in it
                for(int j=0;j<nums.length-1;j  )
                {
               curList= new ArrayList<Integer>(list.get(list.size()-1));
                temp = curList.get(j);
                curList.set(j,curList.get(j 1));
                curList.set(j 1,temp);
                
                System.out.println(" \n*" curList " *\n");
                
                list.add(curList);
                }
             }

            System.out.println(list);
            }
           public static void main(String args[]){
            int nums[]={1,2,3};
              Solution.nextPermutation(nums);
           }
        }

hope this will help.

CodePudding user response：

I looked at your code ran it a few times, I found the issue I can't believe it took me so long to see. This would be hard to catch if you were a beginner, basically when you're adding the tempList into the list using:

list.add(tempList);

It's not doing what you might think. Since objects in java are actually memory references to somewhere else what you're adding to this list is a lot of memory references not copies of the data which is what you want. The problem with storing these memory references is that they get updated even after you've put them down because you're continuing to change the tempList.

To try to explain this better imagine you're pointing at a house and this house is orange. Now with your other hand you point at the same house except it's been repainted and now the house is green. So you have two fingers pointed at the house, both fingers are pointing at a green house even though when you initially pointed your first finger the house was orange. This same thing is happening in your code because the tempList gets updated continually.

Luckily fixing this issue is really simple, all you have to do is copy the tempList into a new ArrayList and store the new ArrayList instead of tempList. That can be done one of two ways, the first looks like this:

list.add(new ArrayList<>(tempList));

Or you can create the new ArrayList outside the add() call like this:

ArrayList<Integer> resultList = new ArrayList<>(tempList);
list.add(resultList);

Hope that helps :)