순열 만들기

Scala에서 순열을 만드는 2가지 방식을 생각해 볼 수 있겠습니다. 물론 더 여러가지가 있을 수 있겠지만...

1. 한번에 숫자 하나씩 처리하기

인자로 받은 리스트의 항목을 하나씩 가지고 결과물을 만들어 나가는 방법입니다. 매번 리스트 항목에서 하나를 선택해서 이미 만들어진 리스트의 앞, 중간, 뒤에 그 항목을 끼워넣습니다.

List(1, 2, 3), List()
-> List(2, 3), List(List(1))
-> List(3), List(List(2, 1), List(1, 2))
-> List(), List(List(3, 2, 1), List(2, 3, 1), List(2, 1, 3), List(3, 1, 2), List(1, 3, 2), List(1, 2, 3))

def permutation[A](xs:List[A]):List[List[A]] = {
  def mutate(x:A, ys:List[A]):List[List[A]] = {  // ys의 앞, 중간, 뒤에 x를 끼워넣은 리스트를 반환
    def helper(zs:List[A], prev:List[A], acc:List[List[A]]):List[List[A]] = zs match {
      case Nil => (ys :+ x)::acc
      case z::zs1 => helper(zs1, prev :+ z, (prev ++ (x::zs))::acc)
    }
    helper(ys, List(), List())
  }                                      
  def helper(ys:List[A], acc:List[List[A]]):List[List[A]] = ys match {
    case Nil => acc
    case y::ys1 => helper(ys1, acc.flatMap(mutate(y, _)))
  }
  helper(xs, List(Nil))
}                                     

2. 재귀호출

리스트의 각 항목을 뽑아 항목과 나머지를 재귀적으로 호출해서 남은 항목이 없으면 만들어진 리스트를 반환합니다. 실제 코드는 간단하지만 이 코드가 만들어지기까지 며칠을 고민해야 했습니다. (바보인증이구먼) 간단하기도 하고 아마 속도도 더 빠르지 않을까 싶은데요. 항목마다 최후에 만들어질 위치를 미리 알 수 있으므로 필요한 경우 재귀호출을 하지 않고 빠져나갈 수도 있겠습니다.

List(1, 2, 3), List()
-> List(1), List(2, 3) | List(2, List(1, 3) | List(3, List(1, 2))
-> List(1,2), List(3) | List(1, 3), List(2) | List(2, 1), List(3) | List(2, 3), List(1) | List(3, 1), List(2) | List(3, 2), List(1)
-> List(1, 2, 3), List() | List(1, 3, 2), List() | List(2, 1, 3), List() | List(2, 3, 1), List() | List(3, 1, 2), List() | List(3, 2, 1), List()

def permutation2[A](xs:List[A]):List[List[A]] = {
  def helper(made:List[A], rest:List[A]):List[List[A]] = rest match {
    case Nil => List(made)
    case _ => rest.flatMap(r => helper(made :+ r, rest.filter(_ != r)))
  }
  helper(List(), xs)
}