分區一套成恰好有k塊

Question

我需要一種算法來生成一組的所有分區小號到正是ķ < | S |塊。

注意：我已經找到了生成所有可能分區的算法;我只需要k分區算法。

有什麼想法？

Answer 1

在評論中，我建議在深度k-1停止「通常的遞歸算法」，考慮到2級遞歸方案，其中每個外部遞歸步驟都是停止構建當前部件並開始構建下一個部件部分，每個內部遞歸步驟是決定將一些元素放入當前部分。這是一個相當不錯的方案，因爲它意味着在遞歸樹的底部生成單獨的k分區，因此如果需要，您可以立即在它們上操作它們，而不必將它們全部存儲到大數組中以便以後處理（當然如果你願意，你仍然可以這樣做）。這裏唯一的技巧就是確保你不會產生同樣的分區 - 特別是通過生成兩個包含相同部分的分區，但這些分區的順序不同。這可以通過強制對零件進行排序來避免。最簡單的方法是，無論何時開始構建新零件時，始終添加第一個（即最左邊的）可用元素 - 這可以確保分區中的零件將按其元素的最小位置排序。

但是，如果您不介意在存儲器中實例化k分區的完整列表，還有另一種我認爲更簡單的方法。下面應該足以幫你把一個簡單的遞歸算法一起：

考慮一些要素s S中S的每k分區是正好兩個類別之一：

1. 出現S在與其他元素相同的部分。在這種情況下，從該部分刪除s給出S \ {s}的k分區。
2. 單獨出現在零件中。在這種情況下，刪除整個部分給出了一個（k-1） - S \ {s}的分區。

在情況（1）中的所有分區可以通過將s添加到S \ {s}的k分區中的一個部分來形成，並且情況（2）中的所有分區可以通過將單獨的部分只包含s到s（s）的（k-1）分區。相信這會產生一次S的所有K分區。

在遞歸過程中，您需要考慮的唯一邊界情況是| S | == k - 在這種情況下，您需要返回包含k個單例集的單個分區。