Search Results for 'Permutation'

1 POSTS

  1. 2011.02.24 Scala로 모든 종류의 순열 구하기 (3)
 2010년 가을 무렵에 맹수님이 스칼라 스터디에서 출제했던 순열(permutation) 구하기 문제를 공유[각주:1]합니다. 당시 이 퀴즈를 풀기위해 점심 시간 한 번은 고민하느라, 또 한 번은 문제 푸느라 휙~ 보냈던 기억이 있어 지금도 이 순열 퀴즈를 '밥도둑'이라 부릅니다. 당연한 이야기이지만, 풀이 방법은 다양하므로 본문 내용은 참고로 보시면 됩니다.

문제

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

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

목표코드의 형태

우선은 순열로 나타낼 대상 문자열을 List[Char]로 나타내고, List에 permutate라는 메서드를 추가해[각주:2] 다음과 같이 동작할 계획이다.
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))
순열은 여러 종류의 문자열이므로 permutate의 결과는 List의 List, 즉 List[List[Char]]이다.

순열 분석

"ABB"를 순열로 표현한다면 첫째 자리에는 3개의 글자 중 중복을 제거한 A 또는 B 두 가지만이 가능하다. 이를 Tree로 나타내면 다음과 같다.

A 혹은 B가 나왔다면 그 다음은 어떤 문자들이 나와야 할까를 고민하며 트리를 작성하다보니, 자식 노드들은 결국 부모 노드의 문자를 제외한 나머지 문자들의 순열이라는 사실을 알 수 있었다. 


다시 말해 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))
*/
  1. 사실 이번에도 묵은지 포스팅임. 본문은 2010년 9월 초에 임시 저장했던 글임. [본문으로]
  2. Implicit Type Conversion을 활용한다는 의미. 이렇게 Implicit Type Conversion은 기존 클래스 혹은 모듈의 기능 확장에 주로 사용됨. [본문으로]
  3. p는 predicate을 나타냄 [본문으로]
  4. val (first, _ :: second) = ... 에는 tuple pattern과 list pattern이 사용됨 [본문으로]
저작자 표시 비영리 변경 금지
신고

티스토리 툴바