Algorithm to list all unique permutations of numbers contain duplicates

by

The simplest approach is as follows:

  1. Sort the list: O(n lg n)
  2. The sorted list is the first permutation
  3. Repeatedly generate the “next” permutation from the previous one: O(n! * <complexity of finding next permutaion>)

Step 3 can be accomplished by defining the next permutation as the one that would appear directly after the current permutation if the list of permutations was sorted, e.g.:

1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...

Finding the next lexicographic permutation is O(n), and simple description is given on the Wikipedia page for permutation under the heading Generation in lexicographic order.
If you are feeling ambitious, you can generate the next permutation in O(1) using plain changes

More Related Contents:

  1. Generate all binary strings of length n with k bits set
  2. Algorithm to return all combinations of k elements from n
  3. Finding all possible combinations of numbers to reach a given sum
  4. Algorithm to generate all possible permutations of a list?
  5. How to generate all permutations of a string in PHP?
  6. Fast permutation -> number -> permutation mapping algorithms
  7. Shuffle list, ensuring that no item remains in same position
  8. Algorithm for finding numerical permutation given lexicographic index
  9. Find the index of a given permutation in the sorted list of the permutations of a given string
  10. Algorithm to list unique permutations of string with duplicate letters
  11. Compute rank of a combination?
  12. Calculating permutations in F#
  13. Best way of calculating n choose k?
  14. Permute all unique enumerations of a vector in R
  15. Algorithm for permutations of operators and operands
  16. The intersection of all combinations of n sets
  17. How to efficiently calculate a row in pascal’s triangle?
  18. Check if array B is a permutation of A
  19. counting combinations and permutations efficiently
  20. Is there an O(n) integer sorting algorithm?
  21. Why does this simple shuffle algorithm produce biased results?
  22. design a stack such that getMinimum( ) should be O(1)
  23. Array remove duplicate elements
  24. Permutations without recursive function call
  25. Unsupervised clustering with unknown number of clusters
  26. What is the fastest way to find the closest point to a given point?
  27. how to find longest palindromic subsequence?
  28. Big-oh vs big-theta [duplicate]
  29. Creating combinations that have no more one intersecting element
  30. Heap’s algorithm permutation generator

Leave a Comment