打印出子集的最佳遞歸算法

我試圖找到一個很好的遞歸算法來打印出一組子集。例如打印出子集的最佳遞歸算法

大小5：給the set {1,2,3,4,5} and the subsets off length 3 gives this output:

{5,4,3} 
{5,4,2} 
{5,4,1} 
{5,3,2} 
{5,3,1} 
{5,2,1} 
{4,3,2} 
{4,3,1} 
{4,2,1} 
{3,2,1}

我嘗試過很多事情，但它不工作。在互聯網上，所有的例子都是使用集算法，但我想寫我自己的，用於學習的目的。

有人可以幫助我嗎？

此致

來源

2011-12-19 user1007522

你可以認爲這是一個計數的問題。你有一個基數爲5的數字系統，你只需要從一個3位數字的最小值到最大值。 –

不是真的很喜歡計數問題 - 因爲你不能在你的3位數字「 – radai

」中多次使用相同的「數字」，2個數字相同但不同的順序是相同的 – radai

最後，它的工作原理：

public static void Dvz(String s, int x, int y){ 
    int i; 
    if(y > 0) 
     for(i = x; i >= y; i--) 
     Dvz(s+i, i-1, y-1); 
    else 
     System.out.println(s); 

    }

來源

2011-12-19 22:18:23 user1007522

爲了構建一個遞歸算法可以發現來自{1,2,3,4,5}長度3的每個子集或者：

包含元素「1 「和{2,3,4,5}中的2個元素。
不包含{2,3,4,5}中的元素「1」和3個元素。

這兩種情況都可以通過遞歸調用你的函數來實現。

來源

2011-12-19 12:16:03

幾年前，我有一個非常類似的問題。順便我最終實現這樣的：
1.存儲中的每個設置爲成員ID的排序後的數組（NO 2個ID相同）
2.迭代給定大小的子集n，其中所述第一N個元件開始原始集合
3.爲了實現下一個子集，您實現了一種「發條機制」機制 - 將子集的最後（最高ID）標記替換爲其超集中的鄰居（下一個更高的標識）。
4.如果超集中沒有這樣的較高鄰居，則遞增該子集的下一個較低成員，然後將原始最高成員設置爲之後的下一個成員。

步驟3和4是遞歸的。用於遍歷的{1,2,3,4,5}所有三胞胎

例如結果序列：

{1,2,3} - 3 lowest memebers 
{1,2,4} - "increment" 3 to 4 
{1,2,5} - 4 to 5 
{1,3,4} - couldnt "increment" 5, so incremented 2-->3 and picked then next one as 3rd 
{1,3,5} - 4-->5 
{1,4,5} - couldnt increment 5 ... 
{2,3,4} - couldnt increment 5, couldnt increment 4, incremented 1-->2 
{2,3,5}

等

其比標誌的建議更復雜，但不佔用內存和堆棧空間。它也是「可重新啓動的」 - 意味着你可以將任何子集傳遞給算法，它會讓你成爲「下一個」子集。

來源

2011-12-19 12:33:59 radai

謝謝，幫助很多。 – user1007522

打印出子集的最佳遞歸算法

回答

相關問題