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.

Source Distribution

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

Uploaded Source

File details

Details for the file CombCov-0.6.5.tar.gz.

File metadata

  • Download URL: CombCov-0.6.5.tar.gz
  • Upload date:
  • Size: 14.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.22.0 setuptools/42.0.2 requests-toolbelt/0.9.1 tqdm/4.40.2 CPython/3.6.7

File hashes

Hashes for CombCov-0.6.5.tar.gz
Algorithm Hash digest
SHA256 763a5240aa6363da6d0ec8d19104ac9ced2cdec3be087ef27dd2ed7fdbe94293
MD5 77bbef76b47d8e256fb7d51039d4cf23
BLAKE2b-256 da6070507c00589c0164a46d387b8d101e45057c4fafaafdf3ce1145e5edf2b3

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page