Алгоритм Нарайаны

Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней перестановку (в лексикографическом порядке). Придуман индийским математиком Пандитом Нарайаной в XIV веке.

Если алгоритм Нарайаны применить в цикле к исходной последовательности из $n$ элементов $a_{1},a_{2},...,a_{n}$, упорядоченных так, что $a_{1} \leq a_{2} \leq ... \leq a_{n}$, то он сгенерирует все перестановки элементов множества $\{a_{1},a_{2},...,a_{n}\}$ в лексикографическом порядке.

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

Алгоритм

• Шаг 1: найти такой наибольший $j$, для которого $a_{j} \leq a_{j+1}$.
• Шаг 2: увеличить $a_{j}$. Для этого надо установить $l=j$. Далее, если $a_{j} \geq a_{l}$, то уменьшать $l$ на $1$ до тех пор, пока не выполнится $a_{j}<a_{l}$. Затем поменять местами $a_{j}$ и $a_{l}$.
• Шаг 3: развернуть последовательность $a_{j+1},...,a_{n}$.

Реализации

Во всех приведенных ниже реализациях a — массив, в котором в прямом порядке записана перестановка, а n — количество элементов в перестановке.

На языке программирования С/С++

int NarayanaNextPerm (int *a, int n)
{
    int i, k, t, tmp;
 
    //Шаг 1
    for (k = n - 2; (k >= 0) && (a[k] >= a[k + 1]); k--);
 
    //Шаг 2
    if (k == -1)
        return 0;
 
    for (t = n - 1; (a[k] >= a[t]) && (t >= k + 1); t--);
 
    tmp = a[k], a[k] = a[t], a[t] = tmp;
 
    //Шаг 3
    for (i = k + 1; i <= (n + k)/2; i++)
    {
        t = n + k - i;
        tmp = a[i], a[i] = a[t], a[t] = tmp;
    }
 
    return i;
}

На языке программирования Паскаль

function NarayanaNextPerm(var a: array of integer; n: integer): integer;
var
  i, k, t, tmp: integer;
begin
  //Шаг 1
  k := n - 2;
  while (k >= 0) and (a[k] >= a[k+1]) do
    k := k - 1;
 
  if k = -1 then begin
    NarayanaNextPerm := 0;
    Exit;
  end;
 
  //Шаг 2
  t := n - 1;
  while (t >= k + 1) and (a[k] >= a[t]) do
    t := t - 1;
  tmp := a[k];
  a[k] := a[t];
  a[t] := tmp;
 
  //Шаг 3
  for i := k + 1 to (n + k) div 2 do begin
    t := n + k - i;
    tmp := a[i];
    a[i] := a[t];
    a[t] := tmp;
  end;
  NarayanaNextPerm := i;
end;

Оценка сложности

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

Наилучшим является случай, когда предпоследний элемент перестановки больше последнего, тогда производится 2 сравнения и 1 обмен. Худшим является случай, когда элементы перестановки отсортированы по убыванию, и, если длина перестановки равна n, то производится n+1 сравнений и n/2+1 обменов.

В целом сложность алгоритма можно оценить как O(n).

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.