[파이썬] 순열과 조합

순열

순서가 부여된 집합
{1, 2, 3}과 {2, 1, 3}을 다른 집합으로 생각한다. 이게 조합과 순열의 차이점

순열 라이브러리 X

def permutation(brr, depth):
    if depth == N:
        print(*brr)
        return

    for i in range(0, len(arr)):
        if visited[i]: continue

        visited[i]=True
        brr[depth]=arr[i]
        permutation(brr, depth+1)

        visited[i]=False


if __name__ == "__main__":
    N=int(input())
    arr=[i for i in range(1, N+1)]
    visited = [False] * len(arr)
    permutation([0]*N, 0)

자바는 배열은 자동초기화가 되는데 이 친구는 그런 기능이 없는 것 같다.

visited가 가독성이 좋지만 초기화가 귀찮으니 파이썬에서는 비트 연산자를 쓰자

 

 

순열 라이브러리 O

from itertools import permutations

n=int(input())
list=[]

for i in range(1, n+1):
    list.append(i)

for p in permutations(list, n):
    for i in p:
        print(i, end=" ")
    print()

permutations() 함수 리턴값이 튜플로 보인다.

그냥 출력하면 (1, 2, 3) 이런식으로 나오니 반복문을 써서 원하는 포맷으로 변경해준다

 

위에 시간이 라이브러리 썼을 때 걸리는 시간이고 아래 시간이 직접 만들었을 때 이다

결론

• 파이썬에서는 라이브러리를 쓰자
• 자바는 라이브러리가 없다. 직접 만들자

문제 출처 : https://www.acmicpc.net/problem/10974

 

 

조합

순서가 부여되지 않은 집합

 

 

조합 라이브러리X

def combination(start, depth):
    if depth==M:
        for i in range(len(arr)):
            if visited[i]:
                print(arr[i], end=" ")
        print()
        return

    for i in range(start, len(arr)):
        visited[i]=True
        combination(i + 1, depth + 1)
        visited[i]=False


if __name__=="__main__":
    N, M = map(int, input().split())
    arr=[i for i in range(1, N+1)]
    visited=[False]*N
    combination(0, 0)

 

 

조합 라이브러리 O

from itertools import combinations

N, M = map(int, input().split())
arr=[]

for i in range(1, N+1):
    arr.append(i)

for com in combinations(arr, M):
    for c in com:
        print(c, end=" ")
    print()

순열과 마찬가지로 튜플로 리턴한다

 

위에가 라이브러리를 사용했을 때 걸리는 시간이다.

 

결론

• 라이브러리 쓰자

 

문제 출처 : https://www.acmicpc.net/problem/15650