Calculating permutations in F#

by

you can also write something like this:

let rec permutations list taken = 
  seq { if Set.count taken = List.length list then yield [] else
        for l in list do
          if not (Set.contains l taken) then 
            for perm in permutations list (Set.add l taken)  do
              yield l::perm }

The ‘list’ argument contains all the numbers that you want to permute and ‘taken’ is a set that contains numbers already used. The function returns empty list when all numbers all taken.
Otherwise, it iterates over all numbers that are still available, gets all possible permutations of the remaining numbers (recursively using ‘permutations’) and appends the current number to each of them before returning (l::perm).

To run this, you’ll give it an empty set, because no numbers are used at the beginning:

permutations [1;2;3] Set.empty;;

More Related Contents:

  1. Algorithm to generate all possible permutations of a list?
  2. Fast permutation -> number -> permutation mapping algorithms
  3. Generate all binary strings of length n with k bits set
  4. Shuffle list, ensuring that no item remains in same position
  5. Algorithm for finding numerical permutation given lexicographic index
  6. Find the index of a given permutation in the sorted list of the permutations of a given string
  7. Algorithm to list unique permutations of string with duplicate letters
  8. The sieve of Eratosthenes in F#
  9. Permute all unique enumerations of a vector in R
  10. Algorithm for permutations of operators and operands
  11. Check if array B is a permutation of A
  12. Algorithm to list all unique permutations of numbers contain duplicates
  13. What is tail recursion?
  14. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  15. Getting the closest string match
  16. Efficient list intersection algorithm
  17. 3D Least Squares Plane
  18. Is there ever a good reason to use Insertion Sort?
  19. Shortest distance between points algorithm
  20. How to generate a random permutation in Java?
  21. Amortized complexity in layman’s terms?
  22. Sorting a sequence by swapping adjacent elements using minimum swaps
  23. Retrieving the top 100 numbers from one hundred million of numbers [duplicate]
  24. What is password hashing? [closed]
  25. Can an array be grouped more efficiently than sorted?
  26. Which is faster, Hash lookup or Binary search?
  27. Finding groups of similar strings in a large set of strings
  28. Tournament bracket placement algorithm
  29. Why is bubble sort O(n^2)?
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment