yamayama - 7 months ago 41

Java Question

I am trying to write a code that generates a List containing all the possible permutations of a given int array.

I have found online a method ("nextPermutation" in the code below) that allows to do that, and I am trying to implement it into a basic code, but it does not work.

The problem is that when I try to dynamically add the array containing the new permutation to the list, all the previous permutations already stored in the list are replaced with the new one.

I guess the problem is somehow related with the fact that my "nextPermutation" is non-static, but I have no idea about what I should do to fix it.

Any suggestion?

`package lang_dist;`

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class lang_dist {

public boolean nextPermutation(int[] array) {

// Find longest non-increasing suffix

int i = array.length - 1;

while (i > 0 && array[i - 1] >= array[i])

i--;

// Now i is the head index of the suffix

// Are we at the last permutation already?

if (i <= 0)

return false;

// Let array[i - 1] be the pivot

// Find rightmost element that exceeds the pivot

int j = array.length - 1;

while (array[j] <= array[i - 1])

j--;

// Now the value array[j] will become the new pivot

// Assertion: j >= i

// Swap the pivot with j

int temp = array[i - 1];

array[i - 1] = array[j];

array[j] = temp;

// Reverse the suffix

j = array.length - 1;

while (i < j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++;

j--;

}

// Successfully computed the next permutation

return true;

}

public static void main( String[] args )

{

int[] array = {0, 0, 1, 1, 1, 1};

List<int[]> rowList = new ArrayList<int[]>();

List<int[]> results = new ArrayList<int[]>();

lang_dist d=new lang_dist();

while (d.nextPermutation(array)){

System.out.println("Permutation:" + Arrays.toString(array));

results = Arrays.asList(array);

rowList.add(results.get(0));

};

System.out.println("---");

for (int[] row : rowList) {

System.out.println("Row = " + Arrays.toString(row));

}

}

}

Answer

The (main) problem is that you store your results in the same array at every permutation. Therefore, `rowList`

contains n references to the same array.

To (quickly) fix the problem, you need to create a new array for every permutation:

`results = Arrays.asList(array.clone());`

Besides, `results`

here is redundant, use `rowList`

**or** `results`

to store your permutations.

I suggest you have a look at: Are arrays passed by value or passed by reference in Java? Is Java "pass-by-reference" or "pass-by-value"?