Java-код для перестановки списка чисел

Question

Я написал программу, чтобы найти все возможные перестановки данного списка предметов. Это точно означает, что моя программа печатает все возможные значения P(n,r) для r=0 до n

Ниже приведен код:

package com.algorithm;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations<T> {
    public static void main(String args[]) {
        Permutations<Integer> obj = new Permutations<Integer>();
        Collection<Integer> input = new ArrayList<Integer>();
        input.add(1);
        input.add(2);
        input.add(3);

        Collection<List<Integer>> output = obj.permute(input);
        int k = 0;
        Set<List<Integer>> pnr = null;
        for (int i = 0; i <= input.size(); i++) {
            pnr = new HashSet<List<Integer>>();
            for(List<Integer> integers : output){
            pnr.add(integers.subList(i, integers.size()));
            }
            k = input.size()- i;
            System.out.println("P("+input.size()+","+k+") :"+ 
            "Count ("+pnr.size()+") :- "+pnr);
        }
    }
    public Collection<List<T>> permute(Collection<T> input) {
        Collection<List<T>> output = new ArrayList<List<T>>();
        if (input.isEmpty()) {
            output.add(new ArrayList<T>());
            return output;
        }
        List<T> list = new ArrayList<T>(input);
        T head = list.get(0);
        List<T> rest = list.subList(1, list.size());
        for (List<T> permutations : permute(rest)) {
            List<List<T>> subLists = new ArrayList<List<T>>();
            for (int i = 0; i <= permutations.size(); i++) {
                List<T> subList = new ArrayList<T>();
                subList.addAll(permutations);
                subList.add(i, head);
                subLists.add(subList);
            }
            output.addAll(subLists);
        }
        return output;
    }
}
Выход
P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]]
P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]]
P(3,1) : Count (3) :- [[3], [1], [2]]
P(3,0) : Count (1) :- [[]]
Моя проблема в том, что я увеличиваю числа в списке ввода. Время работы увеличивается и после 11 цифр в списке ввода программа практически умирает. Занимает около 2 ГБ памяти для запуска.
Я запускаю это на машине с 8 Гб оперативной памяти и процессором i5, поэтому скорость и пространство не являются проблемой.
Буду признателен, если кто-нибудь поможет мне написать более эффективный код.
                                    
                                
                            

Answer 1

Если вы хотите, чтобы все перестановки состояли из 15 или более элементов, запишите их на диск или в БД или что-то еще, так как они не помещаются в памяти. Редактировать: алгоритм Штайнхауса – Джонсона – Троттера. Это, вероятно, то, что вы ищете.

Answer 2

Если вы его не храните - если вы просто перебираете его - тогда подумайте об использовании алгоритма Heap (№ 3 на http://www.cut-the-knot.org/do_you_know/AllPerm.shtml) - или, просто чтобы сделать вашу жизнь проще, используйте Guava's Collections2.permutations, который на самом деле не создает весь список перестановок - он просматривает их на лету. (Раскрытие: я помогаю гуаве.)

Answer 3

Java-библиотека Google (Guava) имеет метод для этого: Collections2 # permutations (Collection)

Answer 4

Вы понимаете, что генерируете очень большие списки, и время выполнения увеличивается с увеличением длины списка. Вы определили, как долго должны быть списки, которые доставляют вам неприятности?

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