ГЕНЕРАЦИЯ ПЕРЕСТАНОВОК С ЧАСТИЧНО ОПРЕДЕЛЕННЫМ ПОРЯДКОМ СЛЕДОВАНИЯ ЭЛЕМЕНТОВ
Ключові слова:
КОМБІНАТОРИКА, ПЕРЕСТАНОВКА, ГЕНЕРАЦІЯ, ПОРЯДОК СЛІДУВАННЯ ЕЛЕМЕНТІВ, МНОЖИНА СПУСКУАнотація
В статті розглядається задача генерації перестановок, для яких порядок слідування (відношення «більше» або «менше») утворюючих елементів у кожній перестановці задано частково, тобто тільки для деяких з них. Запропоновано алгоритм, що дозволяє згенерувати всі перестановки, що задовольняють частково заданому порядку слідування. Описаний алгоритм є універсальним і може бути застосований для генерації інших комбінаторних конфігурацій.
Посилання
Ruskey F. combinatorial generation [Text] / F. Ruskey. – Dept. of computer Science Univ. of victoria, canada, 2003.– 289 p.
Kreher D. combinatorial Algorithms: generation enumeration and Search [Text] / D. Kreher, D. Stinson. cRc Press, 1999. – 329 p.
Knuth D. The Art of computer Programming [Text] / D.Knuth. – volume
, Fascicle 2: generating All Tuples and Permutations. – Addison-wesley, 2005.
Гребенник, И.В. Описание и генерация перестановок, содержащих циклы [текст] / И.В. Гребенник // Кибернетика и системный анализ. – 2010. – № 6. – С. 97-105.
Poneti M. generating restricted classes of involutions, bell and Stirling permutations [Text] / M. Poneti, v. vajnovszki. – european Journal of combinatorics.–2010. – №31. – pp. 553–564.
van Baronaigien R. generating permutations with given ups and downs [Text] / R. van baronaigien, F. Ruskey // Discrete Applied Mathematics. – № 36(1), 1992. – pp. 57–65.
Stanley R. enumerative combinatorics [Text] / R.P. Stanley. –wadsworth, Inc. california. – vol. 1 – 1986.
Stanley R. P. A survey of alternating permutations // contemp. Math. – 2010. – т. 531. – С. 165-196.
Bauslaugh B., Ruskey F. generating alternating permutations lexicographically // bIT Numerical Mathematics. – 1990. – т. 30. – №. 1. – С. 17-26.
Bergeron F., labelle g., leroux P. combinatorial species and tree-like structures. – cambridge University Press, 1998. – т. 67.
Grebennik I. V., lytvynenko O. S. generating combinatorial sets with given properties // cybernetics and Systems Analysis. – 2012. – С. 1-9.
