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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

Во-первых, заметим, что перестановки называются "Permutations". И можно многое найти по поисковым запросам Шаблон:SearchGoogle

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

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

При написании на высокоуровневом языке (типа PL/SQL) разумно попробовать переписать из следующего фрагмента на Python:

<code-python>

  1. !/usr/bin/env python

__version__ = "1.0"

"""xpermutations.py Generators for calculating a) the permutations of a sequence and b) the combinations and selections of a number of elements from a sequence. Uses Python 2.2 generators.

Similar solutions found also in comp.lang.python

Keywords: generator, combination, permutation, selection

See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962 See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463 See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66465 """

from __future__ import generators

def xcombinations(items, n):

   if n==0: yield []
   else:
       for i in xrange(len(items)):
           for cc in xcombinations(items[:i]+items[i+1:],n-1):
               yield [items[i]]+cc

def xuniqueCombinations(items, n):

   if n==0: yield []
   else:
       for i in xrange(len(items)):
           for cc in xuniqueCombinations(items[i+1:],n-1):
               yield [items[i]]+cc
           

def xselections(items, n):

   if n==0: yield []
   else:
       for i in xrange(len(items)):
           for ss in xselections(items, n-1):
               yield [items[i]]+ss

def xpermutations(items):

   return xcombinations(items, len(items))

if __name__=="__main__":

   print "Permutations of 'love'"
   for p in xpermutations(['l','o','v','e']): print .join(p)
   print
   print "Combinations of 2 letters from 'love'"
   for c in xcombinations(['l','o','v','e'],2): print .join(c)
   print
   print "Unique Combinations of 2 letters from 'love'"
   for uc in xuniqueCombinations(['l','o','v','e'],2): print .join(uc)
   print
   print "Selections of 2 letters from 'love'"
   for s in xselections(['l','o','v','e'],2): print .join(s)
   print
   print map(.join, list(xpermutations('done')))

</code-python>

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

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

   _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;
     },{})

</code-oracle8>
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.