Permutation Generator Function F #

Question

I need to generate a list of all the different permutations 1..nx 1..n, where the first value is not equal to the second (i.e. generate 3 → [(3,2) :: (3,1) :: (2,3) : :( 2.1) :: (1.3): :( 1.2)]

Exact scenario - you have a pool of objects (maps), and one for each player. If a player is given a card, no other player can receive this card (do not draw yet, if I need to make a lut for 1-52 to match the actual cards)

I came up with the following which seems useless 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 to do this?

Answer 1

You can do this easily using lists:

 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 nested loops “for” an imperative solution can be performed 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 recursion, so the stack overflow at n = 500 on my machine. It is almost trivial to make this function tail recursive.

The time for this was very interesting. This function (tail recursive version) is 50% larger than the original, and the imperative solution took about 3 times more! Yes - the initial functional solution is the fastest, this is the next fastest, and understanding the imperative list was the slowest, at about 1 :: 1,5 :: 4. Tested on a variety of data sets.