Calculating permutations in F#

Question

Inspired by this question and answer, how do I create a generic permutations algorithm in F#? Google doesn't give any useful answers to this.

EDIT: I provide my best answer below, but I suspect that Tomas's is better (certainly shorter!)

Answer 1

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;;