📌 순열과 조합

❗ 순열과 조합의 차이는 순서를 고려하느냐의 차이 !

• 순열은 순서를 고려하고, 조합은 순서를 고려하지 않는다.
• 순서를 고려한다는 것은 순서가 다르면 다른 것으로 취급한다는 뜻
• DFS로 순열, 조합을 구현하는 방법을 알아보고자 한다 !

⭐ 순열 (permutation)

• 서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열
• 선택하는 순서가 다르면 서로 다른 것 (즉, AB와 BA가 다르다)

코드 설계

• path : 뽑은 원소들을 저장하는 리스트

• used : 원소들의 사용 유무를 체크하는 리스트

• level : 뽑은 카드 번호 (0 ~ r-1)

• 뽑아야 할 원소가 있는 경우 (level < r), 카드 배열 순회

  • 중복을 허용하지 않음 : 아직 사용하지 않은 카드인지 확인 (used[i] == 0)
  • 카드 뽑고( path[level] = card[i] ) 다음 카드 뽑으러가기 (level+1)

• 4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,

  • ABC, ABD, ACB, ACD, ADB, ADC, BAC, BAD, …., DCA, DCB
  • 모든 경우의 수를 출력하는 코드를 구현하면 다음과 같다.

# 순열
# 중복 허용 x, 순서가 다르면 다른 경우의 수

# 4장의 카드 중에서 3장 뽑기 
card = ['A', 'B', 'C', 'D']
path = [0]*3

# used 배열 사용하여 카드 중복 사용 유무 확인
used = [0]*4

def dfs(level):
		# 3장 모두 뽑았으면 출력하고 return
    if level == 3:
        print(*path)
        return
		# 카드 4장 확인하기
    for i in range(4):
        if used[i] == 0:  # 아직 사용하지 않은 카드이면
            used[i] = 1  # 사용 체크 하고
            path[level] = card[i]  # 카드 뽑기
            dfs(level+1)  # 다음 카드 뽑으러 가기
            used[i] = 0  # 리턴 이후에는 다시 사용 체크 해제
            path[level] = 0  # 뽑은 카드 초기화

dfs(0)

⭐ 중복 순열

• 서로 다른 n개의 원소에서 r개를 중복을 허용하여 선택하여 순서대로 나열
• 선택하는 순서가 다르면 서로 다른 것

코드 설계

• path : 뽑은 원소들을 저장하는 리스트

• level : 뽑은 카드 번호 (0 ~ r-1)

• 뽑아야 할 원소가 있는 경우 (level < r), 카드 배열 순회

  • 카드 뽑고( path[level] = card[i] ) 다음 카드 뽑으러가기 (level+1)

• 4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,

  • AAA, AAB, AAC, AAD, ABA, ABB, …., DDA, DDB, DDC, DDD
  • 모든 경우의 수를 출력하는 코드를 구현하면 다음과 같다.

# 중복 순열 
# 중복 허용, 순서가 다르면 다른 경우의 수

# 4장의 카드 중에서 3장 뽑기 
card = ['A', 'B', 'C', 'D']
path = [0]*3

def dfs(level):
		# 3장 모두 뽑았으면 출력하고 리턴
    if level == 3:
        print(*path)
        return
    for i in range(4):
        path[level] = card[i]  # 카드 뽑고
        dfs(level+1)  # 다음 카드 뽑으러 가기
        path[level] = 0  # 리턴 이후 뽑은 카드 초기화

dfs(0)

⭐ 조합 (combination)

• 서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열
• 뽑는 순서와 관계 없음 (즉, AB와 BA가 같다.)

코드 설계

• path : 뽑은 원소들을 저장하는 리스트

• level : 뽑은 카드 번호 (0 ~ r-1)

• start : 뽑기 시작할 카드 인덱스

