При самом заурядном программировании часто возникает задача генерации всех возможных перестановок некоторого заданного множества - и хотя задача написания этого перебора тривиальна, желательно не изобретать велосипед а пользоваться стандартным алгоритмом.
Во-первых, заметим, что перестановки называются "Permutations". И можно многое найти по поисковым запросам http://www.google.ru/search?hl=ru&q=Permutations
очень хорошее описание алгоритма :
При написании программ на C++, разумно использовать STL:
На 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;
},{})
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
