Geco
Geco, a CAT (Constant Amortized Time) recursive generator* for k-combinations chosen from a given set S of n elements, with and without replacement.
It is extremely memory efficient and very fast, it generates all the k-combinations in a set of n elements, using a single sequence of n bits, only 1 bit per element.
It is also able to generate all the k-combinations of a given multiset, aka compositions with restricted parts, of which, combinations with repetition are the general case (without limits on possible repetitions).
NOTE: It generates combinations in Colexicographic Order.
Table of Contents
Install
$ npm install geco [-g]require:
const Geco = ;Run Tests
to run all test files, install devDependencies:
$ cd geco/ # install or update devDependencies $ npm install # run tests $ npm testto execute a single test file simply do:
$ node test/file-name.jsRun Benchmarks
$ cd geco/$ npm run benchto execute a single bench file, simply do:
$ node bench/file-name.jsoutput example and running time:
- generate all boards of 5 cards from a deck of 52, without repetition/replacement - the 52-card deck is: A♠ K♠ Q♠ J♠ T♠ 9♠ 8♠ 7♠ 6♠ 5♠ 4♠ 3♠ 2♠ A♣ K♣ Q♣ J♣ T♣ 9♣ 8♣ 7♣ 6♣ 5♣ 4♣ 3♣ 2♣ A♦ K♦ Q♦ J♦ T♦ 9♦ 8♦ 7♦ 6♦ 5♦ 4♦ 3♦ 2♦ A♥ K♥ Q♥ J♥ T♥ 9♥ 8♥ 7♥ 6♥ 5♥ 4♥ 3♥ 2♥ - generating 5-combinations.. .... - total: 2598960 combinations- rate: 621760 comb/sec- time: 4.18 secs - generating all 7-combinations .. .... - total: 133784580 combinations- rate: 580687 comb/sec- time: 230.39 secs Methods
Arguments between [ ] are optional.
| name | description |
|---|---|
| cnt | count the number of k-combinations of n elements, without repetition |
| gen | get a generator to produce combinations of k elements from a given set, without repetition |
| get | iterate on k-combinations of n elements, without replacement, represented as buffers |
| get_bm | iterate on k-combinations of n elements, without replacement, represented as bitmaps |
| mget | iterate on k-combinations from a mulitiset of v different types, represented as buffers |
Geco.cnt
get the total number of k-combinations from n elements, without replacement
: NumberGeco.gen
iterate on all k-combination of a given set, without replacement
/* * get a generator for iterating on all combinations of k elements, * chosen from the first n items of the given set. Optionally, it * may uses also a bitmap, for generating combinations. * * NOTE: it consumes only n bytes in memory to generate all * combinations, instead, with bitmap, it uses only n bits. */ : GeneratorFunctionGeco.get
iterate on all k-combinations of n elements, without replacement, represented as buffers
/* * the iterator's value is a Buffer with k bytes set to 1. * Every 1 (a byte) represents a chosen element for the current combination. */ : GeneratorFunctionGeco.get_bm
iterate on all k-combinations of n elements, without replacement, represented as bitmaps (Toni)
/* * the iterator's value is a bitmap with k bits set to 1. * Every 1 (a bit) represents a chosen element for the current combination. * * NOTE: to check if the element at index i has been chosen use bitmap.chk( i ). */ : GeneratorFunctionGeco.mget
iterate on k-combinations of a mulitiset of v different types, with replacement
/* * aka compositions with restricted parts, repeated elements are allowed within * certain limits. * * NOTE: when all specified repetitions are (>)= v, it simply generates all the * combinations with repetition. ( n + r − 1 )! / r!( n − 1 )! * * the iterator's value is a Buffer representing the number of elements chosen * for every type/value, according to the limit imposed by the repetition buffer. * * NOTE: the repetitions buffer should contain the nummber of max allowable * repetitions for every type/value. If the max repetitions for a chosen type * are > 256 you should use 2 byte per type (16 bits numbers), in the same * manner, if repetitions > 65536 you should use 4 bytes per type (32 bits). * The buffer returned by the iterator should be read coherently to the number * of bytes used for every type in the repetition buffer (1,2 or 4 bytes). */ : GeneratorFunctionExamples
See examples.
MIT License
Copyright (c) 2018-present < Guglielmo Ferri : 44gatti@gmail.com >
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.