Математический метод получения целочисленного массива (перестановка)

Question

Мне нужна математическая функция, которая производит массивы, содержащие все варианты некоторых целых чисел, так называемые перестановки, например:

private static final int[][] a = {{1}};
private static final int[][] b = {{1,2},{2,1}};
private static final int[][] c = {{1,2,3},{3,2,1},{2,1,3},{3,1,2},{1,3,2},{2,3,1}};
private static final int[][] d = {{1,2,3,4},{1,2,4,3},...};

Должна быть возможность создавать массивы до ста {{1,2,3,....100},{...}} или более, если это возможно.

Знаете ли вы какие-либо формулы или алгоритмы, которые могут создавать такие массивы?

Answer 1

http://en.wikipedia.org/wiki/Permutation

Вы можете следовать приведенному там алгоритму для массива, содержащего {1..k}, (копируя каждую перестановку в новый массив по мере продвижения), и делать то же самое с {1..k+1}, и так далее.

Однако может быть более эффективный метод, поскольку возможности для {1..k} будут результатами для {1..k-1} с k, вставленным в каждую возможную позицию.

Рассмотрим, что вы планируете делать с ними, однако. Если вам нужны только некоторые перестановки, вам не нужно хранить их все в памяти, поэтому вы можете изменить свою функцию так, чтобы она возвращала только n-ю перестановку, или реализовать итератор, который не выполняет никакого копирования массива и затем позвольте вызывающему коду решить, когда копировать. Вы, конечно, не сможете хранить 100! массивы размером 100. Если моя математика верна, для N=12 вы уже говорите о более чем 20 ГБ дискового пространства для хранения всех из них (и это даже не те, которые до N-1).