Permutation - BioHackersNet

순열. Probability공부의 기초

n개중에 k개를 뽑아 줄세우는 것. Combination에 비해 순서에 의미가 있다. 중복을 허용할때와 허용안할때로 나눌수 있다. a, b, c에서 두개씩 순열을 구하라고했을때

중복을 허용하지 않으면 (without repetition)

$n(n-1)(n-2)\cdots (n-k+1) = \frac{n!}{(n-k)!}$

3!/1!=6 즉 6개의 가짓수가 생긴다. ab, ac, bc, ba, ca, cb

중복을 허용하면 (with repetition)

$n^{k}$

3²=9 즉 9가지 가짓수가 생긴다. ab, ac, bc, ba, ca, cb, aa, bb, cc

Python으로 Permutation구하기

중복을 허용하지 않는 순열의 경우 ComputerProgramming할 때 다음의 경우가 있을 수 있다. (from ProgrammingPython), 보다빠른 속도를 원하면 ProbStat참고.

permute : k=n 즉 모든 아이템들 줄세우기

   1 def permute(list):
   2     if not list:
   3         return [list]
   4     else:
   5         res=[]
   6         for i in range(len(list)):
   7             rest = list[:i]+list[i+1:]
   8             for x in permute(rest):
   9                 res.append(list[i:i+1]+x)
  10         return res

subset : n개중 k선정후 줄세우기

   1 def subset(list, size):
   2     if size == 0 or not list:
   3         return [list[:0]]
   4     else:
   5         result=[]
   6         for i in range(len(list)):
   7             pick=list[i:i+1]
   8             rest = list[:i] + list[i+1:]
   9             for x in subset(rest, size-1):
  10                 result.append(pick+x)
  11         return result

Generator이용

Generator를 이용한 예제 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 참고

   1 def xcombinations(items, n):
   2     if n==0: yield []
   3     else:
   4         for i in xrange(len(items)):
   5             for cc in xcombinations(items[:i]+items[i+1:],n-1):
   6                 yield [items[i]]+cc
   7 
   8 def xuniqueCombinations(items, n):
   9     if n==0: yield []
  10     else:
  11         for i in xrange(len(items)-n+1):
  12             for cc in xuniqueCombinations(items[i+1:],n-1):
  13                 yield [items[i]]+cc
  14 
  15 def xselections(items, n):
  16     if n==0: yield []
  17     else:
  18         for i in xrange(len(items)):
  19             for ss in xselections(items, n-1):
  20                 yield [items[i]]+ss
  21 
  22 def xpermutations(items):
  23     return xcombinations(items, len(items))

etc

제가 집에 와서 찾아보니 작년에 유즈넷에 제가 포스팅한 코드가 있군요. 참고하세요.

   1 def perms(list):
   2   if not list: return [[]]
   3   return [[list[i]] + p for i in range(len(list)) for p in perms(list[:i] + list[i+1:])]
   4 
   5 >>>perms([1,2,3])
   6 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

이걸 TestFirstProgramming과 Refactoring만으로 만들 수도 있습니다. 한번 해보세요. 공부가 많이 될 겁니다. --JuneKim