Skip to main content

Searching for combinatorial covers.

Project description


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.


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}


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

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

Source Distribution

CombCov-0.6.5.tar.gz (14.0 kB view hashes)

Uploaded source

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page