ec_gen package¶
Submodules¶
ec_gen.combin module¶
Combinations Generator
This code is a collection of functions that work with combinations in mathematics. A combination is a way of selecting items from a larger set where the order doesn’t matter. The main purpose is to calculate the number of possible combinations and generate all possible combinations for a given set of elements.
The code takes two main inputs: ‘n’ (total number of elements in a set) and ‘k’ (how many elements we want to choose). For example, if we have 6 items and want to choose 3 of them, n would be 6 and k would be 3.
Output varies depending on which function is used. Some functions return the total number of possible combinations, while others generate the actual combinations.
The code achieves its purpose through several different algorithms:
‘comb’ uses recursion and memoization to calculate combinations
‘emk_comb_gen’ uses the “homogeneous revolving-door” algorithm to generate all possible combinations by swapping pairs of elements
An important logic flow is how it handles different cases. When generating combinations, it treats even and odd numbers of elements differently, using separate functions for each case. This helps the algorithm work efficiently.
The ‘emk’ function brings everything together. It generates all combinations by starting with ‘k’ ones followed by ‘n-k’ zeros, then repeatedly swapping elements based on pairs from ‘emk_comb_gen’. This allows producing all possible combinations without storing them all in memory at once.
Overall, this provides a comprehensive toolkit for working with combinations, from simple counting to generating all possibilities. It’s designed to be efficient and flexible.
- ec_gen.combin.comb(n: int, k: int) int[source]¶
The comb function calculates the number of combinations of k elements from a set of n elements using recursion and memoization.
- Parameters:
- Returns:
The function comb returns the number of combinations of n items taken k at a time.
Examples
>>> comb(6, 3) 20 >>> comb(6, 4) == comb(6, 2) True >>> comb(6, 5) == comb(6, 1) True >>> comb(6, 6) == comb(6, 0) True
- ec_gen.combin.comb_recur(n: int, k: int) int[source]¶
The function comb_recur calculates the number of combinations of k elements from a set of n elements using recursion and memoization.
- Parameters:
n (int) – The parameter n represents the total number of items to choose from
k (int) – The parameter k represents the number of elements to be chosen from a set of n elements. It is used in the calculation of the binomial coefficient, which is the number of ways to choose k elements from a set of n elements
- Returns:
The function comb_recur returns the sum of two values, val_a and val_b.
- ec_gen.combin.emk(n: int, k: int, zero: int = 0, one: int = 1) Generator[list, None, None][source]¶
The emk function generates combinations by swapping pairs of integers using the emk algorithm.
- Parameters:
n (int) – The parameter n represents the total number of elements in the combination. It is an integer value
k (int) – The parameter k represents the number of ones in each combination
zero – The zero parameter is the value that represents a zero in the generated combinations. In the example code, it is set to 0, defaults to 0 (optional)
one – The value that represents a “1” in the combinations generated by the algorithm, defaults to 1 (optional)
Examples
>>> for s in emk(6, 3, zero="◾", one="◽"): ... print("".join(s)) ... ◽◽◽◾◾◾ ◽◽◾◽◾◾ ◽◾◽◽◾◾ ◾◽◽◽◾◾ ◾◽◽◾◽◾ ◽◾◽◾◽◾ ◽◽◾◾◽◾ ◽◾◾◽◽◾ ◾◽◾◽◽◾ ◾◾◽◽◽◾ ◾◾◽◽◾◽ ◽◾◾◽◾◽ ◾◽◾◽◾◽ ◾◽◽◾◾◽ ◽◾◽◾◾◽ ◽◽◾◾◾◽ ◽◾◾◾◽◽ ◾◽◾◾◽◽ ◾◾◽◾◽◽ ◾◾◾◽◽◽
- ec_gen.combin.emk_comb_gen(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
Generate all combinations by homogeneous revoling-door
The emk_comb_gen function generates combinations (by swapping pairs of integers) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen returns a generator object that yields pairs of integers (x, y).
Examples
>>> for x, y in emk_comb_gen(6, 3): ... print(f"swap {x} and {y}") ... swap 2 and 3 swap 1 and 2 swap 0 and 1 swap 3 and 4 swap 1 and 0 swap 2 and 1 swap 1 and 3 swap 0 and 1 swap 1 and 2 swap 4 and 5 swap 2 and 0 swap 0 and 1 swap 3 and 2 swap 1 and 0 swap 2 and 1 swap 1 and 4 swap 0 and 1 swap 1 and 2 swap 2 and 3
- ec_gen.combin.emk_gen_even(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
Generate all combinations by homogeneous revoling-door
The emk_gen_even function generates combinations (by swapping pairs of integers) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen returns a generator object that yields pairs of integers (x, y).
- ec_gen.combin.emk_gen_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
Generate all combinations by homogeneous revoling-door
The emk_gen_odd function generates combinations (by swapping pairs of integers) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen_odd returns a generator object that yields pairs of integers (x, y).
- ec_gen.combin.emk_neg_even(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
The emk_neg_even function generates combinations (by swapping pairs of integers in reverse order) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen_even returns a generator object that yields pairs of integers (x, y).
- ec_gen.combin.emk_neg_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
The emk_neg_odd function generates combinations (by swapping pairs of integers in reverse order) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen_odd returns a generator object that yields pairs of integers (x, y).
ec_gen.combin_old module¶
Combinations
- ec_gen.combin_old.comb(n: int, k: int) int[source]¶
The comb function calculates the number of combinations of k elements from a set of n elements using recursion and memoization.
- Parameters:
- Returns:
The function comb returns the number of combinations of n items taken k at a time.
Examples
>>> comb(6, 3) 20 >>> comb(6, 4) == comb(6, 2) True >>> comb(6, 5) == comb(6, 1) True >>> comb(6, 6) == comb(6, 0) True
- ec_gen.combin_old.emk(n: int, k: int, Zero: int = 0, One: int = 1) Generator[list[int], None, None][source]¶
The emk function generates combinations by swapping pairs of integers using the emk algorithm.
- Parameters:
n (int) – The parameter n represents the total number of elements in the combination. It is an integer value
k (int) – The parameter k represents the number of ones in each combination
Zero – The Zero parameter is the value that represents a zero in the generated combinations. In the example code, it is set to 0, defaults to 0 (optional)
One – The value that represents a “1” in the combinations generated by the algorithm, defaults to 1 (optional)
Examples
>>> for s in emk(6, 3, Zero="◾", One="◽"): ... print("".join(s)) ... ◽◽◽◾◾◾ ◽◽◾◽◾◾ ◽◾◽◽◾◾ ◾◽◽◽◾◾ ◾◽◽◾◽◾ ◽◾◽◾◽◾ ◽◽◾◾◽◾ ◽◾◾◽◽◾ ◾◽◾◽◽◾ ◾◾◽◽◽◾ ◾◾◽◽◾◽ ◽◾◾◽◾◽ ◾◽◾◽◾◽ ◾◽◽◾◾◽ ◽◾◽◾◾◽ ◽◽◾◾◾◽ ◽◾◾◾◽◽ ◾◽◾◾◽◽ ◾◾◽◾◽◽ ◾◾◾◽◽◽
- ec_gen.combin_old.emk_gen(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
Generate all combinations by homogeneous revoling-door
The emk_gen function generates combinations (by swapping pairs of integers) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen returns a generator object that yields pairs of integers (x, y).
Examples
>>> for x, y in emk_gen(6, 3): ... print(f"swap {x} and {y}") ... swap 2 and 3 swap 1 and 2 swap 0 and 1 swap 3 and 4 swap 1 and 0 swap 2 and 1 swap 1 and 3 swap 0 and 1 swap 1 and 2 swap 4 and 5 swap 2 and 0 swap 0 and 1 swap 3 and 2 swap 1 and 0 swap 2 and 1 swap 1 and 4 swap 0 and 1 swap 1 and 2 swap 2 and 3
- ec_gen.combin_old.emk_neg(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
The emk_neg function generates combinations (by swapping pairs of integers in reverse order) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen returns a generator object that yields pairs of integers (x, y).
ec_gen.ehr module¶
The ehr_gen function
This code defines a function called ehr_gen that generates permutations using Ehrlich-Hopcroft-Reingold (EHR) algorithm. A permutation is a way of arranging a set of items in a different order. The purpose of this code is to efficiently generate all possible permutations of a given length.
The function takes one input: an integer n, which represents number of elements to permute. For example, if n is 3, it will generate permutations for elements [0, 1, 2].
The output of this function is a generator that yields integers. These integers represent index of element that should be swapped with first element (index 0) to create each new permutation. By following these swap instructions, you can generate all possible permutations of n elements.
The algorithm achieves its purpose by using two lists: b and c. List b represents current permutation, while list c keeps track of algorithm’s state. The function enters a loop where it updates these lists according to specific rules, generating a new permutation with each iteration.
The main logic flow involves finding next element to swap by iterating through c list. When it finds right element, it updates c, yields index from b, and then partially reverses b to set up for next permutation. This process continues until all permutations have been generated.
An important aspect of this algorithm is its efficiency. Instead of generating and storing all permutations at once, it yields them one at a time. This approach saves memory and allows for processing of permutations as they’re generated, which can be very useful when working with large sets of elements.
- ec_gen.ehr.ehr_gen(n: int) Generator[int, None, None][source]¶
The function ehr generates all permutations of a given length using EHR algorithm.
The ehr_gen function is a generator that generates all permutations of length n using ehr algorithm. It yields indices of elements to be swapped with first element (index 0) in each permutation. The algorithm works by maintaining two lists, perm and state, where perm represents the current permutation and state keeps track of state of the algorithm. The algorithm iterates through elements of state and updates elements of perm accordingly to generate all possible permutations.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
Examples
>>> for i in ehr_gen(4): ... print(f"swap 0 and {i}") ... swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 3 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 3 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 3 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2
ec_gen.gray_code module¶
Gray Code Generator
This code implements a Gray code generator, which is a sequence of binary numbers where each successive number differs from the previous one by only one bit. The code consists of two main functions: brgc_gen and brgc.
The brgc_gen function generates a sequence of numbers representing which bit to flip in order to create the Gray code sequence. It takes an integer n as input, which represents the number of bits in the binary code. The function uses a recursive approach to generate the sequence. For example, if n is 4, it will produce a sequence like 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0. Each number in this sequence indicates which bit position to flip to get the next Gray code.
The brgc function uses the sequence generated by brgc_gen to create the actual Gray code. It also takes an integer n as input, representing the number of bits. It starts with a list of n zeros and then flips the bits according to the sequence from brgc_gen. The function yields each step of the Gray code sequence as a list of 0s and 1s.
The code achieves its purpose by using a clever recursive algorithm for brgc_gen. For n bits, it first generates the sequence for n-1 bits, then yields n-1 (to flip the nth bit), and then generates the n-1 sequence again. This creates a mirrored pattern that ensures each successive number differs by only one bit.
An important aspect of the code is how it transforms the bit-flipping sequence into the actual Gray code. The brgc function maintains a list of bits and flips them one at a time based on the output of brgc_gen. This transformation is what converts the simple sequence of numbers into a valid Gray code.
The code also includes examples in the docstrings, showing how to use these functions. One example demonstrates printing the Gray code sequence using black and white square characters, which helps visualize the changing bits in the sequence.
- ec_gen.gray_code.brgc(n: int) Generator[list[int], None, None][source]¶
The function brgc generates a binary reflected gray code sequence of length n.
- Parameters:
n (int) – The parameter n represents the number of bits in the binary code
Examples
>>> s = "◾◽" >>> for lst in brgc(4): ... mylst = list(s[i] for i in lst) ... print("".join(mylst)) ... ◾◾◾◾ ◽◾◾◾ ◽◽◾◾ ◾◽◾◾ ◾◽◽◾ ◽◽◽◾ ◽◾◽◾ ◾◾◽◾ ◾◾◽◽ ◽◾◽◽ ◽◽◽◽ ◾◽◽◽ ◾◽◾◽ ◽◽◾◽ ◽◾◾◽ ◾◾◾◽
- ec_gen.gray_code.brgc_gen(n: int) Generator[int, None, None][source]¶
The function brgc_gen generates a sequence of binary reflected gray code numbers up to a given length n.
- Parameters:
n (int) – The parameter n represents the number of bits in the binary reflected gray code sequence
- Returns:
The function brgc_gen returns a generator object.
Examples
>>> for i in brgc_gen(4): ... print(f"flip {i}") ... flip 0 flip 1 flip 0 flip 2 flip 0 flip 1 flip 0 flip 3 flip 0 flip 1 flip 0 flip 2 flip 0 flip 1 flip 0
ec_gen.set_bipart module¶
Set Partition
A set partition of the set [n] = {1,2,3,…,n} is a collection B0, B1, … Bj of disjoint subsets of [n] whose union is [n]. Each Bj is called a block. Below we show the partitions of [4]. The periods separtate the individual sets so that, for example, 1.23.4 is the partition {{1},{2,3},{4}}.
1 block: 1234 2 blocks: 123.4 124.3 134.2 1.234 12.34 13.24 14.23 3 blocks: 1.2.34 1.24.3 14.2.3 13.2.4 12.3.4 4 blocks: 1.2.3.4
Each partition above has its blocks listed in increasing order of smallest element; thus block 0 contains element 1, block1 contains the smallest element not in block 0, and so on. A Restricted Growth string (or RG string) is a sring a[1..n] where a[i] is the block in which element i occurs. Restricted Growth strings are often called restricted growth functions. Here are the RG strings corresponding to the partitions shown above.
1 block: 0000 2 blocks: 0001, 0010, 0100, 0111, 0011, 0101, 0110 3 blocks: 0122, 0121, 0112, 0120, 0102,
…more
Reference: Frank Ruskey. Simple combinatorial Gray codes constructed by reversing sublists. Lecture Notes in Computer Science, #762, 201-208. Also downloadable from http://webhome.cs.uvic.ca/~ruskey/Publications/SimpleGray/SimpleGray.html
- ec_gen.set_bipart.gen0(num: int) Generator[int, None, None][source]
S(num,k,0) even k
The function gen0 generates a sequence of numbers that satisfy a specific condition.
- Parameters:
num (int) – The parameter num represents an integer value
- Returns:
a generator object.
- ec_gen.set_bipart.gen1(num: int) Generator[int, None, None][source]
S(num,k,1) even k
The function gen1 generates a sequence of numbers that satisfy a specific condition.
- Parameters:
num (int) – The parameter num represents an integer value
- Returns:
a generator object.
- ec_gen.set_bipart.neg1(num: int) Generator[int, None, None][source]
S’(num,k,1) even k
The function neg1 generates a sequence of numbers that satisfy a specific condition.
- Parameters:
num (int) – The parameter num represents an integer value
- Returns:
a generator object.
- ec_gen.set_bipart.set_bipart(num: int) Generator[int, None, None][source]
The function set_bipart generates a sequence of moves that partitions a set of size num into two subsets.
- Parameters:
num (int) – The parameter num represents the number of elements in the bi-partition
Examples
>>> num = 5 >>> blocks = [0] * num + [1] >>> print(blocks[1:]) [0, 0, 0, 0, 1] >>> for idx in set_bipart(num): ... old_val = blocks[idx] ... blocks[idx] = 1 - blocks[idx] ... print(blocks[1:], ": Move {} from B{} to B{}".format(idx, old_val, blocks[idx])) ... [0, 0, 0, 1, 1] : Move 4 from B0 to B1 [0, 1, 0, 1, 1] : Move 2 from B0 to B1 [0, 1, 1, 1, 1] : Move 3 from B0 to B1 [0, 0, 1, 1, 1] : Move 2 from B1 to B0 [0, 0, 1, 0, 1] : Move 4 from B1 to B0 [0, 1, 1, 0, 1] : Move 2 from B0 to B1 [0, 1, 0, 0, 1] : Move 3 from B1 to B0 [0, 1, 0, 0, 0] : Move 5 from B1 to B0 [0, 1, 1, 0, 0] : Move 3 from B0 to B1 [0, 0, 1, 0, 0] : Move 2 from B1 to B0 [0, 0, 1, 1, 0] : Move 4 from B0 to B1 [0, 1, 1, 1, 0] : Move 2 from B0 to B1 [0, 1, 0, 1, 0] : Move 3 from B1 to B0 [0, 0, 0, 1, 0] : Move 2 from B1 to B0
- ec_gen.set_bipart.stirling2nd2(num: int) int[source]
The stirling2nd2 function calculates the Stirling number of the second kind for a given integer num (k = 2) using a recursive approach.
- Parameters:
num (int) – The parameter num represents the number of elements in a set
- Returns:
the Stirling number of the second kind for the given input num.
Examples
>>> stirling2nd2(5) 15
ec_gen.set_partition module¶
Set Partition
A set partition of the set [n] = {1,2,3,…,n} is a collection B0, B1, … Bj of disjoint subsets of [n] whose union is [n]. Each Bj is called a block. Below we show the partitions of [4]. The periods separtate the individual sets so that, for example, 1.23.4 is the partition {{1},{2,3},{4}}.
1 block: 1234 2 blocks: 123.4 124.3 134.2 1.234 12.34 13.24 14.23 3 blocks: 1.2.34 1.24.3 14.2.3 13.2.4 12.3.4 4 blocks: 1.2.3.4
Each partition above has its blocks listed in increasing order of smallest element; thus block 0 contains element 1, block1 contains the smallest element not in block 0, and so on. A Restricted Growth string (or RG string) is a sring a[1..n] where a[i] is the block in whcih element i occurs. Restricted Growth strings are often called restricted growth functions. Here are the RG strings corresponding to the partitions shown above.
1 block: 0000 2 blocks: 0001, 0010, 0100, 0111, 0011, 0101, 0110 3 blocks: 0122, 0121, 0112, 0120, 0102,
…more
Reference: Frank Ruskey. Simple combinatorial Gray codes constructed by reversing sublists. Lecture Notes in Computer Science, #762, 201-208. Also downloadable from http://webhome.cs.uvic.ca/~ruskey/Publications/SimpleGray/SimpleGray.html
- ec_gen.set_partition.gen0_even(n: int, k: int) Generator[tuple[int, int], None, None][source]
S(n,k,0) even k
The function gen0_even generates a sequence of tuples that satisfy certain conditions based on the values of n and k.
- ec_gen.set_partition.gen0_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]
S(n,k,0) odd k
The function gen0_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.gen1_even(n: int, k: int) Generator[tuple[int, int], None, None][source]
S(n,k,1) even k
The function gen1_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.gen1_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]
S(n,k,1) odd k
The function gen1_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.neg0_even(n: int, k: int) Generator[tuple[int, int], None, None][source]
S’(n,k,0) even k
The function neg0_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.neg0_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]
S’(n,k,0) odd k
The function neg0_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.neg1_even(n: int, k: int) Generator[tuple[int, int], None, None][source]
S’(n,k,1) even k
The function neg1_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.neg1_odd(n: int, k: int) Generator[tuple[int, int], None, None][source]
S’(n,k,1) odd k
The function neg1_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition.set_partition(n: int, k: int) Generator[tuple[int, int], None, None][source]
The set_partition function generates all possible set partitions of a set of size n into k blocks.
- Parameters:
Examples
>>> n, k = 5, 2 >>> b = [0] * (n - k + 1) + list(range(k)) >>> print(b[1:]) [0, 0, 0, 0, 1] >>> for x, y in set_partition(n, k): ... old = b[x] ... b[x] = y ... print(b[1:], f": Move {x} from block {old} to {y}") ... [0, 0, 0, 1, 1] : Move 4 from block 0 to 1 [0, 1, 0, 1, 1] : Move 2 from block 0 to 1 [0, 1, 1, 1, 1] : Move 3 from block 0 to 1 [0, 0, 1, 1, 1] : Move 2 from block 1 to 0 [0, 0, 1, 0, 1] : Move 4 from block 1 to 0 [0, 1, 1, 0, 1] : Move 2 from block 0 to 1 [0, 1, 0, 0, 1] : Move 3 from block 1 to 0 [0, 1, 0, 0, 0] : Move 5 from block 1 to 0 [0, 1, 1, 0, 0] : Move 3 from block 0 to 1 [0, 0, 1, 0, 0] : Move 2 from block 1 to 0 [0, 0, 1, 1, 0] : Move 4 from block 0 to 1 [0, 1, 1, 1, 0] : Move 2 from block 0 to 1 [0, 1, 0, 1, 0] : Move 3 from block 1 to 0 [0, 0, 0, 1, 0] : Move 2 from block 1 to 0
- ec_gen.set_partition.stirling2nd(n: int, k: int) int[source]
The stirling2nd function calculates the Stirling number of the second kind for given values of n and k.
- Parameters:
- Returns:
The function stirling2nd returns an integer, which is the Stirling number of the second kind for the given values of n and k.
Examples
>>> stirling2nd(5, 2) 15
ec_gen.set_partition_old module¶
Set Partition
A set partition of the set [n] = {1,2,3,…,n} is a collection B0, B1, … Bj of disjoint subsets of [n] whose union is [n]. Each Bj is called a block. Below we show the partitions of [4]. The periods separtate the individual sets so that, for example, 1.23.4 is the partition {{1},{2,3},{4}}.
1 block: 1234 2 blocks: 123.4 124.3 134.2 1.234 12.34 13.24 14.23 3 blocks: 1.2.34 1.24.3 14.2.3 13.2.4 12.3.4 4 blocks: 1.2.3.4
Each partition above has its blocks listed in increasing order of smallest element; thus block 0 contains element 1, block1 contains the smallest element not in block 0, and so on. A Restricted Growth string (or RG string) is a sring a[1..n] where a[i] is the block in whcih element i occurs. Restricted Growth strings are often called restricted growth functions. Here are the RG strings corresponding to the partitions shown above.
1 block: 0000 2 blocks: 0001, 0010, 0100, 0111, 0011, 0101, 0110 3 blocks: 0122, 0121, 0112, 0120, 0102,
…more
Reference: Frank Ruskey. Simple combinatorial Gray codes constructed by reversing sublists. Lecture Notes in Computer Science, #762, 201-208. Also downloadable from http://webhome.cs.uvic.ca/~ruskey/Publications/SimpleGray/SimpleGray.html
- ec_gen.set_partition_old.gen0_even(n: int, k: int) Generator[source]¶
S(n,k,0) even k
The function gen0_even generates a sequence of tuples that satisfy certain conditions based on the values of n and k.
- ec_gen.set_partition_old.gen0_odd(n: int, k: int) Generator[source]¶
S(n,k,0) odd k
The function gen0_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.gen1_even(n: int, k: int) Generator[source]¶
S(n,k,1) even k
The function gen1_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.gen1_odd(n: int, k: int) Generator[source]¶
S(n,k,1) odd k
The function gen1_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.neg0_even(n: int, k: int) Generator[source]¶
S’(n,k,0) even k
The function neg0_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.neg0_odd(n: int, k: int) Generator[source]¶
S’(n,k,0) odd k
The function neg0_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.neg1_even(n: int, k: int) Generator[source]¶
S’(n,k,1) even k
The function neg1_even generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.neg1_odd(n: int, k: int) Generator[source]¶
S’(n,k,1) odd k
The function neg1_odd generates a sequence of tuples that satisfy certain conditions based on the input parameters n and k.
- ec_gen.set_partition_old.set_partition(n: int, k: int) Generator[source]¶
The set_partition function generates all possible set partitions of a set of size n into k blocks.
- Parameters:
Examples
>>> n, k = 5, 2 >>> b = [0] * (n - k + 1) + list(range(k)) >>> print(b[1:]) [0, 0, 0, 0, 1] >>> for x, y in set_partition(n, k): ... old = b[x] ... b[x] = y ... print(b[1:], f": Move {x} from block {old} to {y}") ... [0, 0, 0, 1, 1] : Move 4 from block 0 to 1 [0, 1, 0, 1, 1] : Move 2 from block 0 to 1 [0, 1, 1, 1, 1] : Move 3 from block 0 to 1 [0, 0, 1, 1, 1] : Move 2 from block 1 to 0 [0, 0, 1, 0, 1] : Move 4 from block 1 to 0 [0, 1, 1, 0, 1] : Move 2 from block 0 to 1 [0, 1, 0, 0, 1] : Move 3 from block 1 to 0 [0, 1, 0, 0, 0] : Move 5 from block 1 to 0 [0, 1, 1, 0, 0] : Move 3 from block 0 to 1 [0, 0, 1, 0, 0] : Move 2 from block 1 to 0 [0, 0, 1, 1, 0] : Move 4 from block 0 to 1 [0, 1, 1, 1, 0] : Move 2 from block 0 to 1 [0, 1, 0, 1, 0] : Move 3 from block 1 to 0 [0, 0, 0, 1, 0] : Move 2 from block 1 to 0
- ec_gen.set_partition_old.stirling2nd(n: int, k: int) int[source]¶
The stirling2nd function calculates the Stirling number of the second kind for given values of n and k.
- Parameters:
- Returns:
The function stirling2nd returns an integer, which is the Stirling number of the second kind for the given values of n and k.
Examples
>>> stirling2nd(5, 2) 15
ec_gen.sjt module¶
Steinhaus-Johnson-Trotter Algorithm
This code implements Steinhaus-Johnson-Trotter algorithm, which is a method for generating all possible permutations (arrangements) of a set of items. The code provides two main functions: sjt_gen and PlainChanges, both of which generate a sequence of swaps that, when applied to a list, will produce all possible permutations of that list.
The input for both functions is a single integer n, which represents number of elements in the list to be permuted. For example, if you have a list of 4 items, you would call function with n=4.
The output of these functions is a generator object. A generator is a special type of function that returns a sequence of values over time, rather than computing them all at once and returning them in a list. In this case, generator yields a series of integers representing positions in list where swaps should occur to create each new permutation.
The algorithm works by recursively generating permutations for smaller lists and then using those to build up permutations for larger lists. It starts with the simplest case (n=2) and builds up from there. The key idea is to move the largest element through all positions in the list, and then recursively permute the remaining elements.
The main logic flow in both functions involves alternating between moving “up” (from left to right in the list) and moving “down” (from right to left). This is achieved using two range objects: up and down. The functions yield positions where swaps should occur, alternating between these upward and downward movements.
An important aspect of the algorithm is that it generates permutations in a way that each new permutation differs from the previous one by just a single swap of adjacent elements. This property makes it efficient for certain applications.
The code includes example usage in the docstrings, showing how to apply the generated swaps to a list of fruit emojis. This demonstrates that by following the sequence of swaps produced by these functions, you can generate all possible arrangements of items in your list.
In summary, this code provides a tool for generating all permutations of a list in a systematic and efficient manner, which can be useful in various programming and mathematical applications where you need to consider all possible arrangements of a set of items.
- ec_gen.sjt.PlainChanges(n: int) Generator[int, None, None][source]¶
Generate to swaps for Steinhaus-Johnson-Trotter algorithm (original method).
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function PlainChanges returns a generator object.
Examples
>>> perm = list("🍉🍌🍇🍏") >>> for x in PlainChanges(4): ... print("".join(perm)) ... perm[x], perm[x + 1] = perm[x + 1], perm[x] ... 🍉🍌🍇🍏 🍉🍌🍏🍇 🍉🍏🍌🍇 🍏🍉🍌🍇 🍏🍉🍇🍌 🍉🍏🍇🍌 🍉🍇🍏🍌 🍉🍇🍌🍏 🍇🍉🍌🍏 🍇🍉🍏🍌 🍇🍏🍉🍌 🍏🍇🍉🍌 🍏🍇🍌🍉 🍇🍏🍌🍉 🍇🍌🍏🍉 🍇🍌🍉🍏 🍌🍇🍉🍏 🍌🍇🍏🍉 🍌🍏🍇🍉 🍏🍌🍇🍉 🍏🍌🍉🍇 🍌🍏🍉🍇 🍌🍉🍏🍇
>>> print("".join(perm)) 🍌🍉🍇🍏
- ec_gen.sjt.sjt_gen(n: int) Generator[int, None, None][source]¶
The function sjt_gen generates all permutations of length n using Steinhaus-Johnson-Trotter algorithm.
Note
The list returns to the original permutations after all swaps.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function sjt_gen returns a generator object.
Examples
>>> perm = list("🍉🍌🍇🍏") >>> for x in sjt_gen(4): ... print("".join(perm)) ... perm[x], perm[x + 1] = perm[x + 1], perm[x] ... 🍉🍌🍇🍏 🍉🍌🍏🍇 🍉🍏🍌🍇 🍏🍉🍌🍇 🍏🍉🍇🍌 🍉🍏🍇🍌 🍉🍇🍏🍌 🍉🍇🍌🍏 🍇🍉🍌🍏 🍇🍉🍏🍌 🍇🍏🍉🍌 🍏🍇🍉🍌 🍏🍇🍌🍉 🍇🍏🍌🍉 🍇🍌🍏🍉 🍇🍌🍉🍏 🍌🍇🍉🍏 🍌🍇🍏🍉 🍌🍏🍇🍉 🍏🍌🍇🍉 🍏🍌🍉🍇 🍌🍏🍉🍇 🍌🍉🍏🍇 🍌🍉🍇🍏
>>> print("".join(perm)) 🍉🍌🍇🍏
ec_gen.sjt_list module¶
- ec_gen.sjt_list.sjt2(n: int) Generator[list[int], None, None][source]¶
The function sjt2 generates all permutations of length n using the Steinhaus-Johnson-Trotter algorithm.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function sjt2 is a generator function, which means it yields values instead of returning them. It generates all permutations of length n using the Steinhaus-Johnson-Trotter algorithm. Each permutation is represented as a list of integers.
Examples
>>> for p in sjt2(3): ... print(p) [0, 1, 2] [0, 2, 1] [2, 0, 1] [2, 1, 0] [1, 2, 0] [1, 0, 2]
ec_gen.skeleton module¶
This is a skeleton file that can serve as a starting point for a Python
console script. To run this script uncomment the following lines in the
[options.entry_points] section in setup.cfg:
console_scripts =
fibonacci = ec_gen.skeleton:run
Then run pip install . (or pip install -e . for editable mode)
which will install the command fibonacci inside your current environment.
Besides console scripts, the header (i.e. until _logger…) of this file can
also be used as template for Python modules.
Note
This file can be renamed depending on your needs or safely removed if not needed.
References
- ec_gen.skeleton.main(args: list[str]) None[source]¶
Wrapper allowing
fib()to be called with string arguments in a CLI fashionInstead of returning the value from
fib(), it prints the result to thestdoutin a nicely formatted message.- Parameters:
args (List[str]) – command line parameters as list of strings (for example
["--verbose", "42"]).
- ec_gen.skeleton.parse_args(args: list[str]) Namespace[source]¶
Parse command line parameters
- Parameters:
args (List[str]) – command line parameters as list of strings (for example
["--help"]).- Returns:
command line parameters namespace
- Return type:
Module contents¶
ec_gen - Enumerative Combinatorics Generation
This package provides generators for various combinatorial structures including:
Combinations (via homogeneous revolving-door algorithm)
Permutations (via Steinhaus-Johnson-Trotter and Ehrlich-Hopcroft-Reingold algorithms)
Gray codes (binary reflected Gray code)
Set partitions (via restricted growth strings)
Each module contains generator functions that yield successive elements of the combinatorial structure, allowing memory-efficient iteration over large collections.
Example
>>> from ec_gen import comb, emk, brgc
>>> comb(6, 3) # Number of combinations
20
>>> for seq in emk(3, 1):
... print(seq)
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
- ec_gen.PlainChanges(n: int) Generator[int, None, None][source]¶
Generate to swaps for Steinhaus-Johnson-Trotter algorithm (original method).
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function PlainChanges returns a generator object.
Examples
>>> perm = list("🍉🍌🍇🍏") >>> for x in PlainChanges(4): ... print("".join(perm)) ... perm[x], perm[x + 1] = perm[x + 1], perm[x] ... 🍉🍌🍇🍏 🍉🍌🍏🍇 🍉🍏🍌🍇 🍏🍉🍌🍇 🍏🍉🍇🍌 🍉🍏🍇🍌 🍉🍇🍏🍌 🍉🍇🍌🍏 🍇🍉🍌🍏 🍇🍉🍏🍌 🍇🍏🍉🍌 🍏🍇🍉🍌 🍏🍇🍌🍉 🍇🍏🍌🍉 🍇🍌🍏🍉 🍇🍌🍉🍏 🍌🍇🍉🍏 🍌🍇🍏🍉 🍌🍏🍇🍉 🍏🍌🍇🍉 🍏🍌🍉🍇 🍌🍏🍉🍇 🍌🍉🍏🍇
>>> print("".join(perm)) 🍌🍉🍇🍏
- ec_gen.brgc(n: int) Generator[list[int], None, None][source]¶
The function brgc generates a binary reflected gray code sequence of length n.
- Parameters:
n (int) – The parameter n represents the number of bits in the binary code
Examples
>>> s = "◾◽" >>> for lst in brgc(4): ... mylst = list(s[i] for i in lst) ... print("".join(mylst)) ... ◾◾◾◾ ◽◾◾◾ ◽◽◾◾ ◾◽◾◾ ◾◽◽◾ ◽◽◽◾ ◽◾◽◾ ◾◾◽◾ ◾◾◽◽ ◽◾◽◽ ◽◽◽◽ ◾◽◽◽ ◾◽◾◽ ◽◽◾◽ ◽◾◾◽ ◾◾◾◽
- ec_gen.brgc_gen(n: int) Generator[int, None, None][source]¶
The function brgc_gen generates a sequence of binary reflected gray code numbers up to a given length n.
- Parameters:
n (int) – The parameter n represents the number of bits in the binary reflected gray code sequence
- Returns:
The function brgc_gen returns a generator object.
Examples
>>> for i in brgc_gen(4): ... print(f"flip {i}") ... flip 0 flip 1 flip 0 flip 2 flip 0 flip 1 flip 0 flip 3 flip 0 flip 1 flip 0 flip 2 flip 0 flip 1 flip 0
- ec_gen.comb(n: int, k: int) int[source]¶
The comb function calculates the number of combinations of k elements from a set of n elements using recursion and memoization.
- Parameters:
- Returns:
The function comb returns the number of combinations of n items taken k at a time.
Examples
>>> comb(6, 3) 20 >>> comb(6, 4) == comb(6, 2) True >>> comb(6, 5) == comb(6, 1) True >>> comb(6, 6) == comb(6, 0) True
- ec_gen.ehr_gen(n: int) Generator[int, None, None][source]¶
The function ehr generates all permutations of a given length using EHR algorithm.
The ehr_gen function is a generator that generates all permutations of length n using ehr algorithm. It yields indices of elements to be swapped with first element (index 0) in each permutation. The algorithm works by maintaining two lists, perm and state, where perm represents the current permutation and state keeps track of state of the algorithm. The algorithm iterates through elements of state and updates elements of perm accordingly to generate all possible permutations.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
Examples
>>> for i in ehr_gen(4): ... print(f"swap 0 and {i}") ... swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 3 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 3 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 3 swap 0 and 2 swap 0 and 1 swap 0 and 2 swap 0 and 1 swap 0 and 2
- ec_gen.emk(n: int, k: int, zero: int = 0, one: int = 1) Generator[list, None, None][source]¶
The emk function generates combinations by swapping pairs of integers using the emk algorithm.
- Parameters:
n (int) – The parameter n represents the total number of elements in the combination. It is an integer value
k (int) – The parameter k represents the number of ones in each combination
zero – The zero parameter is the value that represents a zero in the generated combinations. In the example code, it is set to 0, defaults to 0 (optional)
one – The value that represents a “1” in the combinations generated by the algorithm, defaults to 1 (optional)
Examples
>>> for s in emk(6, 3, zero="◾", one="◽"): ... print("".join(s)) ... ◽◽◽◾◾◾ ◽◽◾◽◾◾ ◽◾◽◽◾◾ ◾◽◽◽◾◾ ◾◽◽◾◽◾ ◽◾◽◾◽◾ ◽◽◾◾◽◾ ◽◾◾◽◽◾ ◾◽◾◽◽◾ ◾◾◽◽◽◾ ◾◾◽◽◾◽ ◽◾◾◽◾◽ ◾◽◾◽◾◽ ◾◽◽◾◾◽ ◽◾◽◾◾◽ ◽◽◾◾◾◽ ◽◾◾◾◽◽ ◾◽◾◾◽◽ ◾◾◽◾◽◽ ◾◾◾◽◽◽
- ec_gen.emk_comb_gen(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
Generate all combinations by homogeneous revoling-door
The emk_comb_gen function generates combinations (by swapping pairs of integers) using the emk algorithm.
- Parameters:
- Returns:
The function emk_gen returns a generator object that yields pairs of integers (x, y).
Examples
>>> for x, y in emk_comb_gen(6, 3): ... print(f"swap {x} and {y}") ... swap 2 and 3 swap 1 and 2 swap 0 and 1 swap 3 and 4 swap 1 and 0 swap 2 and 1 swap 1 and 3 swap 0 and 1 swap 1 and 2 swap 4 and 5 swap 2 and 0 swap 0 and 1 swap 3 and 2 swap 1 and 0 swap 2 and 1 swap 1 and 4 swap 0 and 1 swap 1 and 2 swap 2 and 3
- ec_gen.set_bipart(num: int) Generator[int, None, None][source]¶
The function set_bipart generates a sequence of moves that partitions a set of size num into two subsets.
- Parameters:
num (int) – The parameter num represents the number of elements in the bi-partition
Examples
>>> num = 5 >>> blocks = [0] * num + [1] >>> print(blocks[1:]) [0, 0, 0, 0, 1] >>> for idx in set_bipart(num): ... old_val = blocks[idx] ... blocks[idx] = 1 - blocks[idx] ... print(blocks[1:], ": Move {} from B{} to B{}".format(idx, old_val, blocks[idx])) ... [0, 0, 0, 1, 1] : Move 4 from B0 to B1 [0, 1, 0, 1, 1] : Move 2 from B0 to B1 [0, 1, 1, 1, 1] : Move 3 from B0 to B1 [0, 0, 1, 1, 1] : Move 2 from B1 to B0 [0, 0, 1, 0, 1] : Move 4 from B1 to B0 [0, 1, 1, 0, 1] : Move 2 from B0 to B1 [0, 1, 0, 0, 1] : Move 3 from B1 to B0 [0, 1, 0, 0, 0] : Move 5 from B1 to B0 [0, 1, 1, 0, 0] : Move 3 from B0 to B1 [0, 0, 1, 0, 0] : Move 2 from B1 to B0 [0, 0, 1, 1, 0] : Move 4 from B0 to B1 [0, 1, 1, 1, 0] : Move 2 from B0 to B1 [0, 1, 0, 1, 0] : Move 3 from B1 to B0 [0, 0, 0, 1, 0] : Move 2 from B1 to B0
- ec_gen.set_partition(n: int, k: int) Generator[tuple[int, int], None, None][source]¶
The set_partition function generates all possible set partitions of a set of size n into k blocks.
- Parameters:
Examples
>>> n, k = 5, 2 >>> b = [0] * (n - k + 1) + list(range(k)) >>> print(b[1:]) [0, 0, 0, 0, 1] >>> for x, y in set_partition(n, k): ... old = b[x] ... b[x] = y ... print(b[1:], f": Move {x} from block {old} to {y}") ... [0, 0, 0, 1, 1] : Move 4 from block 0 to 1 [0, 1, 0, 1, 1] : Move 2 from block 0 to 1 [0, 1, 1, 1, 1] : Move 3 from block 0 to 1 [0, 0, 1, 1, 1] : Move 2 from block 1 to 0 [0, 0, 1, 0, 1] : Move 4 from block 1 to 0 [0, 1, 1, 0, 1] : Move 2 from block 0 to 1 [0, 1, 0, 0, 1] : Move 3 from block 1 to 0 [0, 1, 0, 0, 0] : Move 5 from block 1 to 0 [0, 1, 1, 0, 0] : Move 3 from block 0 to 1 [0, 0, 1, 0, 0] : Move 2 from block 1 to 0 [0, 0, 1, 1, 0] : Move 4 from block 0 to 1 [0, 1, 1, 1, 0] : Move 2 from block 0 to 1 [0, 1, 0, 1, 0] : Move 3 from block 1 to 0 [0, 0, 0, 1, 0] : Move 2 from block 1 to 0
- ec_gen.sjt2(n: int) Generator[list[int], None, None][source]¶
The function sjt2 generates all permutations of length n using the Steinhaus-Johnson-Trotter algorithm.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function sjt2 is a generator function, which means it yields values instead of returning them. It generates all permutations of length n using the Steinhaus-Johnson-Trotter algorithm. Each permutation is represented as a list of integers.
Examples
>>> for p in sjt2(3): ... print(p) [0, 1, 2] [0, 2, 1] [2, 0, 1] [2, 1, 0] [1, 2, 0] [1, 0, 2]
- ec_gen.sjt_gen(n: int) Generator[int, None, None][source]¶
The function sjt_gen generates all permutations of length n using Steinhaus-Johnson-Trotter algorithm.
Note
The list returns to the original permutations after all swaps.
- Parameters:
n (int) – The parameter n represents the number of elements in the permutation
- Returns:
The function sjt_gen returns a generator object.
Examples
>>> perm = list("🍉🍌🍇🍏") >>> for x in sjt_gen(4): ... print("".join(perm)) ... perm[x], perm[x + 1] = perm[x + 1], perm[x] ... 🍉🍌🍇🍏 🍉🍌🍏🍇 🍉🍏🍌🍇 🍏🍉🍌🍇 🍏🍉🍇🍌 🍉🍏🍇🍌 🍉🍇🍏🍌 🍉🍇🍌🍏 🍇🍉🍌🍏 🍇🍉🍏🍌 🍇🍏🍉🍌 🍏🍇🍉🍌 🍏🍇🍌🍉 🍇🍏🍌🍉 🍇🍌🍏🍉 🍇🍌🍉🍏 🍌🍇🍉🍏 🍌🍇🍏🍉 🍌🍏🍇🍉 🍏🍌🍇🍉 🍏🍌🍉🍇 🍌🍏🍉🍇 🍌🍉🍏🍇 🍌🍉🍇🍏
>>> print("".join(perm)) 🍉🍌🍇🍏
- ec_gen.stirling2nd(n: int, k: int) int[source]¶
The stirling2nd function calculates the Stirling number of the second kind for given values of n and k.
- Parameters:
- Returns:
The function stirling2nd returns an integer, which is the Stirling number of the second kind for the given values of n and k.
Examples
>>> stirling2nd(5, 2) 15
- ec_gen.stirling2nd2(num: int) int[source]¶
The stirling2nd2 function calculates the Stirling number of the second kind for a given integer num (k = 2) using a recursive approach.
- Parameters:
num (int) – The parameter num represents the number of elements in a set
- Returns:
the Stirling number of the second kind for the given input num.
Examples
>>> stirling2nd2(5) 15