排列生成器函数 F#

Question

我需要生成一个列表，其中包含1..n x 1..n的所有不同排列，其中第一个值不等于第二个值（例如，生成3 -> [(3,2):: (3,1):: (2,3) ::(2,1)::(1,3)::(1,2)]）。

具体情况是，您有一堆对象（牌），每个玩家都会得到一张牌。如果某个玩家得到了一张牌，则其他玩家将不能得到该牌（暂时忽略花色，如果必要，我将为1-52制作一个映射表以映射实际牌）。

我想出了以下代码，但看起来最好还需改进。

 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

有没有更好的方法来做这件事？

- Snark

Answer 1

您可以轻松使用列表推导来完成:

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

- sepp2k

---

根据我的测试，他的实现大约快了13倍。即使我错了很多，这也是不容小觑的成果。 - ChaosPandion

谢谢，我知道必须有更聪明的方法，现在去弄清楚列表推导式是如何工作的... - Snark

关于时间我们达成了一致。对于小的n，差别不大，但是当n > 200时，函数式解决方案（即OP代码）比其他方法快4到5倍。请看下面我的解决方案。 - Stephen Hosking

Answer 2

问题最好看作是一个矩阵问题，而命令式解决方案中嵌套的“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。 在各种数据集上测试过。

- Stephen Hosking

---

从我所看到的情况来看，函数式和列表推导式的解决方案有很大的差异。我不太明白为什么纯函数式带尾递归优化会如此快，在 n = 5000 时，它比其他方法快了超过10倍，而在 n = 500 时，它只比其他方法快了约3倍。我需要查看反射代码... - Snark

谢谢，user442895。我刚刚用一个简单的尾递归函数完成了欧拉计划问题1，并发现网络上的F#解决方案使用列表推导式。函数式解决方案的时间比列表推导式快了大约8倍。 - Stephen Hosking