Sets are an unordered data structure with unique elements that can be created in specific ways, allowing for deduplication and various operations between sets. They are commonly used data tools that handle element uniqueness and set relationships.
01
Sets
The corresponding data structure for sets in Python is set, and its basic usage is as follows:
The output result is:
The output result is:
The output result is:
The output result is:
You can use a for statement to iterate over a set:
The output result is:
The output result is:
Sets do not support indexing:
The output result is:
A set with n elements has 2^n subsets. Below we will generate all subsets of set A={a,b,c,d} using four methods.
1. Combinatorial Method
The output result is:
2. Random Generation Method
The output result is:
Since each element may or may not appear in a subset, the total number of subsets is 2×2×2×2=16, and many problems need to be explored using the random generation method.
3. Binary Method
Convert the numbers 0 to 15 into binary 0000, 0001, 0010, 0011,…, 1110, 1111, which correspond to the subsets [], [‘d’], [‘c’], [‘c’,’d’],…,[‘a’,’b’,’c’], [‘a’,’b’,’c’,’d’]. The four bits of binary correspond to the four elements in set A, and for each 1 in the binary representation, the corresponding element from set A is taken to form the subset.
The output result is:
4. Gray Code Method
The Gray code method is generated as follows: The initial list is [[0],[1]], which is the Gray code of length 1. Based on this, we can generate the Gray code of length 2 by copying all elements of the list in reverse order and adding them to the original list, resulting in [[0],[1],[1],[0]]. Then, we add 0 to the second half and 1 to the first half, generating the Gray code of length 2 [[0,0],[1,0],[1,1],[0,1]]. Using the same method, we can generate the Gray code of length 3 [[0,0,0],[1,0,0],[1,1,0],[0,1,0],[0,1,1],[1,1,1],[1,0,1],[0,0,1]]. Note that adjacent elements in the list differ by exactly one digit. If we consider each element in the list as a point in three-dimensional space, these eight points correspond to the vertices of a unit cube in the first quadrant, and the order of the list traverses all vertices along the edges of the cube without repetition.
The code for generating Gray code is as follows:
Now using the Gray function, generate the Gray code of length 4:
The output result is:
Finally, based on the positions of 1s in the Gray code, extract elements from set A to generate subsets:
The output result is:
02
Reference Book
“Exploring the Mathematical Kingdom with Python – Discrete Mathematics and Combinatorial Mathematics”
ISBN:9787302687429
Authors:Mao Yueyue, Bi Wenbin
Price:89.80 yuan
Content Summary
This book is based on a review of a series of classic materials on “Discrete Mathematics and Combinatorial Mathematics” and implements relevant theories, algorithms, and applications using Python. The content includes principles of combinatorial counting, logical foundations, first-order logic, sets, discrete probability, number theory, induction and recursion, relations, the principle of inclusion-exclusion, generating functions, recurrence relations, graph theory, trees, Boolean algebra and switching functions, grammars, finite state machines, and Turing machines. The book is detailed and includes practical examples, aiming to describe relevant mathematical theories in a simple and understandable way.
This book can serve as a learning and experimental textbook for undergraduate students in science and engineering majors at universities, and can also be a reference for those interested in Python programming.
