Объединение функций списка

Question

Ниже функция вычисляет возможные комбинации элементов списка.

элементы списка, которые так же не возвращаются, а также только уникальные элементы возвращаются:

def combinations[T](l: List[T]): List[(T,T)] = l match { 
    case Nil => Nil 
    case h::Nil => Nil 
    case h::t => t.map(x=>(h,x)) ++ combinations(t) 
} 

List (1,2,3) возвращает список ((1,2), (1,3) , (2,3))

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

Answer 1

Это на самом деле очень интуитивно, когда вы думаете о том, как вы вручную создадите все комбинации. Например, возьмите List(1, 2, 3, 4). Чтобы методично создать все комбинации, я возьму первый элемент в списке 1, а затем объединить его со всеми остальными элементами.

(1, 2), (1, 3), (1, 4) 

Это все возможные комбинации, которые содержат 1. Теперь давайте найдем все комбинации, содержащие 2, но нам не нужно включать те, которые имеют 1, потому что у нас их уже есть. Это означает, что мы возьмем комбинации с остальными элементами списка.

(2, 3), (3, 4) 

А потом с 3:

(3, 4) 

Вы видите картину? Мы берем первый элемент списка, затем соединяем его со всеми остальными элементами списка (хвост). Вот эта часть кода:

case h :: t => t.map(x => (h, x)) 
// 1 :: List(2, 3, 4) => List((1, 2), (1, 3), (1, 4)) 

Затем мы переходим к следующему элементу списка и делаем то же самое. Это рекурсивный шаг: ++ combinations(t), и суммируйте результаты с помощью ++.

Если бы мы начали с 1, то под чехлов первый рекурсивный вызов combinations(List(2, 3, 4)), и мы повторяем логику:

case h :: t => t.map(x => (h, x)) 
// 2 :: List(3, 4) => List((2, 3), (3, 4)) 

И наконец:

case h :: t => t.map(x => (h, x)) 
// 3 :: List(4) => List((3, 4)) 

Так мы и с List((1, 2), (1, 3), (1, 4)) ++ List((2, 3), (3, 4)) ++ List((3, 4))

И, конечно, в других случаях, когда есть нуль или один элемент, невозможно создать больше комбинаций:

case Nil => Nil 
case h :: Nil => Nil 

Как @ 0__ указано, h :: Nil действительно может быть обработан h :: t, потому что мы будем иметь это:

case h :: t => t.map(x => (h, x)) ++ combinations(t) 
//  ^Nil ^Nil maps to Nil  ^Will hit the first case on the next call, which is also Nil 

Answer 2

При определении функционального/рекурсивное решение с List, самый простой подход должен охватывать основные случаи, которые происходят. Затем вы определяете частичные решения и добавляете их вместе.

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

Обратите внимание, что технически средний случай не имеет значения. Достаточно

def combinations[A](xs: List[A]): List[(A, A)] = xs match { 
    case Nil => Nil 
    case h :: t => t.map(h -> _) ++ combinations(t) 
}