Java: перестановка массива

Question

Я не очень знаком с рекурсией в Java. Я пытаюсь написать метод, который вычисляет все перестановки массива целых чисел. Мне нужно изменить следующий идеально работающий метод так, чтобы вместо печати для проверки всех перестановок массива он вставлял их в двумерный массив. Таким образом, входные данные метода - это массив из n целых чисел, а выходные данные - это двумерный массив с n! строки и n столбцов. Программа мне нужно изменить это:

public static void permute(int[] array, int k)
{
    for(int i=k; i<array.length; i++)
    {
        int temp;
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
        permute(array, k+1);
        int temp2;
        temp2 = array[i];
        array[i] = array[k];
        array[k] = temp2;
    }
    if (k == array.length-1)
    {
        Array.printValues(array);
    }
}

Итак, мне нужно что-то вроде этого:

public static int[][] permute(int[] array, int k)
{
    //code here
}

Спасибо.

Answer 1

Вставьте их в список, а затем извлеките из него массив. Вы можете перейти непосредственно к int[][], но вы не знаете первое значение измерения без дополнительного повторения.

public static int[][] permuteToArray(int[] array, int k){
    ArrayList<int[]> arrL=new ArrayList<>();
    for(int i=k; i<array.length; i++)
    {
        int temp;
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
        permute(array, k+1, arrL);
        int temp2;
        temp2 = array[i];
        array[i] = array[k];
        array[k] = temp2;
    }
    if (k == array.length-1)
    {
        arrL.add(array);
    }
    return arrL.toArray(new int[][]);
}

+ Изменить permute( быть:

public static void permute(int[] array, int k, ArrayList arrL) //raw type, I know
{
    for(int i=k; i<array.length; i++)
    {
        int temp;
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
        permute(array, k+1);
        int temp2;
        temp2 = array[i];
        array[i] = array[k];
        array[k] = temp2;
    }
    if (k == array.length-1)
    {
        arrL.add(array);
    }
}

Answer 2

 public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void permute(int[] array, List<int[]> cache, int k)
{

    if (k == array.length-1)
    {
        cache.add(array.clone()); //use clone, or you will get the same int array
        return;
    }
    for(int i=k; i<array.length; i++)
    {
        swap(array, i,k);
        permute(array, cache, k+1);
        swap(array, i, k);
    }
}

Answer 3

public static void _permute(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int k, boolean[] status, int[] array)
{
  if (cur.size() == k) {
    res.add((ArrayList<Integer>)cur.clone());
    return;
  }
  for (int i = 0; i < k; i++)
  {
    if (status[i]) continue;
    cur.add(array[i]);
    status[i] = true;
    _permute(res, cur, k, status, array);
    status[i] = false;
    cur.remove(new Integer(array[i]));
  }
}

public static ArrayList<ArrayList<Integer>> permute(int[] array, int k)
{
  ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  ArrayList<Integer> cur = new ArrayList<Integer>();
  boolean[] status = new boolean[k];
  for (int i = 0; i < k; i++) 
  {
    status[i] = false;
  } 
  _permute(res, cur, k, status, array);
  return res;
  //code here
 }

Вы можете получить все перестановки массива в списке массивов. Я думаю, что вы можете извлечь массив из списка самостоятельно. И будьте осторожны, эта функция может удалить дубликаты, если в исходном массиве одинаковые числа.

Answer 4

Я могу привести вам пример рекурсивного алгоритма перестановки. Он основан на том, что перестановка n элементов основана на перестановке n-1 элементов.

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

class Permutation {

    public static void main(String[] args) {
        List<Object> input = new ArrayList<>();
        input.add(1);
        input.add(2);
        input.add(3);
        print(permutation(input));
    }

    public static void print(List<List<Object>> list) {
        for (List<Object> objects : list) {
            System.out.println(objects);
        }
    }

    public static List<List<Object>> permutation(List<Object> input) {
        if (input.isEmpty()) {
            throw new IllegalStateException();
        }
        // This is end condition for recursion
        if (input.size() == 1) {
            List<List<Object>> result = new ArrayList<>();
            result.add(input);
            return result;
        }
        return merge(input.get(0), permutation(input.subList(1, input.size())));
    }

    private static List<List<Object>> merge(Object o, List<List<Object>> input) {
        List<List<Object>> result = new ArrayList<>();
        int inputSize = input.get(0).size();
        for (int i = 0; i < inputSize + 1; i++) {
            for (List<Object> oneRow : input) {
                // copy the row and insert additional element
                List<Object> oneRowExpanded = new ArrayList<>();
                oneRowExpanded.addAll(oneRow);
                oneRowExpanded.add(i, o);
                result.add(oneRowExpanded);
            }
        }
        return result;
    }
}

Это напечатает следующее:

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