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.
$ npm install geco [-g]require:
const Geco = require( 'geco' );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.js$ 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 (133784560)..
....
- total: 133784580 combinations
- rate: 580687 comb/sec
- time: 230.39 secs
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 |
'cnt' : function ( Number n, Number k ) : Number/*
* 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.
*/
'gen' : function *( Number n, Number k, Array set [, Boolean bitmap ] ) : GeneratorFunction/*
* 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.
*/
'get' : function ( Number n, Number k ) : GeneratorFunctioniterate 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 ).
*/
'get_bm' : function ( Number n, Number k ) : GeneratorFunction/*
* 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).
*/
'mget' : function ( Number k, Number v, Buffer | Number repetitions ) : GeneratorFunctionSee examples.
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.