|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Генерация перестановокМатериал из CustisWikiПри самом заурядном программировании часто возникает задача генерации всех возможных перестановок некоторого заданного множества - и хотя задача написания этого перебора тривиальна, желательно не изобретать велосипед а пользоваться стандартным алгоритмом. Во-первых, заметим, что перестановки называются "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; },{})
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Генерация перестановок» |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |