Быстрая перестановка-> число-> алгоритмы отображения перестановки

Чтобы описать перестановку 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} ( последовательность будет {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}, мы получим обратная перестановка, представленная в общем виде. ( {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²). Если вам нужно применить перестановку несколько раз, сначала преобразуйте ее в общее представление.