Scala перестановками через flatMap из подмножества

Question

У меня есть метод, который делает перестановки:

def permutations[T](lst: List[T]): List[List[T]] = lst match { 
    case Nil => List(Nil) 
    case x :: xs => permutations(xs) flatMap { perm => 
     (0 to xs.length) map { num => 
     (perm take num) ++ List(x) ++ (perm drop num) 
     } 
    } 
    } 

Во-первых, принять рекурсивный вызов с парой - голова, хвост для списка («а», «б», «в "): c - Nil b - c a - bc

и переставить до и после деталей. В результате у меня есть все перестановки с трех позже. Мой вопрос следующий: почему рекурсивный вызов не возвращает промежуточный оператор типа «bc», «cb», «c» и возвращает допустимый набор из трех позже.

Answer 1

Ну, в каждой итерации вы обязательно возвращать только списки с теми же размерами, что и входной список, потому что вы возвращаетесь перестановки формы (perm take num) ++ List(x) ++ (perm drop num), которая всегда будет содержать все элементы в perm плюс x элемента.

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

Чтобы это исправить, вы можете добавить permбезx в результате каждого цикла, но вам придется добавить distinct избавиться от дупликации:

def permutations[T](lst: List[T]): List[List[T]] = lst match { 
    case Nil => List(Nil) 
    case x :: xs => permutations(xs) flatMap { perm => 
    ((0 to xs.length) flatMap { num => 
     List(perm, (perm take num) ++ List(x) ++ (perm drop num)) 
    }).distinct 
    } 
}