Как напечатать возможные перестановки длины массива в Java

Question

Я работаю над задачей, в которой я должен показать возможные перестановки длины массива.Я попробовал несколько хитростей, но он по-прежнему дает список многих выходных данных, и в итоге мой проект потерпел крах.

Я попытался математически и получил ответ "39916800.

Например: для входного массива [3,2,1,4,6], всего 5! = 120 возможных.

Вопрос:

Учитывая, что int [] a = [3, 10, 4, 6, 1, 8, 5, 9, 0, 11, 7, 2].Как часто вам приходится переставлять a с собой, пока вы не получите снова (это так называемая степень a)?

Пример: степень [0,2,1] равна 2, потому что permute([0,2,1], [0,2,1]) = [0,1,2] и перестановка ([0,1, 2], [0,2,1]) = [0,2,1].

Ответ должен состоять из 8 цифр.

Вот мой код:

public class Permute{
static void permute(java.util.List<Integer> arr, int k){
    for(int i = k; i < arr.size(); i++){
        java.util.Collections.swap(arr, i, k);
        permute(arr, k+1);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() -1){
        System.out.println(java.util.Arrays.toString(arr.toArray()));
    }
}
public static void main(String[] args){
    Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0);
}

}

Answer 1

Если ваша задача просто вычислить число возможных перестановок для данного массива, вам не нужно фактически создавать и выводить эти перестановки.Обратите внимание, что число растет в геометрической прогрессии.Вместо этого вы можете просто рассчитать число математически.Просто делай!в простом цикле for.

Если действительно могут быть только уникальные целые числа:

public int permutations(int[] numbers){
  int result = 1;
  for(int i=2; i<=numbers.size(); i++){
    result*=i;
  }
  return result;
}

Answer 2

Взгляните на пример ниже:

public class Main {
    static int[] requestedNumbs = {3,4,6,2,1};


public static List<List<Integer>> permuteUnique(int[] nums, int index) {
        List<List<Integer>> newList = new LinkedList<>();
        if (index == nums.length - 1) {
            List<Integer> newPermute = new LinkedList<>();
            newPermute.add(nums[index]);
            newList.add(newPermute);
        } else {
            List<List<Integer>> oldList = permuteUnique(nums, index + 1);
            for (List<Integer> permute : oldList) {
                int permuteSize = permute.size();
                int i = 0;
                for (; i < permuteSize; i++) {
                    List<Integer> newPermute = new LinkedList<>();
                    newPermute.addAll(permute.subList(0, i));
                    newPermute.add(nums[index]);
                    newPermute.addAll(permute.subList(i, permuteSize));
                    newList.add(newPermute);
                    if (permute.get(i) == nums[index]) {
                        break;
                    }
                }
                if (i == permuteSize) {
                    List<Integer> newPermute = new LinkedList<>();
                    newPermute.addAll(permute.subList(0, permuteSize));
                    newPermute.add(nums[index]);
                    newList.add(newPermute);
                }
            }
        }
        return newList;
    }

    public static void main(String[] args) {
       List<List<Integer>> list = permuteUnique(requestedNumbs,0);
       System.out.println("Size of a list: " + list.size());
       System.out.println(list);
    }
}