Skip to main content

Searching for combinatorial covers.

Project description

CombCov

Build Status Coverage Status Requirements Status Licence

PyPi Version PyPi Downloads Python Implementation Python Versions

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 Word Set cover for the set of words over the alphabet {a,b} that avoids the subword aa (meaning no words in the set contains aa as a subword).

$ python -m demo.word_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 and rules...
[INFO] (CombCov) Bitstring to cover: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 
[INFO] (WordSet) Generated 16 subrules
[INFO] (CombCov) ...DONE creating binary strings and rules! (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 with bitstring 000000000000000000000000000000000000000000000000000000000000000000000000000000000000001: ''*Av(a,b) over ∑={a,b}
 - Rule #2 with bitstring 000000000000000000000000000000000000000000000000000000000000000000000000000000000000010: 'a'*Av(a,b) over ∑={a,b}
 - Rule #3 with bitstring 111111111111111111111000000000000011111111111110000000011111111000001111100011100110100: 'b'*Av(aa) over ∑={a,b}
 - Rule #4 with bitstring 000000000000000000000111111111111100000000000001111111100000000111110000011100011001000: 'ab'*Av(aa) over ∑={a,b}

Development

Run unittests (with coverage for the demo module as well):

./setup.py test --addopts --cov=demo

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for CombCov, version 0.6.5
Filename, size File type Python version Upload date Hashes
Filename, size CombCov-0.6.5.tar.gz (14.0 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page