Генерация перестановок
При самом заурядном программировании часто возникает задача генерации всех возможных перестановок некоторого заданного множества - и хотя задача написания этого перебора тривиальна, желательно не изобретать велосипед а пользоваться стандартным алгоритмом.
Во-первых, заметим, что перестановки называются "Permutations". И можно многое найти по поисковым запросам Шаблон:SearchGoogle
очень хорошее описание алгоритма :
При написании программ на C++, разумно использовать STL:
При написании на высокоуровневом языке (типа PL/SQL) разумно попробовать переписать из следующего фрагмента на Python:
<code-python>
- !/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.Список авторов доступен на этом ресурсе в статье под тем же названием.