Чтобы описать перестановку из n элементов, вы видите, что для позиции, в которой заканчивается первый элемент, у вас есть n возможностей, поэтому вы можете описать это числом от 0 до n-1. Для позиции, в которой заканчивается следующий элемент, у вас есть n-1 оставшихся возможностей, поэтому вы можете описать это числом от 0 до n-2.
И так далее, пока у вас есть n номеров.
В качестве примера для n = 5 рассмотрим перестановку, которая приводит abcde к caebd.
a, первый элемент, заканчивается на второй позиции, поэтому мы присваиваем ему индекс 1 . b заканчивается на четвертой позиции, которая будет индексом 3, но это третья оставшаяся позиция, поэтому мы присваиваем ей 2 . c заканчивается в первой оставшейся позиции, которая всегда равна 0 . d заканчивается в последней оставшейся позиции, которая (из двух оставшихся позиций) равна 1 . e заканчивается в единственной оставшейся позиции с индексом 0 .
Итак, у нас есть последовательность индексов {1, 2, 0, 1, 0} .
Теперь вы знаете, что, например, в двоичном числе «xyz» означает z + 2y + 4x. Для десятичного числа:
это z + 10y + 100x. Каждая цифра умножается на некоторый вес, а результаты суммируются. Очевидная закономерность в весе - это, конечно, вес w = b ^ k, где b - основание числа, а k - индекс цифры. (Я всегда буду считать цифры справа и начиная с индекса 0 для самой правой цифры. Аналогично, когда я говорю о «первой» цифре, я имею в виду самую правую.)
Причина , почему веса для цифр следуют этому шаблону, заключается в том, что наибольшее число, которое может быть представлено цифрами от 0 до k, должно быть ровно на 1 меньше, чем наименьшее число, которое может быть представлено только используя цифру k + 1. В двоичном коде 0111 должен быть на единицу меньше 1000. В десятичном виде 099999 должен быть на единицу меньше 100000.
Кодирование в переменную-основу
Интервал между последующими числами, равный 1, является важным правилом. Понимая это, мы можем представить нашу индексную последовательность с помощью базового числа переменной . База для каждой цифры - это количество различных возможностей для этой цифры. Для десятичной дроби каждая цифра имеет 10 возможностей, для нашей системы самая правая цифра будет иметь 1 возможность, а самая левая будет иметь n возможностей. Но поскольку самая правая цифра (последняя цифра в нашей последовательности) всегда равна 0, мы ее опускаем. Это означает, что у нас остались базы от 2 до n. Как правило, k-ая цифра будет иметь основание b [k] = k + 2. Максимальное допустимое значение для цифры k - это h [k] = b [k] - 1 = k + 1.
Наше правило о весах w [k] цифр требует, чтобы сумма h [i] * w [i], где i переходит от i = 0 к i = k, была равна 1 * w [k + 1]. Заявлено периодически, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Первый вес w [0] всегда должен быть 1. Начиная с этого момента, мы имеем следующие значения:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(Общее соотношение w [k-1] = k! Легко доказывается по индукции.)
Число, которое мы получим от преобразования нашей последовательности, будет тогда суммой s [k] * w [k], с k, работающим от 0 до n-1. Здесь s [k] k-й (самый правый, начиная с 0) элемент последовательности. В качестве примера возьмем наш {1, 2, 0, 1, 0} с удаленным крайним правым элементом, как упомянуто ранее: {1, 2, 0, 1} . Наша сумма составляет 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .
Обратите внимание, что если мы возьмем максимальную позицию для каждого индекса, у нас будет {4, 3, 2, 1, 0}, и это преобразуется в 119. Поскольку веса в нашей числовой кодировке были выбраны таким образом, чтобы мы не не пропускайте любые числа, все числа от 0 до 119 действительны. Их точно 120, то есть n! для n = 5 в нашем примере точно число различных перестановок. Таким образом, вы можете увидеть наши закодированные числа полностью указать все возможные перестановки.
Декодирование с переменной базы
Декодирование аналогично преобразованию в двоичное или десятичное число. Общий алгоритм таков:
int number = 42;
int base = 2;
int[] bits = new int[n];
for (int k = 0; k < bits.Length; k++)
{
bits[k] = number % base;
number = number / base;
}
Для нашего переменного базового числа:
int n = 5;
int number = 37;
int[] sequence = new int[n - 1];
int base = 2;
for (int k = 0; k < sequence.Length; k++)
{
sequence[k] = number % base;
number = number / base;
base++; // b[k+1] = b[k] + 1
}
Это правильно декодирует наши 37 обратно в {1, 2, 0, 1} (sequence будет {1, 0, 2, 1} в этом примере кода, но что угодно ... до тех пор, пока вы правильно проиндексировали). Нам просто нужно добавить 0 в правом конце (помните, что последний элемент всегда имеет только одну возможность для своей новой позиции), чтобы вернуть нашу первоначальную последовательность {1, 2, 0, 1, 0}.
Преобразование списка с использованием последовательности индексов
Вы можете использовать приведенный ниже алгоритм для перестановки списка в соответствии с определенной последовательностью индекса. К сожалению, это алгоритм O (n²).
int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];
for (int i = 0; i < n; i++)
{
int s = sequence[i];
int remainingPosition = 0;
int index;
// Find the s'th position in the permuted list that has not been set yet.
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;
remainingPosition++;
}
}
permuted[index] = list[i];
set[index] = true;
}
Общее представление перестановок
Обычно вы представляете перестановку не так интуитивно, как мы, а просто абсолютной позицией каждого элемента после применения перестановки. Наш пример {1, 2, 0, 1, 0} для abcde до caebd обычно представлен {1, 3, 0, 4, 2}. Каждый индекс от 0 до 4 (или вообще от 0 до n-1) встречается ровно один раз в этом представлении.
Применение перестановки в этой форме легко:
int[] permutation = new int[] { 1, 3, 0, 4, 2 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
for (int i = 0; i < n; i++)
{
permuted[permutation[i]] = list[i];
}
Инвертирование очень похоже:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
Преобразование из нашего представления в общее представление
Обратите внимание, что если мы возьмем наш алгоритм для перестановки списка с использованием нашей индексной последовательности и применим его к перестановке идентификаторов {0, 1, 2, ..., n-1}, мы получим перестановку inverse, представленный в общем виде. ( {2, 0, 4, 1, 3} в нашем примере).
Чтобы получить неинвертированную премутацию, мы применяем алгоритм перестановки, который я только что показал:
int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];
for (int i = 0; i < n; i++)
{
normal[identity[i]] = list[i];
}
Или вы можете просто применить перестановку напрямую, используя алгоритм обратной перестановки:
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
int[] inverted = { 2, 0, 4, 1, 3 };
for (int i = 0; i < n; i++)
{
permuted[i] = list[inverted[i]];
}
Обратите внимание, что все алгоритмы для работы с перестановками в общей форме - это O (n), тогда как применение перестановки в нашей форме - это O (n²). Если вам нужно применить перестановку несколько раз, сначала преобразуйте ее в общее представление.