如何产生一个多重的所有排列？ [英] How to generate all the permutations of a multiset?

问题描述

一个多集是一组中的所有元素可能无法unique.How枚举所有可能的排列的一组元素中？

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?

推荐答案

生成所有可能的排列，然后丢弃重复的人是非常低效的。不同的算法存在直接生成字典顺序或其他种类的订货的多集的排列。高冈的算法是一个很好的例子，但可能亚伦·威廉姆斯是更好

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

<一个href="http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf">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屋！