class Fish {
 def swim = println("fish: swim")
}

class Duck {
 def quack = println("duck: quaaaack")
 def feathers = println("duck: white feathers")
}

class Person {
 def think = println("person: therefore I am")
 def quack = println("person: speak qua~~ack!")
 def feathers = println("person: wear feather clothing")
}

type DuckLike = { def quack; def feathers } // Structural Typing

def inTheForest( duckLike: DuckLike ) {
  duckLike.quack
  duckLike.feathers
}

/*
scala> inTheForest( new Duck )  
duck: quaaaack
duck: white feathers

scala> inTheForest( new Person )
person: speak qua~~ack!
person: wear feather clothing

scala> inTheForest( new Fish )
<console>:9: error: type mismatch;
 found   : Fish
 required: DuckLike
       inTheForest( new Fish )
                    ^

*/

임의의 알파벳 시퀀스를 입력받아서, 해당 알파벳으로 만들 수 있는 순서의 조합을 모두 구한다. 
그리고 결과는 문자열의 오름차순으로 정렬하여 출력한다. 
(예를 들어, "AB", "BA" 가 있는 경우 "AB"가 "BA"보다 먼저 나와야 한다.)

 ex)  "ABC" -> "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"
      "AAB" -> "AAB", "ABA", "BAA"
      "ABA" -> "AAB", "ABA", "BAA"
      "000" -> "000"

scala> "AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

scala> "ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))

다시 말해 1의 영역은 A를 제외한 나머지 원소들의 순열이고, 2의 영역은 B를 제외한 나머지 원소들의 순열이다. 예를 들어 부모 노드에서 A가 나오면 나머지 문자인 B, B로 구성된 순열은 1가지 뿐이다.  전체 순열은 "A + 영역1"과 "B+영역2"로 나타낼 수 있으므로, 이를 통해 순열 문제는 재귀적인 과정으로 풀 수 있다는 예측이 가능하다.

permutate 메서드의 작성

이제 트리를 코드로 표현해야 한다. 트리의 특정 문자열(예시의 경우 List("A","B","B"))의 순열은 결국 자신의 원소들을 중복 제거한 head와 head를 제외한 나머지 원소들의 순열로 표현된다. 이는 대강 다음과 같은 형태로 표현이 가능하다. 

def permutate(list:List[Char]):List[List[Char]] = {

  val heads:List[Char] = list.distinct       // 원소의 중복을 제거하는 distinct 메서드는 제공됨
  
  // heads loop {

    val tail = list.removeFirst( _ == head)  // 일치하는 조건의 원소를 단 하나만 지움(작성 예정)
    permutate(tail).map( head :: _ )         // 자식의 순열에 head를 결합하면 전체 순열이 됨

  // } loop end

완전하지 않은 코드이지만 핵심은 모두 담고 있다.

먼저 조건식 p와 일치하는 원소를 하나만 제거하는 removeFirst()를 작성하자.

def removeFirst[T](p:(T)=> Boolean):List[T] = {
  val index = list.indexWhere(p)
  val (first, _ :: second) = list.splitAt(index)
  first ::: second
}

내용은 간단하다. 조건식 p와 일치^[각주:3]하는 원소의 위치를 찾아(indexWhere), 해당 위치를 기준으로 두 리스트로 쪼개고(splitAt), 패턴 매칭^[각주:4]을 활용해 조건에 맞는 위치의 원소 하나를 제외한 앞 뒤 List를 합쳤다. 그 결과 찾아낸 원소가 제외된 리스트가 완성된다. 

핵심 메서드인 permutate의 구현은 다음과 같다. 중복 없는 head에 소트를 추가하는 등의 내용이 추가됐고, flatMap 등의 메서드가 머리를 어지럽게 할 수도 있지만  미리 작성해본 permutate 구현과 핵심적인 내용은 같다. 오히려 코드를 참고하지 않고 직접 작성해 보면 이해가 빠를지도 모르겠다.

def permutate(list:List[Char]):List[List[Char]] ={
val heads:List[Char] = list.distinct.sortWith(_ < _)
heads.flatMap( head => {
  val tail = list.removeFirst( _ == head)
  tail match {
	case Nil => List(List(head))
	case _ => permutate(tail).map ( head :: _ )
  }
})
}

마지막으로 List에 permutate 메서드(removeFirst 도 추가하려 한다)를 추가하기 위해 Implicit Type Conversion을 적용해 보자.

Implcit Type Conversion 적용

PermuatbleList 클래스에 순열을 만들기 위해 필요한 기능을 넣고 Implicit Type Conversion을 적용해 List의 기능을 확장할 계획이다. Implicit Type Conversion을 적용하려면 해당하는 implicit 메서드가 현재 scope에서 사용가능해야 한다.

object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }
}

implicit 메서드가 위와 같이 선언되어 있을 경우, Implicit Type Conversion이 일어나게 하려면 다음 구문이 필요하다.

import PermutableList._

마무리

Implicit Type Conversion을 적용하고 정리한 최종 코드는 다음과 같다

package lasco.homework.nephilim.permutation

class PermutableList(val list:List[Char]) {
  def permutate():List[List[Char]] ={
    PermutableList.permutate(list)
  }

  def removeFirst[T](p:(T)=> Boolean):List[T] = {
    PermutableList.removeFirst(list)(p)
  }

}

object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }

  def removeFirst[T](list:List[T])(p:(T)=> Boolean):List[T] = {
    val index = list.indexWhere(p)
    val (first, _ :: second) = list.splitAt(index)
    first ::: second
  }

  def permutate(list:List[Char]):List[List[Char]] ={
    val heads:List[Char] = list.distinct.sortWith(_ < _)
    heads.flatMap( head => {
      val tail = list.removeFirst( _ == head)
      tail match {
        case Nil => List(List(head))
        case _ => permutate(tail).map ( head :: _ )
      }
    })
  }
}

/*
//@ scala console
import lasco.homework.nephilim.permutation._
import PermutableList._

"A".toList.permutate
res7: List[List[Char]] = List(List(A))

"AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

"ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))
*/