There is a code that iterates through all possible combinations of the List<Integer> elements:

 import java.util.Arrays; import java.util.Collections; import java.util.List; public class Permute_sout { static void permute(List<Integer> arr, int k) { for (int i = k; i < arr.size(); i++) { Collections.swap(arr, i, k); permute(arr, k + 1); Collections.swap(arr, k, i); } if (k == arr.size() - 1) { System.out.println(Arrays.toString(arr.toArray())); } } static void permute(List<Integer> arr) { permute(arr, 0); } public static void main(String[] args) { permute(Arrays.asList(1, 2, 3)); } }

I need to change the permute method so that it does not output data to the console, but returns a List<List<Integer>> :

 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class Permute { private static List<List<Integer>> lists = new ArrayList<>(); static List<List<Integer>> permute(List<Integer> arr, int k) { for (int i = k; i < arr.size(); i++) { Collections.swap(arr, i, k); permute(arr, k + 1); Collections.swap(arr, k, i); } if (k == arr.size() - 1) { lists.add(arr); //добавление в список комбинаций } return lists; } static List<List<Integer>> permute(List<Integer> arr) { return permute(arr, 0); } public static void main(String[] args) { System.out.println(permute(Arrays.asList(1, 2, 3))); } }

However, this code writes to all List<List<Integer>> elements only the first List<Integer> of the search. Where is the mistake?

  • ideone.com/WsjFQ8 you have it all works - Senior Pomidor
  • @SeniorPomidor nea. Conclusion [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]] instead of the required [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]] can not be called true. More precisely, can not be called such as required. - Regent
  • pancake, did not notice ( - Senior Pomidor

1 answer 1

The problem is that the permute method works with the same list of arr , which is constantly changing (and in the end it turns out to be the same as it was).

Accordingly, if you have added the same list to lists many times, you will end up with the same list (the final state arr ) many times.

In lists you need to add a copy of arr :

 lists.add(new ArrayList<>(arr));