How to generate all the permutations of a multiset?

by

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

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

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!)

More Related Contents:

  1. Ukkonen’s suffix tree algorithm in plain English
  2. How to generate all permutations of a string in PHP?
  3. Creating all possible k combinations of n items in C++
  4. Algorithm to convert an IEEE 754 double to a string?
  5. Finding the ranking of a word (permutations) with duplicate letters
  6. Algorithm to find articles with similar text
  7. Best data structure for implementing a dictionary?
  8. Compute rank of a combination?
  9. PHP take all combinations
  10. generate all partitions of a set [closed]
  11. Parse usable Street Address, City, State, Zip from a string [closed]
  12. “The argument type ‘String?’ can’t be assigned to the parameter type ‘String'” when using stdin.readLineSync()
  13. Format a Go string without printing?
  14. C++/CLI Converting from System::String^ to std::string
  15. In Bash, how can I check if a string begins with some value?
  16. Bash: Split string into character array
  17. String with array structure to Array [duplicate]
  18. Replacing characters in Ant property
  19. How do I convert a Vec to Vec?
  20. How to convert “Index” to type “Int” in Swift?
  21. Scheduling algorithm for a round-robin tournament?
  22. Print all the permutations of a string in C
  23. Python: find closest string (from a list) to another string
  24. Approximate string matching algorithms
  25. Is there an owned version of String::chars?
  26. How to split a string in Haskell?
  27. Repeat and concatenate a string N times
  28. scala string.split does not work
  29. Algorithm for Calculating Binomial Coefficient
  30. Does C have any tools for doing string addition?

Leave a Comment