BioHackersNet순열. Probability공부의 기초
n개중에 k개를 뽑아 줄세우는 것. Combination에 비해 순서에 의미가 있다. 중복을 허용할때와 허용안할때로 나눌수 있다. a, b, c에서 두개씩 순열을 구하라고했을때
중복을 허용하지 않으면 (without repetition)
3!/1!=6 즉 6개의 가짓수가 생긴다. ab, ac, bc, ba, ca, cb
중복을 허용하면 (with repetition)
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
11
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
12
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))
24
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]]
7
이걸 TestFirstProgramming과 Refactoring만으로 만들 수도 있습니다. 한번 해보세요. 공부가 많이 될 겁니다. --JuneKim