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

Question

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]

Why the solution you found in these other threads don't suit your needs ? The Collections2.permutations(vals) does exactly what you want. — Anthony BONNIER
– Anthony BONNIER, Commented Sep 5, 2018 at 7:59
It is safe to say that I'm still a beginner. To be honest the posted solution does look good, I just don't know how to actually use it. For example with myArray to aktually go through it in these orders. I would really appreciate it if you could maybe post an example of how I could do this! Thank you very much! — NikNet
– NikNet, Commented Sep 5, 2018 at 8:10
The for (List<Integer> val : orderPerm) line in your code seems to be exactly the example that you asked for. It goes through all permutations, one at a time. If you want something else, then please be more specific in your question. — fishinear
– fishinear, Commented Sep 5, 2018 at 11:14
Thank you fishinear, say I would want to print out the numbers, how could I do that? Or even better store it in a two dimensional field. — NikNet
– NikNet, Commented Sep 5, 2018 at 12:59
I can try to make an example for you, using your array and printing the numbers out. But, I don't understand how you could store them in a two dimensional field. What would be the two dimensions ? — Anthony BONNIER
– Anthony BONNIER, Commented Sep 5, 2018 at 13:48

Anthony BONNIER · Accepted Answer · 2018-09-05 15:20:10Z

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

Joop Eggen · Accepted Answer · 2018-09-05 16:45:34Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related