Discrete Veerapat

DiscreteVRP เวอร์ชัน 0.1.4 คือ Python package สำหรับฝึกเขียนโปรแกรมและเรียนรู้คณิตศาสตร์ดีสครีต (Discrete Mathematics) ในระดับเบื้องต้น เหมาะสำหรับนักศึกษาที่กำลังเริ่มเรียน Python

Package นี้มี 3 โมดูลหลัก:

• counting สำหรับหลักการนับ
• number_theory สำหรับทฤษฎีจำนวน
• graph_theory สำหรับทฤษฎีกราฟ โดยใช้ NetworkX, NumPy และ Matplotlib

การติดตั้ง

ติดตั้งจากโฟลเดอร์ package:

pip install .

หรือติดตั้งแบบแก้ไขโค้ดได้ทันทีระหว่างพัฒนา:

pip install -e .

การเริ่มต้นใช้งาน

import DiscreteVRP as dv

print(dv.__version__)  # 0.1.4

1. Counting Module

โมดูล Counting ใช้สำหรับโจทย์เกี่ยวกับแฟกทอเรียล การเรียงสับเปลี่ยน การจัดหมู่ และหลักการนับพื้นฐาน

import DiscreteVRP as dv

# แฟกทอเรียล
print(dv.factorial(5))  # 120

# การเรียงสับเปลี่ยน P(n, k)
print(dv.permutation(5, 2))  # 20

# การจัดหมู่ C(n, k)
print(dv.combination(5, 2))  # 10

# Stars and Bars: แจกของ 5 ชิ้นลงใน 3 กล่อง
print(dv.stars_and_bars(5, 3))  # 21

# Stars and Bars: ทุกกล่องต้องมีอย่างน้อย 1 ชิ้น
print(dv.stars_and_bars_at_least_one(5, 3))  # 6

# Floor และ Ceiling
print(dv.floor_function(3.7))    # 3
print(dv.ceiling_function(3.2))  # 4

# Inclusion-Exclusion สำหรับ 2 เซต
print(dv.inclusion_exclusion_2(10, 15, 3))  # 22

# Pigeonhole Principle
print(dv.pigeonhole_principle(10, 3))
# At least 1 hole has 4 pigeons

Fibonacci และ Memoization

ฟังก์ชัน fibonacci() ใช้ recursive function ร่วมกับ memoization เพื่อเก็บคำตอบที่เคยคำนวณแล้ว ทำให้เรียกใช้ซ้ำได้รวดเร็วขึ้น

import DiscreteVRP as dv

print(dv.fibonacci(10))  # 55

การนับการเรียงตัวอักษรที่ไม่ซ้ำกัน

ฟังก์ชัน count_unique_permutations() ใช้ set และ string processing เพื่อคำนวณจำนวนวิธีเรียงตัวอักษรที่มีตัวซ้ำ

import DiscreteVRP as dv

print(dv.count_unique_permutations("AAB"))  # 3
# AAB, ABA, BAA

2. Number Theory Module

โมดูล Number Theory ใช้สำหรับตรวจสอบจำนวนเฉพาะ ห.ร.ม. ค.ร.น. และการคำนวณเกี่ยวกับเลขมอดูลาร์

import DiscreteVRP as dv

# จำนวนคู่และจำนวนคี่
print(dv.is_even(4))  # True
print(dv.is_odd(7))   # True

# จำนวนเฉพาะและจำนวนประกอบ
print(dv.is_prime(29))       # True
print(dv.is_composite(10))   # True

# Division Algorithm
print(dv.division_algorithm(70, 15))
# 70 = 4(15) + 10

# ห.ร.ม. และ ค.ร.น.
print(dv.gcd(48, 18))  # 6
print(dv.lcm(12, 18))  # 36

# จำนวนเฉพาะร่วม
print(dv.is_relatively_prime(15, 28))  # True

Euclidean Algorithm

import DiscreteVRP as dv

dv.euclidean_algorithm_steps(48, 18)

# 48 = 2(18) + 12
# 18 = 1(12) + 6
# 12 = 2(6) + 0

Extended Euclidean Algorithm และ Modular Inverse

import DiscreteVRP as dv

# gcd(17, 43) = 1 และ 17x + 43y = 1
print(dv.extended_gcd(17, 43))

# หา x ที่ทำให้ 3x mod 7 = 1
print(dv.modular_inverse(3, 7))  # 5

Chinese Remainder Theorem

ใช้แก้ระบบสมการมอดูลาร์อย่างง่าย โดย moduli ทุกตัวต้องเป็นจำนวนเฉพาะร่วมกัน

import DiscreteVRP as dv

# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
print(dv.chinese_remainder_theorem([2, 3, 2], [3, 5, 7]))
# 23

3. Graph Theory Module

โมดูล Graph Theory ใช้ networkx เป็นหลักสำหรับสร้างและคำนวณกราฟ และใช้ matplotlib.pyplot สำหรับแสดงรูปกราฟ

