Bruteforce를 위한 순열,조합 컨닝페이퍼

자 이제 짐승같이 문제를 풀기위하여 Bruteforce를 하는데 일단 많이 나오는 순열,조합,중복순열,중복조합 각각 무슨라이브러리 임포트 해야하는지 어느건지 한줄 설명 간다. -> 이거 안하면 맨날 잊어버려 ㅠㅠ

 

아 맞다 시간복잡도 까지해서 n몇 넘으면 박살나는지도 적어야겠다

순열

뭐써야하는가? -> permutations

import itertools
 
a = [1,2,3,4]

res = itertools.permutations(a, 2)

순서를 고려해서 뽑는 경우의수

-> 서로다른 n개에서 r개를 택하여 일렬로 나열하는 경우의 수. -> 이거는 앞뒤 순서 관계까지 고려한거

ex)(1,2) (2,1) 이 다른거

5개에서 3개 뽑는다면

5x4x3 = 60 임

 

123에서 2개 뽑는경우

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

 

시간복잡도:

permutations(크기 n,r)

->n! / r!

대충 O(n!)이다 

즉 대충  N이 11까지 되는것 

이거 r이 크면 은근 차이가 나니까 한번 계산해보고 생각하자

몇개중 몇개인지는 계산해봐야할듯

 

조합

뭐써야하는가? -> combinations

import itertools
 
a = [1,2,3,4]

res = itertools.combinations(a, 2)

순서를 고려하지 않고 뽑는 경우의수 -> 순열보다 당연히 경우의수 적지 그냥 진짜 경우의수만 보는거

ex)(1,2) (2,1) 이 같은거

 

123에서 2개 뽑는경우

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

시간복잡도:

combinations(크기 n,r)

->n! / (n-r)!(r)!

 

 조합은 생각보다 경우의수 커도 괜춘한데? 밑에 나눠지는게 은근 크다.

 

몇개중 몇개인지는 계산해봐야할듯

중복순열

뭐써야하는가? -> product

import itertools

sets = [1,2,3,4,5,6]

data = itertools.product(sets, repeat = 4)
#repeat는 몇개를 뽑을지

 

순서를 고려해서 뽑는데 숫자 중복가능 중복해서 뽑기가능 -> 이거는 앞뒤 순서 관계까지 고려한거 인데 중복해서 같은수 뽑을수있음

ex)(1,2) (2,1) 이 다른거 + (1,1)가능

 

123에서 2개 뽑는경우

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

 

중복조합

뭐써야하는가? -> combinations_with_replacement

import itertools

sets = [1,2,3,4,5,6,10,7,8]

data = itertools.combinations_with_replacement(sets, 5)

중복을 허용하는 경우의수 -> 그냥 순수하게 진짜 뽑을수있는 경우의수인데 같은거 여러번 뽑을수있음 중복으로

ex)(1,2) (2,1) 이 같은거 + (1,1) 가능

 

123에서 2개 뽑는경우

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

 

순열과 조합만 시간복잡도 계산하는거 봤는데 대략 어쩃든 N!에 수렴하고 그냥 11 넘는다 싶으면 다른방법을 찾아보자