生成所有可能的配對

這是一個遞歸問題，這真的讓我很困惑。生成所有可能的配對

我想爲一系列數字生成所有配對。它們不必全部存儲，只需至少生成一次。例如，對於0 1 2 3 4 5這將是

(0 1) (2 3) (4 5) 
(0 1) (2 4) (3 5) 
(0 1) (2 5) (3 4) 
(0 1) (3 4) (2 5) 
(0 1) (3 5) (2 4) 
(0 2) (1 3) (4 5) 
(0 2) (1 4) (3 5) 
etc.

正如你所看到的，我的方法是使用第一個可用的使用數量，以產生第一對（在開始的時候，這是0，用0-5），迭代通過所有剩餘的數字來創建第一對。然後，對於每一對我遞歸剩餘的數字。所以如果我的貨幣對是0 1我會用2 3 4 5重複這個過程。

我的問題是我無法弄清楚如何實現這個作爲遞歸函數。我發現它必須保留所有解決方案的運行列表（所以可以找到一些東西），同時還必須附加較小的解決方案並將它們結合起來。這對我來說太複雜了，因此我們將不勝感激。因此，任何關於方法或僞代碼的幫助（儘可能簡單）都是非常有用的。

來源

2014-10-27 qwr

我不確定遞歸函數是否是生成對的正確工具。如果你不僅需要生成對，而且還要生成'（0 2 4 5）'和'（1 3 4）'等等，你可以使用一個遞歸函數來接受兩個參數：當前排列和剩餘數字列表。 – Stijn 2014-10-27 08:46:47

您的規則不明確。首先，顯然'（0 1）（2 3）（4 5）'是有效的，但是'（0 1）（2 3）（5 4）'是無效的;正確？另外，從（（0 1）（4 5）（2 3）''是唯一的'（0 1）（2 3）（4 5）';正確？什麼確定了有效的配對？ – user2338816 2014-10-29 05:36:22

@ user2338816前兩個實際上是一樣的。我犯了一個錯誤，你提到的最後兩個也是一樣的。 – qwr 2014-10-29 22:16:03

下面是一些僞代碼：

function allPairingsInSet(Array set) { 

    // assume all elements in set are unique and set.length() >= 2 
    if(set.length() == 2) { 
     return set; 
    } 

    // get all pairings containing first element 
    Array pairingsWithFirstElement; 
    for(int i = 1; i < set.length(); i++){ 
     pairingsWithFirstElement[i] = (set[0], set[i]); 
    } 

    // get subsequent pairings excluding the ones with the first element, 
    // which we already have; then concatenate the arrays 
    return pairingsWithFirstElement + allPairingsInSet(set.subArray(1, set.length()-1)); 
}

設置你提供，(0, 1, 2, 3, 4, 5)，這種方法將穿行，找到所有包含集，0的第一個元素配對的例子。

[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]

則它與該亞羣(1, 2, 3, 4, 5)一樣，給人

[(1, 2), (1, 3), (1, 4), (1, 5)]

這繼續一路下跌到基情況下設置爲僅包含兩個元素，它可以產生只有一個可能的配對。在這種情況下，基本情況返回我們

(4, 5)

然後，在最後的return語句，所有含配對這些陣列的結合在一起，並提出作爲最終輸出。

來源

2014-10-29 05:01:35

生成所有可能的配對

回答

相關問題