遍歷Int集的算法

我不確定這是否是提出這樣一個問題的正確位置。我會給它一個鏡頭。遍歷Int集的算法

問題：

假設val threshold: Int和val size: Int。

我正在尋找一種有效的算法來遍歷所有可能的x: Set[Int]，其中x.sum < threshold和x.size == n。應該考慮只有大於0的Ints。這當然是有限數量的可能性。

我已經試圖開發一個，但即使對於較小的投入，它也需要永久。

在此先感謝。

來源

2013-12-21 Kigyo

您可以提供的示例代碼？ –

所以你有一個Traversable [Set [Int]]？ –

最後更像是一個Set [Set [Int]]。 – Kigyo

您可以很容易地遞歸生成它們。以下是Python中的一些代碼，它可以直接轉換爲Scala。

def sets(n, threshold, atleast=1): 
    if threshold <= n * (n + atleast * 2 - 1) // 2: return 
    if n == 0: 
     yield [] 
     return 
    for i in xrange(atleast, threshold): 
     for s in sets(n - 1, threshold - i, i + 1): 
      yield [i] + s 

print list(sets(4, 15))

來源

2013-12-21 13:30:42

看起來很有希望，我會盡快試一試。 – Kigyo

如果閾值<= n *（n + atleast * 2 - 1）'應該返回什麼？我不太明白，因爲我必須產生一些Set [Set [Int]]。 – Kigyo

@Kigyo該條件捕捉的想法是，如果閾值太低，或者太大，那麼就有滿足條件的整數個集合。（表達式是sum（i =至少at + n + 1）i <閾值）。所以它只是返回而不產生任何集合。 –

我只是張貼我的執行提到的算法在斯卡拉如果有人感興趣：

def generatePossibilities(n: Int, threshold: Int) = { 
    def sets(n: Int, threshold: Int, atleast: Int = 1) : Set[Set[Int]] = { 
     if(threshold <= n * (n + atleast * 2 - 1)/2) { 
     Set.empty[Set[Int]] 
     } else if(n == 0) { 
     Set(Set.empty[Int]) 
     } else { 
     (for(i <- atleast until threshold; 
      s <- sets(n - 1, threshold - i, i + 1)) yield s + i)(collection.breakOut) 
     } 
    } 
    sets(n, threshold) 
}

來源

2013-12-22 01:59:05 Kigyo

'n = 0，threshold = 0'的情況是錯誤的。你從我的代碼中刪除了一個條件，它既捕獲了這個邊界情況（這可能並不重要），也消除了很多不會產生結果的遞歸調用。例如，嘗試（n = 100，閾值= 5051）有和沒有額外的子句。 –

不知道Scala，我懷疑缺少的代碼是'if（threshold <= n *（n + atleast * 2 - 1）/ 2）{Set.empty [Set [int]]}' –

Ok thx。現在我明白你的意思了。我認爲這只是對最初的'n'和'treshold'的一般性檢查。它也沒有它。編輯我的答案。 – Kigyo

遍歷Int集的算法

回答

相關問題