• 뽑아야 할 원소가 있는 경우 (level < r)

  • 순서를 고려하지 않음 : 0번째에서 원소 i를 뽑은 경우를 확인했으면, 0번째에서 원소 i+1를 뽑았을 때 1번째에서 원소i를 뽑는 경우는 제외 해야함
    • for문 범위에서 변수 start 를 사용하여 뽑기 시작할 원소 인덱스 정하기
  • 중복을 허용하지 않음 : 직전에 뽑은 카드의 다음 인덱스의 카드 부터 카드 뽑기
  • 카드 뽑고 (path[level] = card[i]) 다음 카드 뽑으러 가기 (level+1, start ← i + 1)

• 4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,

  • ABC, ABD, ACD, BCD
  • 모든 경우의 수를 출력하는 코드를 구현하면 다음과 같다.

# 조합
# 중복 허용 X, 순서가 달라도 같은 경우의 수

# 4장의 카드 중에서 3장 뽑기 
card = ['A', 'B', 'C', 'D']
path = [0]*3

def dfs(level, start):
		# 3장 모두 뽑았으면 출력하고 리턴
    if level == 3:
        print(*path)
        return
    for i in range(start, 4):  
        path[level] = card[i]  # 카드 뽑기
        dfs(level+1, i+1)  # 직전에 뽑은 카드의 다음 인덱스의 카드 부터 카드 뽑기
        path[level] = 0  # 리턴 이후 뽑은 카드 초기화

dfs(0, 0)

조합 응용 - 부분 집합 만들기

• 4장의 카드 (A, B, C, D)로 만들 수 있는 조합 / 조합 개수 출력하기

card = ['A', 'B', 'C', 'D']
path = ['']*4
cnt = 0
def abc(level, start):
    global cnt
    cnt += 1  # 함수 진입할 때마다 cnt +1
    if level == 4:
        return
    for i in range(start, 4):
        path[level] = card[i]
        print(*path)  # 카드 새로 뽑을 때마다 출력
        abc(level+1, i+1)  # 직전에 뽑은 카드의 다음 인덱스의 카드 부터 카드 뽑기
        path[level] = ''  # 리턴 이후 뽑은 카드 초기화

abc(0, 0)
print(cnt)

⭐ 중복 조합

• 서로 다른 n개의 원소에서 r개를 중복을 허용하여 선택하여 순서대로 나열
• 뽑는 순서와 관계 없음 (즉, AB와 BA가 같다.)

코드 설계

• path : 뽑은 원소들을 저장하는 리스트

• level : 뽑은 카드 번호 (0 ~ r-1)

• start : 뽑기 시작할 카드 인덱스

• 뽑아야 할 원소가 있는 경우 (level < r)

  • 순서를 고려하지 않음 : 0번째에서 i를 뽑은 경우를 확인했으면, 0번째에서 i+1를 뽑았을 때 1번째에서 i를 뽑는 경우는 제외 해야함
    • for문 범위에서 변수 start 를 사용하여 뽑기 시작할 원소 인덱스 정하기
  • 중복을 허용 : 직전에 뽑은 카드와 같은 인덱스부터 카드 뽑기
  • 카드 뽑고 (path[level] = card[i]) 다음 카드 뽑으러 가기 (level + 1, start ← i)

• 4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,

  • AAA, AAB, AAC, AAD, ABB, ABC, ABD, …, CCC, CCD, CDD, DDD
  • 모든 경우의 수를 출력하는 코드를 구현하면 다음과 같다.

# 중복 조합
# 중복 허용 O, 순서가 달라도 같은 경우의 수

card = ['A', 'B', 'C', 'D']
path = [0]*3

def dfs(level, start):
		# 3장 모두 뽑았으면 출력하고 리턴
    if level == 3:
        print(*path)
        return 
    for i in range(start, 4):
        path[level] = card[i]  # 카드 뽑기
        dfs(level+1, i)  # 직전에 뽑은 카드와 같은 인덱스부터 카드 뽑기
        path[level] = 0  # 리턴 이후 뽑은 카드 초기화

dfs(0, 0)