조합. [[Probability]]공부의 기초

[[Permutation]]에서는 선택된 아이템들의 순서가 중요하다. [[Combination]]은 순서는 중요하지 않고, n개서 k개를 뽑아내는 가짓수이다. 이것역시 중복허용 조합과 중복비허용 조합으로 나뉜다. a,b,c에서 두개를 뽑는다고 하면,

중복없이 뽑을때 (without repetition)

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

3!/2!= 3 즉 세가지 ab, ac, bc

중복을 허용해서 뽑을 때 (with repetition)

{{{#!latex
$$ {{n+k-1} \choose k} $$
}}}

4!/(2!*2!) = 6 즉 여섯가지 aa, ab, ac, bb, bc, cc

== 조합과 관련된 수식들 ==

{{{#!latex
$ {a \choose 0} = 1$, in particular, ${0 \choose 0} = 1$
}}}
<<BR>>
{{{#!latex  
$$ {n \choose k} = {n \choose {n-k}} $$  
$$ {a \choose k} + {a \choose {k+1}} = {{a+1} \choose {k+1}} $$
$$ \sum_{s=0}^{n-1} {{k+s} \choose k} = {{n+k} \choose {k+1}} $$  
$$ \sum_{k=0}^r {p \choose k} {q \choose {r-k}} = {{p+q} \choose r} $$
}}}

== Python으로 구현하면 ==

중복을 허용하지 않을때
{{{#!python
def combo(aList, size=2): 
    if size==0 or not aList: 
        return [aList[:0]] 
    else: 
        result = [] 
        for i in range(0, (len(aList)-size)+1): 
            pick = aList[i:i+1] 
            rest = aList[i+1:] 
            for x in combo(rest, size-1): 
                result.append(pick+x) 
        return result 
}}}

보다 빠른 속도를 원한다면 ProbStat참고

SeeAlso http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465