Differences between revisions 7 and 8
⇤ ← Revision 7 as of 2011-09-07 16:35:30 →
Size: 2945
Editor: 211
Comment:
← Revision 8 as of 2012-06-19 14:39:49 → ⇥
Size: 2947
Editor: 61
Comment:
Deletions are marked like this. Additions are marked like this.
Line 56: Line 56:
[Generator]를 이용한 예제 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 참고 [[Generator]]를 이용한 예제 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 참고

순열. 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} $$

32=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

Permutation (last edited 2012-06-19 14:39:49 by 61)

web biohackers.net