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
• Run Tests
• Run Benchmarks
• Properties
  • cnt
  • gen
  • get
  • get_bm
  • mget
• Events
• Examples
  • Simple Example
  • Cards Example
  • Cartesian Product
  • 52-Card Deck Example
  • Simple Multiset Example
  • Multiset Example
  • Multiset Fixed Repetitions Example
  • 7-card Poker Boards Example
  • 5 different cards Poker Boards Example
• MIT License

Install

$ npm install geco [-g]

require:

const Geco  = require( 'geco' );

Run Tests

to run all test files, install devDependencies:

 $ cd geco/
 # install or update devDependencies
 $ npm install 
 # run tests
 $ npm test

to execute a single test file simply do:

 $ node test/file-name.js

Run Benchmarks

$ cd geco/
$ npm run bench

to execute a single bench file, simply do:

 $ node bench/file-name.js

output 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

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

'cnt' : function ( Number n, Number k ) : Number

Geco.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.
 */
'gen' : function *( Number n, Number k, Array set [, Boolean bitmap ] ) : GeneratorFunction

Geco.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.
 */
'get' : function ( Number n, Number k ) : GeneratorFunction

Geco.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 ).
 */
'get_bm' : function ( Number n, Number k ) : GeneratorFunction

Geco.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).
 */
'mget' : function ( Number k, Number v, Buffer | Number repetitions ) : GeneratorFunction

Examples

• Simple Example
• Cards Example
• Cartesian Product
• 52-Card Deck Example
• Simple Multiset Example
• Multiset Example
• Multiset Fixed Repetitions Example
• 7-card Poker Boards Example
• 5 different cards Poker Boards Example

See examples.

MIT License

Copyright (c) 2018-present < Guglielmo Ferri : [email protected] >

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.