StasFomin в 16:56, 13 июня 2011

2011-06-13T16:56:56Z

Новая страница

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

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

очень хорошее описание алгоритма :
* http://rain.ifmo.ru/~mikhalev/samples/disarray/disarray.html

При написании программ на C++, разумно использовать STL:
* http://www.devx.com/tips/Tip/20816

* [http://hydra.marketsite.ru/dimas/doc/books/programming/shen/node7.html#SECTION00220000000000000000 Описание алгоритма и реализация на Pascal]

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

[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}

Генерация перестановок - История изменений

StasFomin в 16:56, 13 июня 2011