Ответ 1
есть ли уловкий способ упаковать порядок перечисления в числовое значение
Да, вы можете представить упорядочение как числовое значение, хотя для его использования вам нужно преобразовать обратно в массив byte/int. А так как есть 64! возможные порядки из 64 значений и 64! больше, чем Long.MAX_VALUE, вам нужно сохранить номер в BigInteger. Я предполагаю, что это будет наиболее экономичный способ хранения заказов, хотя то, что вы получаете в памяти, вы теряете во времени из-за необходимости преобразования числа в массив.
Для алгоритмов преобразования между представлениями числа/массива см. этот вопрос.
Здесь альтернатива вышесказанному, не знаю, насколько он эффективен, как на этом, и вам придется преобразовать код из int в BigInteger, но этого должно быть достаточно, чтобы дать вы идете:
/**
* Returns ith permutation of the n numbers [from, ..., to]
* (Note that n == to - from + 1).
* permutations are numbered from 0 to n!-1, if i is outside this
* range it is treated as i%n!
* @param i
* @param from
* @param n
* @return
*/
public static int[] perm(long i, int from, int to)
{
// method specification numbers permutations from 0 to n!-1.
// If you wanted them numbered from 1 to n!, uncomment this line.
// i -= 1;
int n = to - from + 1;
int[] initArr = new int[n]; // numbers [from, ..., to]
int[] finalArr = new int[n]; // permutation of numbers [from, ..., to]
// populate initial array
for (int k=0; k<n; k++)
initArr[k] = k+from;
// compute return array, element by element
for (int k=0; k<n; k++) {
int index = (int) ((i%factorial(n-k)) / factorial(n-k-1));
// find the index_th element from the initial array, and
// "remove" it by setting its value to -1
int m = convertIndex(initArr, index);
finalArr[k] = initArr[m];
initArr[m] = -1;
}
return finalArr;
}
/**
* Helper method used by perm.
* Find the index of the index_th element of arr, when values equal to -1 are skipped.
* e.g. if arr = [20, 18, -1, 19], then convertIndex(arr, 2) returns 3.
*/
private static int convertIndex(int[] arr, int index)
{
int m=-1;
while (index>=0) {
m++;
if (arr[m] != -1)
index--;
}
return m;
}
В основном вы начинаете с вашего массива init в своем естественном порядке, затем перебираете свой последний массив, каждый раз вычисляя, какой из остальных элементов должен быть размещен дальше. Эта версия "удаляет" элементы из массива init, устанавливая значение -1. Вероятно, было бы более интуитивно понятно использовать List или LinkedList, я только что вставил это из какого-то старого кода, в котором я лежал.
С помощью вышеуказанных методов и с этим как main:
public static void main(String[] args) {
int n = (int) factorial(4);
for ( int i = 0; i < n; i++ ) {
System.out.format( "%d: %s\n", i, Arrays.toString( perm(i, 1, 4 ) ) );
}
}
Вы получаете следующий результат:
0: [1, 2, 3, 4]
1: [1, 2, 4, 3]
2: [1, 3, 2, 4]
3: [1, 3, 4, 2]
4: [1, 4, 2, 3]
5: [1, 4, 3, 2]
6: [2, 1, 3, 4]
7: [2, 1, 4, 3]
8: [2, 3, 1, 4]
9: [2, 3, 4, 1]
10: [2, 4, 1, 3]
11: [2, 4, 3, 1]
12: [3, 1, 2, 4]
13: [3, 1, 4, 2]
14: [3, 2, 1, 4]
15: [3, 2, 4, 1]
16: [3, 4, 1, 2]
17: [3, 4, 2, 1]
18: [4, 1, 2, 3]
19: [4, 1, 3, 2]
20: [4, 2, 1, 3]
21: [4, 2, 3, 1]
22: [4, 3, 1, 2]
23: [4, 3, 2, 1]
Вот исполняемая версия ideone.
Судя по BigInteger.bitLength(), должно быть возможно сохранить порядок 64 элементов не более 37 байт (плюс накладные расходы на использование экземпляра BigInteger). Я не знаю, стоит ли этого, но это делает приятное упражнение!