[Python] 순열과 조합 (Permutation and Combination)

순열 (Permutation)

: 서로 다른 n개에서 r개를 선택할 때 순서를 고려하여 선택한 경우의 수를 나열하는 방법 (중복 허용x)

- nPr (0 <= r <=n)

- 순서를 고려한다는 것은 AB와 BA를 서로 다른 것이라고 여기는 것

 

• nPr = n * (n-1) * (n-2) * .... *(n-r+1)
• nPr = n! / (n-r)!

from itertools import permutations

iterator = [1, 2, 3, 4]
for i in permutations(iterator, 2):
    print(i)

(1, 2)
(1, 3)
(1, 4)
(2, 1)
(2, 3)
(2, 4)
(3, 1)
(3, 2)
(3, 4)
(4, 1)
(4, 2)
(4, 3)

 

 

 

조합 (Combination)

: 서로 다른 n개에서 r개를 선택할 때 순서를 고려하지 않고 선택한 경우의 수를 나열하는 방법

- nCr

- 순서를 고려한다는 것은 AB와 BA를 서로 같은 것이라고 여기는 것

• nCr = n * (n-1) * (n-2) * .... *(n-r+1) / r * (r-1) * (r-2) * ...* 2 * 1
• nCr = n! / r! (n-r)!

from itertools import combinations

iterator = [1, 2, 3, 4]
for i in combinations(iterator, 3):
    print(i)

 

(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)

 

 

중복 순열

: 반복 가능한 객체에 대해서 중복을 허용한다.

from itertools import product

iterator1 = ['A', 'B', 'C']
iterator2 = ['1', '2', '3']

for i in product(iterator1, iterator2, repeat=1):
    print(i)

('A', '1')
('A', '2')
('A', '3')
('B', '1')
('B', '2')
('B', '3')
('C', '1')
('C', '2')
('C', '3')