CODEWITHSUNDEEP
javaarrayspermutation
NikNet
NikNet

Reputation: 45

Substituting a for-loop with all permutations of an array - Java

How is it possible to substitute a for-loop

for(int i = 0; i < myArray.length; i++){
    System.out.println(myArray[i]);
}

which will go through the array like this: (1,2,...n) for something similar that will go through all permutations of the elements of the array. In other threads I have found this (source): 

public void permutations () {

    List<Integer> vals = Ints.asList(new int[] {1, 2, 3});

    Collection<List<Integer>> orderPerm = Collections2.permutations(vals);

    for (List<Integer> val : orderPerm) {
        logger.info(val);
    }

    assertEquals(6, orderPerm.size());
}

But I am unable to combine the two to make an "all permutations for-loop". Your help is greatly apprechiated. Just for clarification for an array of size 3 I want the loop to go through the array with the indices:

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

Upvotes: 1

Views: 968

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109613

For a more algorithmic solution. It will make copies of arrays, as "immutable" objects. A permutation array serves contains the indexes to be applied on the original array.

    int[] myArray = new int[] {10, 20, 30};
    int[] permutation = zeroPermutation(myArray.length);
    int n = 1 << myArray.length;
    for (int i = 0; i < n; ++i) {
        int[] arr = permute(myArray, permutation);
        System.out.printf("[%d] %s%n", i, Arrays.toString(arr));
        permutation = nextPermutation(permutation);

    }

zeroPermutation delivers the array with indices 0, 1, 2, 3, ... - not permuting anything.

/**
 * An array 0, 1, 2, ...´, length-1.
 * <code>array[zeroPermutation(array.length)[i]] == array[i]</code>
 * @param length of array.
 * @return identity permutation.
 */
static int[] zeroPermutation(int length) {
    return IntStream.range(0, length).toArray();
}

The nextPermutation "counts upwards" taking the next "larger" sequence of indices.

static int[] nextPermutation(int[] permutation) {
    // Find the first position i from the right, that can made larger out of the right part.
    // ... [4] < 7 > 5 > 3 > 2 > 0
    //      i
    int i = permutation.length - 2;
    while (i >= 0 && permutation[i] > permutation[i + 1]) {
        --i;
    }
    if (i < 0) {
        return zeroPermutation(permutation.length);
    }
    // Take the next larger:
    // ... [5] < 7 > 4 > 3 > 2 > 0
    //      \________/
    //      i        j
    int xi = permutation[i];
    int j = permutation.length - 1;
    while (j > i && xi > permutation[j]) {
        --j;
    }
    int[] next = Arrays.copyOf(permutation, permutation.length);
    next[i] = next[j];
    next[j] = xi;

    // And for the right part the smallest permutation:
    // By reversal of the order.
    // ... [5] < 0 < 2 < 3 < 4 < 7
    int nright = permutation.length - (i + 1);
    for (int k = 0; k < nright / 2; ++k) {
        int xk = next[i + 1 + k];
        next[i + 1 + k] = next[permutation.length - 1 - k];
        next[permutation.length - 1 - k] = xk;
    }
    return next;
}

And then we want to apply the permutation to an array, receiving the permutated array.

static int[] permute(int[] array, int[] permutation) {
    int[] permuted = new int[array.length];
    for (int i = 0; i < array.length; ++i) {
        permuted[i] = array[permutation[i]];
    }
    return permuted;
}

Some care is taken, that instead of copying one could change the arrays in-situ.

Upvotes: 0

Anthony BONNIER
Anthony BONNIER

Reputation: 355

Here is an example, as you asked :

// myArray with 1,2,3,...,n values
int[] myArray = new int[] {1, 2, 3};

// Convert it in a List to use it through guava Collections
List<Integer> vals = Ints.asList(myArray);  

// Compute all permutations using Guava Collections API
Collection<List<Integer>> orderPerm = Collections2.orderedPermutations(vals);

// Convert the result in List of Lists to get indexed values by number (to display them, easier to access than using an Iterator)
List<List<Integer>> myTwoDimensionalArray = new ArrayList<>(orderPerm);

// Loop over the result to display the 2 dimensional array
for (int dim1 = 0 ; dim1 < myTwoDimensionalArray.size() ; dim1++) {

  String dim2 = "";
  // Here I build a string to display the numbers without the brackets (not necessary)
  for (int i = 0 ; i < myTwoDimensionalArray.get(dim1).size() ; i++) {
    if (i > 0) {
      dim2 += ",";
    }
    dim2 += myTwoDimensionalArray.get(dim1).get(i);
  }

  // Displaying the 2 dimensional results
  System.out.println(dim1 + " : " + dim2);
  // Uncomment here to display with brackets directly
  // System.out.println(dim1 + " : " + myTwoDimensionalArray.get(dim1));
}

Just to be clear, here are the imports :

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import com.google.common.collect.Collections2;
import com.google.common.primitives.Ints;

It displays this output :

0 : 1,2,3
1 : 1,3,2
2 : 2,1,3
3 : 2,3,1
4 : 3,1,2
5 : 3,2,1

This one with brackets :

0 : [1, 2, 3]
1 : [1, 3, 2]
2 : [2, 1, 3]
3 : [2, 3, 1]
4 : [3, 1, 2]
5 : [3, 2, 1]

I've imported 2 jars in my project (using Maven) to use Guava collections :

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>26.0-jre</version>
</dependency>
<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava-collections</artifactId>
  <version>r03</version>
</dependency>

If you don't know how to use Maven, just download these jars from the maven repository and copy them in your workspace to add them in your Java classpath.

If your don't work in a workspace (like Eclipse), just compile your class using the javac -classpath option to add these jars in the compilation.

Here is a documentation about javac compilation : https://www.cis.upenn.edu/~bcpierce/courses/629/jdkdocs/tooldocs/solaris/javac.html

Upvotes: 2

Related Questions