CODEWITHSUNDEEP
algorithmscala
pacman
pacman

Reputation: 837

Scala permutations via flatMap of subset

I have the method which makes permutations:

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)
      }
    }
  }

Firstly, it take a recursive call with pair - head, tail for List("a","b", "c"): c - Nil b - c a - bc

and permute before and after parts. As result, I have all permutations from three later. My question is next: why recursive call doesn't return the intermediate statement like "bc", "cb", "c" and return valid set from three later.

Upvotes: 1

Views: 238

Answers (1)

Tzach Zohar
Tzach Zohar

Reputation: 37832

Well, in each iteration you necessarily return only lists with the same size as the input list, because you return permutations of the form (perm take num) ++ List(x) ++ (perm drop num), which would always contain all of the elements in perm plus the x element.

Therefore, recursively - if each cycle returns only values of the same size as its input (including the end case of Nil), then the end result must only contain permutations of the same size.

To fix this, you can add the perm without x to each cycle's result, but you'll have to add distinct to get rid of duplications:

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
  }
}

Upvotes: 2

Related Questions