순열_python

nPr

n!

서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것이다.

보통 대부분의 문제는 n! 으로 풀린다.

 

n! 에서 n이 10정도면.. C기준으로 10초정도면 계산한다. python은 약 30초 정도 걸린다.(가지치기를 안한 기준)

n이 12 이상이면 시간 복잡도는 폭팔적으로 늘어난다.

n이 10~15정도면 가지치기 잘하면 순열로 풀 수 도 있겠구나라고 생각하고 접근하고 만약 15가 넘는다면 순열로 푸는거 아니다.

 

 

바로 코드보자. 크게 visited를 이용한 풀이와 swap를 이용한 풀이가 있다.

 

nPr

# visited

def perm(n, r, k):
    if r == k:
        print(t)
    else:
        for i in range(0, n):
            if visited[i] : continue
            t[k] = a[i]
            visited[i] = True
            perm(n, r, k+1)
            visited[i] = False


a = [1, 2, 3]
t = [0] * 3
visited = [0] * 3
perm(3, 2, 0)

#swap

def myprint(q):
    for i in range(q-1, -1, -1):
        print("%d " % t[i], end="")
    print()

def perm(n, r, q):
    if r == 0:
        myprint(q)
    else:
        for i in range(n-1, -1, -1):
            a[i], a[n-1] = a[n-1], a[i]
            t[r-1] = a[n-1]
            perm(n, r-1, q)
            a[i], a[n - 1] = a[n - 1], a[i]

a = [1,2,3, 4]
t = [0] * 3

perm(4, 2, 2)

 

 

nPn

# visited

def perm(n, k):
    if n == k:
        print(t)
    else:
        for i in range(0, n):
            if visited[i] : continue
            t[k] = a[i]
            visited[i] = True
            perm(n, k+1)
            visited[i] = False

a = [1, 2, 3]
t = [0] * 3
visited = [0] * 3
perm(3, 0)

# swap

def perm(n, k):
    if n == k:
        print(a)
    else:
        for i in range(k, n):
            a[i], a[k] = a[k], a[i]
            perm(n, k+1)
            a[i], a[k] = a[k], a[i]

a = [1,2,3]

perm(3, 0)

 

 

아래는 중복 순열이다.

 

visited

#nPr

def perm(n, r, k):
    if r == k:
        print(t)
    else:
        for i in range(0, n):
            # if visited[i] : continue
            t[k] = a[i]
            # visited[i] = True
            perm(n, r, k+1)
            # visited[i] = False


a = [1, 2, 3]
t = [0] * 2
visited = [0] * 3
perm(3, 2, 0)



##########################################


#nPn

def perm(n, k):
    if n == k:
        print(t)
    else:
        for i in range(0, n):
            # if visited[i] : continue
            t[k] = a[i]
            # visited[i] = True
            perm(n, k+1)
            # visited[i] = False

a = [1, 2, 3]
t = [0] * 3
visited = [0] * 3
perm(3, 0)

 

swap

def myprint(q):
    while(q):
        q -= 1
        print(" %d" % (t[q]), end="")
    print()
def PI(n, r, q):
    if r==0:
        myprint(q)
    else:
        for i in range(n-1, -1, -1):
            a[i], a[n-1] = a[n-1], a[i]
            t[r-1] = a[n-1]
            PI(n, r-1, q)
            a[i], a[n - 1] = a[n - 1], a[i]

a = [1,2,3]
t = [0] * 3

PI(3, 2, 2)