Идея алгоритма для генерации перестановок

Введение

Здравствуйте! Я хочу рассказать Вам об идее алгоритма для генерации перестановок. Отмечу сразу, чтобы не показаться человеком открывающим Америку, я «гуглил» алгоритмы перестановок и их реализация отличалась. Если такой алгоритм уже существует, то пусть эта статья будет туториалом.

Задача алгоритма для генерации перестановки

Этот абзац можно пропустить, если вы знаете, что делают алгоритмы генерации перестановок

Давайте я введу Вас в курс дела. Смотрите, допустим у нас есть строка:

"ABC"

И нам надо получить все возможные перестановки этой строки, то есть:

"ABC"
"ACB"
"BAC"
"BCA"
"CBA"
"CAB"


Собственно, этим и занимаются алгоритмы для генерации перестановок. Поехали дальше.

Суть

Представьте вот такую машину:



Я думаю, вы по данной визуализации поняли саму идею. Что, собственно, тут происходит?

У нас есть сама строка, которая будет использоваться для генерации перестановок. Над ней строится такая «пирамида». Это пирамида из выключателей, которые могут быть либо включены, либо выключены, то есть два состояния.

Далее, когда мы включаем выключатель, то меняем две буквы на которые смотрит этот выключатель. А так как у нас два состояния у выключателя, то какие выключатели включать или выключать мы можем закодировать одним числом. В общем, вот и вся идея.

Реализация

Теперь, у нас есть некая концепция, которую надо перенести из мира мыслей, в мир математики. Другими словами, описать математически.

Путём долгих размышлений, мне дошло, что сначала надо понять, как вычислить количество этих выключателей для строки. Было ясно, что это количество напрямую зависит от длины строки.

Сначала надо вычислить высоту пирамиды. Она считается вот так:

let height = str.length - 1;

Или другими словами, это длина строки минус 1. Потому что, пирамида строится над строкой, на один этаж выше, другими словами. А количество выключателей уменьшается, каждый раз когда мы поднимаемся вверх на этаж.

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



Сразу стало понятно, что нужно делать. Не буду комментировать, а сразу напишу формулу:

let switchQuantity = str.length * height / 2;

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

Дальше, чисто экспериментально «на бумажке» удалось вычислить левый и правый индекс у выключателя, которые надо менять и в итоге получился какой-то результат.

Код

/**
 * Алгоритм генерации перестановок
 */
function gent(items, index)
{
	const length = items.length;
  
  const height = length - 1;
  const max    = length * height / 2;

  // Цикл перебирает все "выключатели" и меняет местами буквы, если бит в соответствующей позиции == 1
  // i - это просто счётчик от 0 до количества выключателей минус один
  // j - этаж на котором мы находимся в данный момент
  // k - ряд на котором мы находимся в данный момент
  for (let i=0, j=0, k=1; i < max; ++i,++k) {
  	
    // Здесь мы вычисляем, какие индексы массива мы будем менять местами
    let left = k - 1;
    let right = k + j;
    
    // Если "выключатель" включён, то меняем местами
    if ( index & (0x01 << i) ) {
    	const tmp = items[left];
      items[left] = items[right];
      items[right] = tmp;
    }
    
    // Увеличиваем высоту, если мы прошли ряд
    if (k % (height - j) === 0) {
    	k -= (height - j);
    	++j;
    }
  }
  
  return items;
}

Вот ссылка на JSFiddle: ссылка на реализацию алгоритма.

Преимущества

Как мы видим, алгоритм очень прост, всего лишь один цикл, да пару условий. Никаких рекурсий. Я сначала протестировал на строке «abc» и обрадовался — «Это работает!». Но, протестировав на строке «abcd», появилась проблема.

Проблема

А проблема такая. Когда строка длиннее 3-х букв, одни и те же перестановки начинают повторятся.

Смотрите, вот результат работы алгоритма на строке «abcd»:

0: abcd - 0000000000
1: bacd - 0000000001
2: acbd - 0000000010
3: bcad - 0000000011
4: abdc - 0000000100
5: badc - 0000000101
6: acdb - 0000000110
7: bcda - 0000000111
8: cbad - 0000001000
9: cabd - 0000001001
10: bcad - 0000001010
11: acbd - 0000001011
12: dbac - 0000001100
13: dabc - 0000001101
14: dcab - 0000001110
15: dcba - 0000001111
16: adcb - 0000010000
17: bdca - 0000010001
18: adbc - 0000010010
19: bdac - 0000010011
20: acdb - 0000010100
21: bcda - 0000010101
22: abdc - 0000010110
23: badc - 0000010111


К примеру, вторая и одиннадцатая перестановки одинаковые, хотя такого быть не должно. Но, если мы переберём все индексы от 0 до $\$inline\$2^x-1\$inline\$$ (где x — это количество наших выключателей), которые передаём в функцию gent(items, index), то мы получим с Вами все перестановки. Даже не знаю, как доказать это математически, но я убедился в этом экспериментально.

Пробовал отсекать повторяющиеся перестановки и смотреть, какие индексы у «уникальных» перестановок. Но, спустя пол года, так и не понял как уникальные индексы зависят от длины строки.

Заключение

Мне кажется, что всё таки есть зависимость между длиной строки и уникальными индексами. Может быть она прямая, или через высоту, количество «выключателей» и т.д.

Если бы можно было понять эту зависимость, вывести формулу. И перед тем как выполнять цикл, пересчитать index учитывая эту формулу, то в итоге, можно было бы передавать индекс от нуля до факториала от длины строки — 1 и получать уникальные перестановки. Это был бы полноценный рабочий алгоритм.

Благодарю, за внимание.