สร้างและวาดกราฟ

import DiscreteVRP as dv

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]

graph = dv.create_graph(edges)
dv.draw_graph(graph, "My First Graph")

Connected Graph และ Connected Components

import DiscreteVRP as dv

graph = dv.create_graph([
    ("A", "B"),
    ("B", "C"),
    ("D", "E"),
])

print(dv.is_connected(graph))  # False
print(dv.connected_components(graph))
# [{'A', 'B', 'C'}, {'D', 'E'}]

Adjacency Matrix

ฟังก์ชันนี้คืนค่าเป็น NumPy array

import DiscreteVRP as dv

graph = dv.create_graph([
    ("A", "B"),
    ("B", "C"),
])

matrix = dv.adjacency_matrix(graph, ["A", "B", "C"])
print(matrix)

# [[0 1 0]
#  [1 0 1]
#  [0 1 0]]

Euler Trail และ Euler Circuit

• Euler Trail คือเส้นทางที่เดินผ่านทุกเส้นเชื่อมเพียงครั้งเดียว
• Euler Circuit คือ Euler Trail ที่เริ่มและจบที่จุดยอดเดียวกัน

import DiscreteVRP as dv

graph = dv.create_graph([
    ("A", "B"),
    ("B", "C"),
    ("C", "A"),
])

print(dv.has_euler_path(graph))     # True
print(dv.has_euler_circuit(graph))  # True
print(dv.euler_path(graph))

Tree, Leaf และ Internal Vertex

import DiscreteVRP as dv

tree = dv.create_graph([
    ("A", "B"),
    ("A", "C"),
    ("B", "D"),
    ("B", "E"),
])

print(dv.is_tree(tree))            # True
print(dv.leaf_vertices(tree))      # ['C', 'D', 'E']
print(dv.internal_vertices(tree))  # ['A', 'B']

Minimum Spanning Tree

สามารถเลือกใช้ Kruskal's Algorithm หรือ Prim's Algorithm ได้

import DiscreteVRP as dv

weighted_edges = [
    ("A", "B", 4),
    ("A", "C", 2),
    ("B", "C", 1),
    ("B", "D", 5),
    ("C", "D", 8),
]

graph = dv.create_graph(weighted_edges, weighted=True)

# Kruskal's Algorithm
mst = dv.minimum_spanning_tree(graph, algorithm="kruskal")
print(list(mst.edges(data=True)))

# Prim's Algorithm
prim_mst = dv.minimum_spanning_tree(graph, algorithm="prim")
print(list(prim_mst.edges(data=True)))

dv.draw_graph(mst, "Minimum Spanning Tree")

Dijkstra's Shortest Path

import DiscreteVRP as dv

weighted_edges = [
    ("A", "B", 4),
    ("A", "C", 2),
    ("C", "B", 1),
    ("B", "D", 5),
    ("C", "D", 8),
]

graph = dv.create_graph(weighted_edges, weighted=True)

path, distance = dv.shortest_path(graph, "A", "D")

print(path)      # ['A', 'C', 'B', 'D']
print(distance)  # 8

Graph Coloring

ผลลัพธ์เป็น dictionary ที่เก็บหมายเลขสีของแต่ละจุดยอด

import DiscreteVRP as dv

graph = dv.create_graph([
    ("A", "B"),
    ("B", "C"),
    ("C", "A"),
])

colors = dv.graph_coloring(graph)
print(colors)
# ตัวอย่าง: {'A': 0, 'B': 1, 'C': 2}

Graph Isomorphism เบื้องต้น

ตรวจสอบว่ากราฟ 2 กราฟมีโครงสร้างเหมือนกันหรือไม่

import DiscreteVRP as dv

graph_one = dv.create_graph([("A", "B"), ("B", "C")])
graph_two = dv.create_graph([(1, 2), (2, 3)])

print(dv.graphs_are_isomorphic(graph_one, graph_two))  # True

รายการฟังก์ชัน

Module	Functions
Counting	factorial, permutation, combination, stars_and_bars, stars_and_bars_at_least_one, fibonacci, count_unique_permutations
Number Theory	is_prime, gcd, lcm, extended_gcd, modular_inverse, chinese_remainder_theorem
Graph Theory	create_graph, draw_graph, is_connected, adjacency_matrix, euler_path, is_tree, minimum_spanning_tree, shortest_path, graph_coloring

หมายเหตุ

• ฟังก์ชัน Graph Theory ต้องใช้ networkx และ matplotlib
• ฟังก์ชัน adjacency_matrix() คืนค่าเป็น numpy.ndarray
• ฟังก์ชันสำหรับกราฟถูกออกแบบให้เข้าใจง่าย เหมาะกับการทดลองและการเรียนรู้เบื้องต้น
• Package นี้ไม่ใช่เครื่องมือสำหรับงานกราฟขนาดใหญ่หรือการคำนวณเชิงวิจัย