ecgenpy package

Submodules

ecgenpy.combin module

Combinations

ecgenpy.combin.EMK(n: int, k: int, Zero=0, One=1)

The EMK function generates combinations by swapping pairs of integers using the EMK algorithm.

Parameters:

n – The parameter n represents the total number of elements in the combination. It is an

integer value :type n: int :param k: The parameter k represents the number of ones in each combination :type k: int :param 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) :param 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))
...
◽◽◽◾◾◾
◽◽◾◽◾◾
◽◾◽◽◾◾
◾◽◽◽◾◾
◾◽◽◾◽◾
◽◾◽◾◽◾
◽◽◾◾◽◾
◽◾◾◽◽◾
◾◽◾◽◽◾
◾◾◽◽◽◾
◾◾◽◽◾◽
◽◾◾◽◾◽
◾◽◾◽◾◽
◾◽◽◾◾◽
◽◾◽◾◾◽
◽◽◾◾◾◽
◽◾◾◾◽◽
◾◽◾◾◽◽
◾◾◽◾◽◽
◾◾◾◽◽◽

ecgenpy.combin.EMK_gen(n: int, k: int) → Generator

Generate all combinations by homogeneous revoling-door

The EMK_gen function generates combinations (by swapping pairs of integers) using the EMK algorithm.

Parameters:

n – The parameter n represents the total number of elements in the set, and k represents

the number of elements to be selected in each combination :type n: int :param k: The parameter k represents the number of elements to be selected in each combination :type k: int :return: 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

ecgenpy.combin.EMK_neg(n: int, k: int) → Generator

The EMK_neg function generates combinations (by swapping pairs of integers in reverse order) using the EMK algorithm.

Parameters:

n – The parameter n represents the total number of elements in the set, and k represents

the number of elements to be selected in each combination :type n: int :param k: The parameter k represents the number of elements to be selected in each combination :type k: int :return: The function EMK_gen returns a generator object that yields pairs of integers (x, y).

ecgenpy.combin.comb(n: int, k: int) → int

The comb function calculates the number of combinations of k elements from a set of n elements using recursion and memoization.

Parameters:

n – The parameter n represents the total number of items or elements available for selection

in the combination :type n: int :param k: The parameter k represents the number of items to choose from the set of n items. In other words, it represents the size of the combination :type k: int :return: 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

ecgenpy.ehr module

ecgenpy.ehr.Ehr(n: int) → Generator

The function Ehr generates all permutations of a given length using the EHR algorithm.

Parameters:

n (int) – The parameter n represents the number of elements in the permutation

Examples

>>> fruits = list("🍉🍌🍇🍏")
>>> for lst in Ehr(4):
...     mylst = list(fruits[i] for i in lst)
...     print("".join(mylst))
...
🍉🍌🍇🍏
🍌🍉🍇🍏
🍇🍉🍌🍏
🍉🍇🍌🍏
🍌🍇🍉🍏
🍇🍌🍉🍏
🍏🍌🍉🍇
🍉🍌🍏🍇
🍌🍉🍏🍇
🍏🍉🍌🍇
🍉🍏🍌🍇
🍌🍏🍉🍇
🍇🍏🍉🍌
🍏🍇🍉🍌
🍉🍇🍏🍌
🍇🍉🍏🍌
🍏🍉🍇🍌
🍉🍏🍇🍌
🍌🍏🍇🍉
🍇🍏🍌🍉
🍏🍇🍌🍉
🍌🍇🍏🍉
🍇🍌🍏🍉

ecgenpy.ehr.Ehr_gen(n: int) → Generator

The function Ehr generates all permutations of a given length using the EHR algorithm.

The Ehr_gen function is a generator that generates all permutations of length n using the Ehr algorithm. It yields the indices of the elements to be swapped with the first element (index 0) in each permutation. The algorithm works by maintaining two lists, b and c, where b represents the current permutation and c keeps track of the state of the algorithm. The algorithm iterates through the elements of c and updates the elements of b 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

ecgenpy.gray_code module

ecgenpy.gray_code.BRGC(n: int) → Generator

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))
...
◾◾◾◾
◽◾◾◾
◽◽◾◾
◾◽◾◾
◾◽◽◾
◽◽◽◾
◽◾◽◾
◾◾◽◾
◾◾◽◽
◽◾◽◽
◽◽◽◽
◾◽◽◽
◾◽◾◽
◽◽◾◽
◽◾◾◽
◾◾◾◽

ecgenpy.gray_code.BRGC_gen(n: int) → Generator

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

ecgenpy.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

ecgenpy.set_bipart.GEN0(n: int) → Generator

S(n,k,0) even k

Parameters:

