Searching for combinatorial covers.
Project description
CombCov
A generalization of the permutation-specific algorithm Struct -- extended for other types of combinatorial objects.
Demos
Take a look at the demo/
folder in this repo to see examples on how to use
CombCov
with your own combinatorial object. On example finds a String Set
cover for the set of string over the alphabet {a,b}
that avoids the substring
aa
(meaning no string in the set contains aa
as a substring).
$ python -m demo.string_set
[INFO] (CombCov) Enumerating all elements of size up to 7...
[INFO] (CombCov) ...DONE enumerating elements! (Running time: 0.00 sec)
[INFO] (CombCov) Total of 87 elements.
[INFO] (CombCov) Enumeration: [1, 2, 3, 5, 8, 13, 21, 34]
[INFO] (CombCov) Creating binary strings from rules...
[INFO] (CombCov) Bitstring to cover: 154742504910672534362390527
[INFO] (StringSet) Generated 16 subrules
[INFO] (CombCov) ...DONE creating binary strings! (Running time: 0.00 sec)
[INFO] (CombCov) Total of 14 valid rules with 14 distinct binary strings.
[INFO] (CombCov) Searching for a cover for ''*Av(aa) over ∑={a,b}...
[INFO] (CombCov) Gurobi installed on system and set as solver
[INFO] (CombCov) ...DONE searching for a cover! (Running time: 0.02 sec)
Solution found!
- Rule #1: ''*Av(a,b) over ∑={a,b} with bitstring 1
- Rule #2: 'a'*Av(a,b) over ∑={a,b} with bitstring 2
- Rule #3: 'b'*Av(aa) over ∑={a,b} with bitstring 154742431132702343545997108
- Rule #4: 'ab'*Av(aa) over ∑={a,b} with bitstring 73777970190816393416
Development
Run unittests (with coverage for the demo
module as well):
./setup.py test --addopts --cov=demo
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
CombCov-0.3.2.tar.gz
(11.7 kB
view hashes)