排列生成器函数 F#

Question

我需要生成 1..nx 1..n 的所有不同排列的列表，其中第一个值不等于第二个值 （即生成 3 -> [(3,2):: (3,1):: (2,3) ::(2,1)::(1,3)::(1,2)

]确切的情况是，你有一堆物体（牌），每个玩家都会发一张牌，如果给一个玩家发一张牌，那么其他玩家就不能发这张牌（暂时忽略花色，如果有必要的话我会的。为 1-52 制作一个 lut 来映射到实际的卡片）

我想出了以下内容，充其量看起来很混乱，

 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

有更好的方法吗？

Answer 1

该问题最好被视为一个矩阵问题，并且命令式解决方案的嵌套“for”循环可以通过函数来​​完成。

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)

这不是尾递归，所以在我的机器上大约 n = 500 时出现堆栈溢出。使这个函数尾部递归几乎是微不足道的。

这段时间非常有趣。这个函数（尾递归版本）比原来的函数多花费了 50%，而命令式解决方案又花费了大约 3 倍的时间！是的 - 原始函数式解决方案是最快的，这是第二快的，命令式列表理解是最慢的，大约为 1::1.5::4。在各种数据集上进行了测试。

Answer 2

您可以使用列表理解轻松完成此操作：

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