Сгенерировать все возможные пары

Question

Это проблема с рекурсией, которая меня действительно путала.

Я хочу сгенерировать все пары для диапазона чисел. Они не должны быть все сохранены, только что сгенерированы хотя бы один раз. Например, для 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.

Моя проблема: я не могу понять, как реализовать это как рекурсивную функцию. Я понял, что он должен поддерживать список всех решений (так что можно найти что-то), а также добавлять небольшие решения и комбинировать их. Это слишком сложно для меня, чтобы попытаться представить, так что любая помощь в методе или псевдокоде (как можно более простое) будет с благодарностью оценена.

Answer 1

Вот некоторый псевдокод:

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)

Затем, в конечном возвратноге заявлении, все эти массивы, содержащих спаривания соединяются вместе и представлены в качестве конечной продукции.