重複約束的隨機包

Question

我正在尋找一種算法來隨機化一組長度爲n的項目，其中可能有多個項目（1到m）。另外一個限制是相同的項目可能不會出現在前一項的k項目中。

你可能會認爲n遠低於100，總是有一個解決方案，即m以及k都很小。如果有幫助，您還可以將輸入更改爲<項目列表，頻率>對。

爲了給出一點上下文，假設我在遊戲中生成任務並且有一組目標可供選擇。有些目標可能會出現多次（例如「殺死老闆」），但不應該彼此接近，所以只需簡單地洗牌即可。

我可以隨機播放列表，然後在跟蹤項目間隔的同時迭代它，如果它沒有通過測試，則從新的隨機播放開始，但是我正在尋找一個更加優雅的解決方案，該解決方案也應該是緊湊的，實用的很容易用例如C，C++或JavaScript。換句話說，它不應該依賴於我可能不瞭解的特殊語言功能或標準庫函數，或者可能難以實現。但是，您可能會認爲可以使用最常用的列表操作，例如排序和混排。

Answer 1

如果你想在一組有效結果上使用統一概率，我的預感是你所提出的拒絕方案（如果安排不好，隨機洗牌然後重新啓動）將是最容易正確編碼，理解，閱讀，並保持以及可能相當接近最快，假設數字是這樣的，大多數排列是有效的。

這是另一種簡單的方法，但是，它基於貪婪地選擇有效值並希望自己不要自責。如果存在許多無效排列（高m和k），則不能保證找到解決方案。

shuffled = list of length n 
not_inserted = {0, 1, ..., n-1} 
for each item i, frequency m_i, nearness constraint k_i: 
    valid = not_inserted 
    do m_i times: 
     choose an index j from valid 
     shuffled[j] = i 
     not_inserted.remove(j) 
     valid.remove(j-k_i, j-k_i+1, ..., j, ..., j+k_i) 

如果valid是有史以來空的，你已經建立了部分解決方案是壞的，你可能會重新啓動。我猜如果你按照遞減的順序進行循環，那麼失敗的可能性就會降低。

我不確定這種方法與排序/拒絕方法相比有多少次失敗（對於某些數字實現和運行它會很有趣......）。我猜想在k中等偏高的情況下可能會更快，但通常會更慢，因爲n << 100的洗牌速度非常快。