如何生成多重集的所有排列? [英] How to generate all the permutations of a multiset?

问题描述

多集是一个集合，其中所有元素可能不唯一.如何枚举集合元素之间所有可能的排列?

A multi-set is a set in which all the elements may not be unique.How to enumerate all the possible permutations among the set elements?

推荐答案

生成所有可能的排列然后丢弃重复的排列是非常低效的.存在各种算法来直接生成按字典顺序或其他类型排序的多集的排列.Takaoka 的算法是一个很好的例子，但可能 Aaron Williams 的算法更好

Generating all the possible permutations and then discarding the repeated ones is highly inefficient. Various algorithms exist to directly generate the permutations of a multiset in lexicographical order or other kind of ordering. Takaoka's algorithm is a good example, but probably that of Aaron Williams is better

http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf

此外，它已在 R 包multicool"中实现.

moreover, it has been implemented in the R package ''multicool''.

顺便说一句，如果你只想要不同排列的总数，答案是多项式系数:例如，如果您有 n_a 个元素a"、n_b 个元素b"、n_c 个元素c"，不同排列的总数是 (n_a+n_b+n_c)!/(n_a!n_b!n_c!)

Btw, if you just want the total number of distinct permutations, the answer is the Multinomial coefficient: e.g., if you have, say, n_a elements 'a', n_b elements 'b', n_c elements 'c', the total number of distinct permutations is (n_a+n_b+n_c)!/(n_a!n_b!n_c!)

这篇关于如何生成多重集的所有排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！