Permutation generator function F#

Question

I need to generate a list of all distinct permutations of 1..n x 1..n where teh first value does not equal the second (i.e. generate 3 -> [(3,2):: (3,1):: (2,3) ::(2,1)::(1,3)::(1,2)]

the exact scenario is you have a pool of objects(cards) and one is dealt to each player. If a player is dealt a card, no other player can be dealt that card(ignore suits for the time being, if I have to I will make a lut for 1-52 to map to the actual cards)

I came up with the following which seems messy at best

 let  GenerateTuples (numcards: int) =
    let rec cellmaker (cardsleft: int) (cardval:int) = 
        if cardval = cardsleft  then (if cardval <= 0  then []  else cellmaker cardsleft (cardval-1) ) elif cardval <= 0  then [] else (cardsleft, cardval) :: cellmaker cardsleft (cardval-1)
    let rec generatelists (cardsleft:int) =
        cellmaker cardsleft numcards @ (if cardsleft > 1 then generatelists (cardsleft-1) else [])
    generatelists numcards

is there a better way of doing this?

Answer 1

You can do it easily using list comprehensions:

let GenerateTuples (n:int) =
    [for i in 1..n do for j in 1..n do if i <> j then yield (i,j)]

Answer 2

The problem is best seen as a matrix problem, and the nested "for" loops of the imperative solution can be done functionally.

let Permute n =
let rec Aux (x,y) =
    if (x,y) = (n,n) then
        []
    else
        let nextTuple = if y = n then ((x + 1),1) else (x,(y + 1))
        if x = y then
            Aux nextTuple
        else
            (x,y)::(Aux nextTuple)
Aux (1,1)

This is not tail-recursive, so get's a stack overflow at approx n = 500, on my machine. It is almost trivial to make this function tail recursive.

The times for this were very interesting. This function (tail recursive version) took 50% more than the original, and the imperative solution took approx 3 times as long again! Yes - the original functional solution is the fastest, this is the next fastest, and the imperative list comprehension was the slowest, by approx 1::1.5::4. Tested on a wide variety of datasets.