n (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_bipart.GEN1(n: int) → Generator

S(n,k,1) even k

Parameters:

n (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_bipart.NEG1(n: int) → Generator

S’(n,k,1) even k

Parameters:

n (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_bipart.set_bipart(n: int) → Generator

[summary]

Parameters:

n (int) – [description]

Yields:

[type] – [description]

Examples

>>> n = 5
>>> b = [0] * n + [1]
>>> print(b[1:])
[0, 0, 0, 0, 1]
>>> for x in set_bipart(n):
...     old = b[x]
...     b[x] = 1 - b[x]
...     print(b[1:], ": Move {} from B{} to B{}".format(x, old, b[x]))
...
[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

ecgenpy.set_bipart.stirling2nd2(n: int) → int

Stirling number of second kind (k = 2)

Parameters:

n (int) – [description]

Returns:

[description]

Return type:

int

Examples

>>> stirling2nd2(5)
15

ecgenpy.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

ecgenpy.set_partition.GEN0_even(n: int, k: int) → Generator

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.

Parameters:

n – The parameter n represents the total number of elements in a sequence. It is an integer

value :type n: int :param k: The parameter k represents the number of elements to be selected from a set of n elements. It is used in the context of generating even-sized subsets of a set :type k: int

ecgenpy.set_partition.GEN0_odd(n: int, k: int) → Generator

S(n,k,0) odd k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.GEN1_even(n: int, k: int) → Generator

S(n,k,1) even k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.GEN1_odd(n: int, k: int) → Generator

S(n,k,1) odd k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.NEG0_even(n: int, k: int) → Generator

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.

Parameters:

n – The parameter n represents the total number of elements in a sequence or set. It is an

integer value :type n: int :param k: The parameter k represents the number of elements to be selected from a set of n elements. It is used to control the iteration and recursion in the function :type k: int

ecgenpy.set_partition.NEG0_odd(n: int, k: int) → Generator

S’(n,k,0) odd k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.NEG1_even(n: int, k: int) → Generator

S’(n,k,1) even k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.NEG1_odd(n: int, k: int) → Generator

S’(n,k,1) odd k

Parameters:

• n (int) – [description]

• k (int) – [description]

Yields:

[type] – [description]

ecgenpy.set_partition.set_partition(n: int, k: int) → Generator

The set_partition function generates all possible set partitions of a set of size n into k blocks.

Parameters:

• n (int) – The parameter n represents the total number of elements in the set

• k (int) – The parameter k represents the number of blocks in the set partition

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

ecgenpy.set_partition.stirling2nd(n: int, k: int) → int

The stirling2nd function calculates the Stirling number of the second kind for given values of n and k.

Parameters:

• n (int) – The parameter n represents the total number of objects or elements in a set

• k – The parameter k represents the number of non-empty subsets that need to be formed from a

set of n elements :type k: int :return: 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

ecgenpy.sjt module

Steinhaus-Johnson-Trotter algorithm

ecgenpy.sjt.PlainChanges(n)

Generate the swaps for the Steinhaus-Johnson-Trotter algorithm (original method).

ecgenpy.sjt.SJT(n: int) → Generator

The function SJT 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 SJT returns a generator object.

Examples

>>> fruits = list("🍉🍌🍇🍏")
>>> for lst in SJT(4):
...     mylst = list(fruits[i] for i in lst)
...     print("".join(mylst))
...
🍉🍌🍇🍏
🍉🍌🍏🍇
🍉🍏🍌🍇
🍏🍉🍌🍇
🍏🍉🍇🍌
🍉🍏🍇🍌
🍉🍇🍏🍌
🍉🍇🍌🍏
🍇🍉🍌🍏
🍇🍉🍏🍌
🍇🍏🍉🍌
🍏🍇🍉🍌
🍏🍇🍌🍉
🍇🍏🍌🍉
🍇🍌🍏🍉
🍇🍌🍉🍏
🍌🍇🍉🍏
🍌🍇🍏🍉
🍌🍏🍇🍉
🍏🍌🍇🍉
🍏🍌🍉🍇
🍌🍏🍉🍇
🍌🍉🍏🍇
🍌🍉🍇🍏

ecgenpy.sjt.SJT_gen(n: int) → Generator

The function SJT_gen generates all permutations of length n using the 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

>>> for i in SJT_gen(4):
...     print("swap {} and {}".format(i, i + 1))
...
swap 2 and 3
swap 1 and 2
swap 0 and 1
swap 2 and 3
swap 0 and 1
swap 1 and 2
swap 2 and 3
swap 0 and 1
swap 2 and 3
swap 1 and 2
swap 0 and 1
swap 2 and 3
swap 0 and 1
swap 1 and 2
swap 2 and 3
swap 0 and 1
swap 2 and 3
swap 1 and 2
swap 0 and 1
swap 2 and 3
swap 0 and 1
swap 1 and 2
swap 2 and 3
swap 0 and 1

ecgenpy.sjt_list module

ecgenpy.sjt_list.SJT2(n: int) → Generator

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.

ecgenpy.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 = ecgenpy.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

• https://setuptools.pypa.io/en/latest/userguide/entry_point.html

• https://pip.pypa.io/en/stable/reference/pip_install

ecgenpy.skeleton.fib(n)

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

ecgenpy.skeleton.main(args)

Wrapper allowing fib() to be called with string arguments in a CLI fashion

Instead of returning the value from fib(), it prints the result to the stdout in a nicely formatted message.

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--verbose", "42"]).

ecgenpy.skeleton.parse_args(args)

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:

argparse.Namespace

ecgenpy.skeleton.run()

Calls main() passing the CLI arguments extracted from sys.argv

This function can be used as entry point to create console scripts with setuptools.

ecgenpy.skeleton.setup_logging(loglevel)

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

ecgenpy.test module

ecgenpy.test.PlainChanges(n)

Generate the swaps for the Steinhaus-Johnson-Trotter algorithm.

Module contents