순열. [[Probability]]공부의 기초

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

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

{{{#!latex
$$ 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)

{{{#!latex
$$ n^{k} $$
}}}

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


== Python으로 Permutation구하기 ==

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

=== permute : k=n 즉 모든 아이템들 줄세우기 ===
{{{#!python
def permute(list):
    if not list:
        return [list]
    else:
        res=[]
        for i in range(len(list)):
            rest = list[:i]+list[i+1:]
            for x in permute(rest):
                res.append(list[i:i+1]+x)
        return res
}}}

=== subset : n개중 k선정후 줄세우기 ===
{{{#!python
def subset(list, size):
    if size == 0 or not list:
        return [list[:0]]
    else:
        result=[]
        for i in range(len(list)):
            pick=list[i:i+1]
            rest = list[:i] + list[i+1:]
            for x in subset(rest, size-1):
                result.append(pick+x)
        return result
}}}

=== Generator이용 ===
[[Generator]]를 이용한 예제 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 참고
{{{#!python
def xcombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xcombinations(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)-n+1):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc

def xselections(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for ss in xselections(items, n-1):
                yield [items[i]]+ss

def xpermutations(items):
    return xcombinations(items, len(items))
}}}

== etc ==

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

{{{#!python
def perms(list):
  if not list: return [[]]
  return [[list[i]] + p for i in range(len(list)) for p in perms(list[:i] + list[i+1:])]

>>>perms([1,2,3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}}}

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