Генерация перестановок

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

Во-первых, заметим, что перестановки называются "Permutations". И можно многое найти по поисковым запросам http://www.google.ru/search?hl=ru&q=Permutations

очень хорошее описание алгоритма :

• http://rain.ifmo.ru/~mikhalev/samples/disarray/disarray.html

При написании программ на C++, разумно использовать STL:

• http://www.devx.com/tips/Tip/20816

• Описание алгоритма и реализация на Pascal

На PL/SQL это выглядит примерно так (также долно работать, для перестановок с повторениями):

    _public_procedure({get_next_permutation},{
        _param({a_permutation}, {IN OUT NOCOPY pk_cmn.TStringArray},{},{Перестановка - массив 
                                                                        строк индексируемый с 1
                                                                        без пропусков})
        },{Получить следующую перестановку в лексикографическом порядке. 
           Если перестановка на входе последняя - то возвращается пустой массив
          (a_permutation.first IS NULL)  },
      {
      AS
        l_i PLS_INTEGER;
        l_j PLS_INTEGER;
        PROCEDURE swap(l_i PLS_INTEGER, l_j PLS_INTEGER) AS
        l_val VARCHAR2(4000);
        BEGIN
          l_val:=a_permutation(l_i);
          a_permutation(l_i):=a_permutation(l_j);
          a_permutation(l_j):=l_val;  
        END;
      BEGIN
        l_i:=a_permutation.count-1;
        -- поиск l_i
        WHILE (l_i>0)AND(a_permutation(l_i)>=a_permutation(l_i+1)) LOOP l_i:=l_i-1; END LOOP;
        IF l_i>0 THEN
            l_j:=l_i+1;
            --поиск l_j
            WHILE (l_j<a_permutation.COUNT)AND(a_permutation(l_j+1)>a_permutation(l_i)) LOOP            
                 l_j:=l_j+1; 
            END LOOP;
            -- меняем l_i и l_j
            swap(l_i,l_j);
            ---  переставляем  в обратном порядке от l_i до конца
            FOR l_j IN l_i+1 .. TRUNC((a_permutation.COUNT+l_i)/2) LOOP 
              Swap(l_j,a_permutation.count-l_j+l_i+1);
            END LOOP;
        ELSE 
            a_permutation.DELETE;
        END IF;
      END;
      },{})

---

Репликация: База Знаний «Заказных Информ Систем» → «Генерация перестановок»

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».