Scala函數獲取大小爲k的所有排序子集

我給定了一組大小爲L並希望生成大小爲k的每個排序子集。如果你的解決方案是scala，但是我可以自己翻譯，那會很好。Scala函數獲取大小爲k的所有排序子集

運行L = 6和k = 3的示例應該會產生。

1，2，3
1，2，4
1，2，5
1，2，6
1，3，4
1，3，5
1,3 6
1，4，5
1，4，6
1，5，6
2，3，4
2，3，5
2，3，6
2，4，5
2，4，6
2，5，6
3，4，5
3，4，6
3，5，6
4，5，6

我的斯卡拉嘗試是這樣的：

object Util { 
    def main(args : Array[String]) : Unit = { 
    starts(6,3,1) 
    } 

    def starts(L: Int, num: Int, level: Int) : List[List[Int]] = { 
    if(num == 0) { 
     return List() 
    }else{ 
     (level to (L-num+1)).map(o => o :: starts(L,num-1,level+1)) 
    } 
    } 
}

我希望你能幫助我。

來源

2011-11-15 peri4n

我希望你能幫助自己，因爲我不知道你想要什麼，這聽起來像作業 –

這不是作業。我只想爲這個問題學習一個scala方法。 – peri4n

你可以從

def subsets(start: Int, end: Int, count: Int) :Seq[Seq[Int]] = (
    if (count == 0) 
    List(Nil) 
    else 
    for(head <- start to end; tail <- subsets(head + 1, end, count -1)) 
    yield head +: tail 
)

來源

2011-11-15 13:58:25

作品完美。非常感謝你。 – peri4n

開始如果你確實有塊而不是項那麼你需要知道每個塊有多長。你已經顯示的是條目（或者等價於長度爲1的塊）。

首先，請注意，我們必須有L>=k。其次，請注意，如果第一個條目爲i，則剩餘的可能性爲i+f(L-i,k-1)，其中f是生成條目的內容，並且假設+分佈在集合中。最後，我們注意到具有爲每個元素生成序列的函數的flatMap將會將結果解壓縮爲單個序列。

現在，我們擁有一切，我們需要知道：

def choices(N: Int, k: Int): List[List[Int]] = { 
    if (k==1) (1 to N).toList.map(x => List(x)) 
    else if (N < k) Nil 
    else (1 to 1+N-k).toList.flatMap{ i => 
    choices(N-i,k-1).map(xs => i :: xs.map(_ + i)) 
    } 
}

如果你沒有在實際上意味着塊，那麼我們就需要知道塊有多長。該分析是相同的，除了代替跳過只有一個值，我們需要跳過塊大小：

def blockchoices(N: Int, k: Int, size: Int): List[List[Int]] = { 
    if (k==1) (1 to N+1-size).toList.map(x => List(x)) 
    else if (N <= k+size) Nil 
    else (1 to 2+N-k-size).toList.flatMap{ i => 
    choices(N-i+1-size, k-1, size).map(xs => i :: xs.map(_ + i+size-1)) 
    } 
}

（塊的起始條目列出）。

來源

2011-11-15 14:14:21

偉大的增加。我也對這個解決方案感興趣。不幸的是，對變長塊進行泛化會突破我統計模型的複雜性。 – peri4n

所有你需要的是

def subsets(L: Int, k: Int) = 
    1 to L combinations k

結果：按要求

scala> subsets(6, 3) foreach println 
Vector(1, 2, 3) 
Vector(1, 2, 4) 
Vector(1, 2, 5) 
Vector(1, 2, 6) 
Vector(1, 3, 4) 
Vector(1, 3, 5) 
Vector(1, 3, 6) 
Vector(1, 4, 5) 
Vector(1, 4, 6) 
Vector(1, 5, 6) 
Vector(2, 3, 4) 
Vector(2, 3, 5) 
Vector(2, 3, 6) 
Vector(2, 4, 5) 
Vector(2, 4, 6) 
Vector(2, 5, 6) 
Vector(3, 4, 5) 
Vector(3, 4, 6) 
Vector(3, 5, 6) 
Vector(4, 5, 6)

。

來源

2011-11-15 15:50:33

我認爲作爲一名scala程序員，應該知道這個庫。：d – peri4n

Scala函數獲取大小爲k的所有排序子集

回答

相關問題