排列生成器函數F＃

我需要生成1..nx 1..n所有不同排列的列表，其中第一個值不等於第二個（即生成3 - > [（3,2）:: （3,1）::（2,3）：:(2,1）：:(1,3）：:(1,2）]排列生成器函數F＃

確切的場景是你有一個物體池），每個玩家處理一個，如果一個玩家被交易一張牌，則其他玩家不能被處理該牌（暫時忽略西裝，如果必須，我會爲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

有沒有更好的方法來做到這一點？

來源

2010-09-10 Snark

您可以輕鬆地使用列表理解做到這一點：

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

來源

2010-09-11 00:09:12 sepp2k

根據我的測試，他的實現速度快了13倍。即使我關了很多，也沒有什麼可以打噴嚏。 – ChaosPandion 2010-09-11 00:20:07

謝謝，我知道必須有更聰明的東西，現在去弄清楚列表解析是如何工作的... – Snark 2010-09-11 00:20:51

+1雖然擊敗了我的蹩腳的答案。 :) – ChaosPandion 2010-09-11 00:25:21

的問題是最好被視爲一個矩陣問題，嵌套「的」命令式解決方案的可循環功能來完成。

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)

這不是尾遞歸的，所以在我的機器上得到大約500的堆棧溢出。使這個函數尾遞歸幾乎是微不足道的。

這個時代非常有趣。這個函數（尾遞歸版本）比原來多了50％，並且命令式解決方案再次花費了大約3倍！是的 - 最初的功能解決方案是最快的，這是下一個最快的，並且命令列表理解最慢，約爲1 :: 1.5 :: 4。在各種數據集上進行測試。

來源

2010-09-14 08:51:38

從我所能看到的功能和列表理解的解決方式出發，頗爲激烈。我不明白爲什麼純功能w /尾遞歸優化如此之快，在n = 5000時，它比10倍更好，而在n = 500時，它更接近3倍。我需要看看反射的代碼... – Snark 2010-09-16 20:54:53

謝謝，user442895。我剛剛完成了Project Euler問題1，並帶有一個簡單的尾遞歸函數，並發現網上的F＃解決方案使用列表理解。功能解決方案的時間比列表解析要好大約8倍。 – 2010-09-17 00:05:04

排列生成器函數F＃

回答

相關問題