Подстановка цикла for со всеми перестановками массива - Java

Question

Как можно заменить цикл for

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

, который будет проходить через массив следующим образом: (1,2, ... n) для чего-то похожего, что будет проходить через все перестановки элементов массива. В других темах я нашел это ( 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());
}

Но я не могу объединить два, чтобы сделать "все перестановки для цикла". Ваша помощь очень ценится. Просто для пояснения для массива размера 3 я хочу, чтобы цикл проходил через массив с индексами:

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

Answer 1

Для более алгоритмического решения. Он будет делать копии массивов, как «неизменяемые» объекты. Обслуживающий массив перестановок содержит индексов , которые должны применяться к исходному массиву.

    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 доставляет массив с индексами 0, 1, 2, 3, ... - ничего не переставляя.

/**
 * 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();
}

nextPermutation "считает вверх", принимая следующую "большую" последовательность индексов.

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;
}

И затем мы хотим применить перестановку к массиву, получив перестановочный массив.

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;
}

Некоторое внимание уделяется тому, что вместо копирования можно менять массивы на месте.

Answer 2

Вот пример, как вы спросили:

// 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));
}

Просто чтобы прояснить, вот импорт:

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

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

Отображает этот вывод:

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

Это в скобках:

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

Я импортировал 2 баночки в своем проекте (используя Maven), чтобы использовать коллекции Guava:

<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>

Если вы не знаете, как использовать Maven, просто загрузите эти jar-файлы из репозитория maven и скопируйте их в рабочее пространство, чтобы добавить их в путь к классам Java.

• https://mvnrepository.com/artifact/com.google.guava/guava/26.0-jre
• https://mvnrepository.com/artifact/com.google.guava/guava-collections/r03

Если вы не работаете в рабочей области (например, Eclipse), просто скомпилируйте ваш класс, используя опцию javac -classpath, чтобы добавить эти jar-файлы в компиляцию.

Вот документация по компиляции javac: https://www.cis.upenn.edu/~bcpierce/courses/629/jdkdocs/tooldocs/solaris/javac.html