(python)포함-배제 원칙(The principle of Inclusion-exclusion)

1. 개념

 

포함-배제 원칙은 합집합의 원소의 개수를 구하는 것과 동일하다고 볼 수 있다.

 

<집합의 개수에 따른 공식>

• 집합 2개: |A∪B| = |A| + |B| - |A∩B|
• 집합 3개: |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
• 집합 4개: |A∪B∪C∪D | = |A| + |B| + |C| + |D| - |A∩B| - |A∩C| - |B∩C| - |A∩D| - |B ∩D| - |C∩D| + |A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D| - |A∩ B∩C∩D|

 

위의 공식에서 나타나듯이 집합의 개수를 늘려가면서 교집합 연산을 하는 것을 확인할 수 있다.

부호는 양수, 음수를 번갈아 가며 나타난다.

 

그러므로 집합 n개에 대하여 아래와 같은 공식이 성립한다.

---

포함-배제 원칙 공식

 

---

2. 코드 구성

사용자는 만들고 싶은 집합의 개수와 각 집합 별로 구성 원소를 입력하고, 그에 해당하는 공식과 결괏값을 얻을 수 있는 프로그램.

 

---

2 - 1. makeSet()

 

입력 받은 집합의 개수만큼 각 집합의 이름을 설정하고 원소들을 입력받아 집합을 구성하는 함수

 

#make union acording to input number
def makeSet(lst1, lst2, n):
    #make a name of set from 'A'~
    for i in range(n):
        character = chr(65+i)   #using ASCII CODE
        lst1.append(character)
    #input elements for each set
    for i in range(n):
        print("Enter the elements of set %c."%lst1[i])
        parted_set = set(map(int, input().split())) #input numbers in a line
        lst2.append(parted_set)

 

---

2 - 2. showPIE()

 

위의 개념에서의 공식을 적용하여 집합의 개수만큼 그 공식을 출력해주고, 결괏값을 출력한다.

이 코드에서 특징점은 포함-배제 원칙 공식은 교집합의 연산이 중복되지 않기에 combination(집합 리스트, 선택할 개수) 함수를 이용하여 중복을 피하였다.

 

#show result
def showPIE(lst1, lst2, n):
    global res  #variavle for result value
    res = 0
    #showing │A∪B∪C....∪│
    for i in range(n):
        if i == 0:
            print('│', end='')
        print(lst1[i], end='')
        if i < n - 1:
            print('∪', end='')
        if i == n-1:
            print('│=', end='')
    #showing result
    for i in range(n):
        setting_set = list(combinations(lst1, i + 1))    #calculating combination for the number(i+1)
        renew_set = []
        for e in setting_set:
            renew_set.append(''.join(e))    #using join function for looking string form
        for j in range(len(renew_set)): #repeat the number of subsets
            temp = {}   #temp variable for saving intersection set
            #deciding a sign according to even or odd number of set
            if (i+1) % 2 == 0:
                print('-', end='')
            elif (i+1) % 2 != 0:
                print('+', end='')
            for k in range(len(renew_set[j])):  #repeat as many as the tpye of sets
                if k == 0:
                    print('│', end='')
                    idx = ord(renew_set[j][k]) % 65 #using ASCII and index
                    temp = lst2[idx]
                else:
                    idx = ord(renew_set[j][k]) % 65
                    temp = temp & lst2[idx]   #intersection operation
                print(renew_set[j][k], end='')
                if k == len(renew_set[j]) - 1:  #calculating result value
                    if(i+1) % 2 == 0:
                        res -= len(temp)
                    else:
                        res += len(temp)
                    print('│', end='')
                    break
                print('∩', end='')

 

---

2 - 3. main

 

print('Enter the number of sets you want to make.')
n = int(input())
set_name = []   #list for name of sets
elements_set = []   #list for elements for each set
makeSet(set_name, elements_set, n)
print("Formula:", end='')
showPIE(set_name, elements_set, n)
print("= %d"%res)

 

---

2 - 4. 출력 화면

 

Enter the number of sets you want to make.
3
Enter the elements of set A.
1 2 3 8 9 10
Enter the elements of set B.
3 4 5 6 7 8 9
Enter the elements of set C.
7 8 9 10 11
Formula:│A∪B∪C│=+│A│+│B│+│C│-│A∩B│-│A∩C│-│B∩C│+│A∩B∩C│= 11

 

---