[APS] 9. Python으로 순열(Permutation) 만들기

1. 순열(Permutation) 이란?

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 (순서 고려)

• $nPr$ 이라고 표현한다.

• $nPr = n*(n-1)*(n-2)*…*(n-r+1)$

• $nPn = n! = n*(n-1)*….*2*1$

• 12! 이상으로 넘어가면 숫자가 폭발적으로 증가한다!

  → n > 12 이상인 경우에는 잘 사용하지 않는다.

2. python을 이용해서 순열 생성해보기!

• 예를 들어 [1,2,3] 으로 만들 수 있는 모든 순열의 가지수는 어떻게 될까?

→ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

→ 총 6가지!

이 6가지를 출력하는 코드를 작성해보려고 한다.

1. 반복문을 이용해서

for i in range(1,4):
    for j in range(1,4):
        if i!= j:
            for k in range(1,4):
                if k!= i and k!= j:
                    print(i,j,k)

#output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• 다음은 재귀함수를 이용해서 구현해 보자!

  2. 재귀함수를 이용해서

• 어떤 인자가 필요할까?

⇒ i (level의 번호이자, 원하는 p에 채워지는 index)

⇒ k (만들고 싶은 조합에 쓰일 숫자수. 예를 들어 위 상황은 nPk에서의 k)

• 대략적인 구조는 이해가 되었다. 그렇다면, visited (혹은 used)를 이용해서 nPr 를 구현해보자!

  def nPr(i, k):  # nPr(즉 n개에서 순서를 고려하여 k개의 순열을 만드는) 함수를 정의해보겠다.
      if i == k:  # level, 혹은 p의 index 번호가 k에 도달했다면. 즉 원하는 만큼 다 뽑았다면
          print(p)    # 완성된 p를 출력하고
          return  # 이전으로 돌아가자
      else:
          for j in range(N):
              if not used[j]:
                  used[j] = 1
                  p[i] = a[j] # 출력할 배열의 i번째 원소는, a의 j번째 인덱스 값이다.
                  nPr(i+1, k)
                  used[j] = 0 # return 되었을 때, 원복시켜주는 것
  
  a = [1, 3, 5, 6, 8]
  N = len(a)  # 주어진 배열의 길이. nPr에서 n에 해당한다.
  R = 2   # 내가 몇개를 뽑을지 골라본다. nPr에서 r에 해당한다.
  used = [0]*N
  p = [0]*R # 나중에 출력할 것
  nPr(0, R)

  # output
  # 5P2 = 5x4 = 20개가 잘 출력되었음을 확인할 수 있다.
  [1, 3]
  [1, 5]
  [1, 6]
  [1, 8]
  [3, 1]
  [3, 5]
  [3, 6]
  [3, 8]
  [5, 1]
  [5, 3]
  [5, 6]
  [5, 8]
  [6, 1]
  [6, 3]
  [6, 5]
  [6, 8]
  [8, 1]
  [8, 3]
  [8, 5]
  [8, 6]

• 혹은 원소의 자리를 바꾸는 방법으로 구현할 수도 있다.

  def f(i,k):
      if i == k:
          print(p)
          return
      else:
          for j in range(i, k):       # 자기 자신을 그대로 두는 것부터 시작
              p[i], p[j] = p[j], p[i]     # 자리를 바꾼다
              f(i+1, k)
              p[i], p[j] = p[j], p[i]
  p = [1, 2, 3]
  f(0, 3)

  # output 출력결과는 사전식 배열은 아니다.
  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 2, 1]
  [3, 1, 2]

Uploaded by N2T