dankogai / js-combinatorics Goto Github PK

Because I have a lot of combinations, ranging from billion. I'm not using the toArray bigCombinations, memory usage goes it up high.

Sorry, I don't know exact English term for this, but that should be know as Permutation with Repetition, total number of permutations is n ^ r.

I have an alphabet, 'a, b, c, d, e' and need to generate all possible permutations, including ones

[a, a, a, a],
[a, b, a, a]
[a, b, c, a]

etc.

Can it be done with js-combinatorics?

My project depends on ^0.4.0, and as soon as we picked up 0.4.1 we got a breaking change because of the switch from exporting the Combinatorics object to the global namespace (compare 0.4.0 and 0.4.1). Example:

# snippet of "index.js"
7: var combinatorics = require('js-combinatorics').Combinatorics;
...
72: var possibleFilenames = _(combinatorics.power(flags).toArray())

# results in
TypeError: Cannot read property 'power' of undefined
    at coalesceFiles (/Users/daniel.ramagem/.../index.js:72:44)

As it stands now the package should have the major version reved to 1 (e.g., 1.0.0) since this was a breaking API change (see semver reference).

UPDATE: FWIW a colleague just pointed out that before "1.0.0" a project is considered unstable so you can't necessarily expect adherence to the semver ordering.

Thank you for this great library, very useful.

I am wondering, if is it is possible to create pagination for large output and create and fetch only required output based on page number to make it memory efficient.

It is easy to create pagination when you have all results in hand, but it is not memory efficient.

Is there a way to do that ?

I'm using baseN to create a 11x11 array.

const values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2];
const allCombinations = Combinatorics.baseN(values, 11).toArray();

I'm with the out-of-memory error. So i'm wondering if is there a way to limit my result string to show my only the firsts X results?

Thanks.

please can you add function help to get combination of specify target value (number) from array

getCombinationTarget(arr,n,taregtValue);

https://runkit.com/giorgio79/5c17cba0317a9a0015756c65

Looks like permutationCombination for an array of 10 is very slow. Any ideas?

Hi. I'm using baseN to create a combinations from 10 elements(numbers and letters).
I save each array to a file.
Can i somehow start with the last array if I stop generating combinations?

It would be great if you could add a changelog that details what's in each update. It can give people more confidence when upgrading.

The combination algorithm seems to be buggy since 1.x.

As of 1.3.0 [...new Combination([1, 2, 3, 4, 5], 2)] returns the following array:
[[1,2],[1,3],[1,4],[2,1],[2,3],[3,1],[2,4],[3,2],[3,5],[5,1]]

whereas e.g. Python's itertools library returns the correct
[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]].

Combinatorics.C(25, 20) = 53129.99999999999

Expected: 53130

https://jsfiddle.net/27sf94k1/

I don't understand while(a = cmb.next()) console.log(a)
a seems to be an array, so why is it an array of the single options? And what is this next()?

Thank you for a great library.
I see in the package.json file you say the licence is BSD but you don't have a licence file in the repository.

Thanks!

Hi,

Is there possibility to implement .nth(n) function for Combinatorics.combination ?

Hi,

I found RangeError problem with combination function when used arrays with size > 32:

var x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]; var array = Combinatorics.combination(x, 2).toArray();

Any idea for solve it?

Thanks for advance.

Hi, first of all, thanks a lot for building this awesome lib.
I was almost going to implement my own, but I found this and it suits my needs almost perfectly.

The implementation of most functions in this lib is lazy and that's really a good design choice because combinatorics are things just bound to explode in size. However, being forced to consume them in while loops feels a bit outdated.

const cmb = combination([1, 2, 3], 2);
let item;
while((item = cmb.next()) {
  console.log(item);
}

You are probably aware, but JavaScript Generators gives us a more native way of expressing lazy behavior.

I wrote some tiny wrappers around the functions this lib exposes, such as:

import { combination as originalCombination } from 'js-combinatorics';

export default function combination(arr, size) {
  return {
    *[Symbol.iterator]() {
      const cmb = originalCombination(arr, size);

      let item;
      while ((item = cmb.next())) {
        yield item;
      }
    },
  };
}

This way, I can consume it with a for..of loop:

const cmb = combination([1, 2, 3], 2);
for (let item of cmb) {
  console.log(i);
}

Or could even use the spread operator to turn it into an array:

const cmb = combination([1, 2, 3], 2);
const arr = [...cmb];
console.log(arr);

Maybe this could be made built-in. If you are willing to give this a try, I could work on a PR as soon as I have some time off.

It would be great if this package could gain native typescript support. With the 1.0.0 upgrade, this package has become unusable for me because the type definitions provided by DefinitelyTyped are now out of date. It's easier for me to just switch to another package that's natively written in Typescript, where the type definitions will always be in sync.

I'd like to save the state of the iterator to a file, so that I can continue iterating at that exact point on next run. A few values are held via closure, so I can't just serialize the iterator itself. Any ideas?

If I run the following code snippet:

import { Combination } from "js-combinatorics";

const allPossible = new Combination(["en", "es", "pt", "fr", "tr"], 2);

console.log([...allPossible]);

I get the following error:

import { Combination } from 'js-combinatorics';
         ^^^^^^^^^^^
SyntaxError: The requested module 'js-combinatorics' is expected to be of type CommonJS, which does not support named exports. CommonJS modules can be imported by importing the default export.
For example:
import pkg from 'js-combinatorics';
const { Combination } = pkg;
    at ModuleJob._instantiate (internal/modules/esm/module_job.js:98:21)
    at async ModuleJob.run (internal/modules/esm/module_job.js:137:5)
    at async Loader.import (internal/modules/esm/loader.js:162:24)
    at async Object.loadESM (internal/process/esm_loader.js:68:5)

Looks like the package.json of version 1.2.1 is missing the required "type": "module" config in order to work properly with Node.js >=13.

Currenlty I get the following package.json after installing:

{
  "name": "js-combinatorics",
  "version": "1.2.1",
  "description": "Simple combinatorics like power set, combination, and permutation in JavaScript",
  "main": "combinatorics.js",
  "module": "combinatorics.js",
  "types": "combinatorics.d.ts",
  "files": [
    "combinatorics.d.ts",
    "combinatorics.js"
  ],
  "runkitExample": "require=require(\"esm\")(module);\nvar Combinatorics=require(\"js-combinatorics\");\n",
  "devDependencies": {
    "typescript": "^3.9.7",
    "@types/node": "^14.0.26",
    "mocha": "^8.0.0",
    "chai": "^4.2.0"
  },
  "scripts": {
    "test": "make test"
  },
  "repository": {
    "type": "git",
    "url": "git://github.com/dankogai/js-combinatorics.git"
  },
  "keywords": [
    "Combinatorics",
    "combination",
    "permutation"
  ],
  "author": "Dan Kogai",
  "license": "MIT",
  "readmeFilename": "README.md",
  "gitHead": "e3684eb54f7c6fbb24bb7a4d08d88671ce12e9eb"
}

If I change the package.json for js-combinatorics inside node_modules like this:

{
  "name": "js-combinatorics",
  "version": "1.2.1",
+ "type": "module",
  "description": "Simple combinatorics like power set, combination, and permutation in JavaScript",
  "main": "combinatorics.js",
  "module": "combinatorics.js",
  "types": "combinatorics.d.ts",

Then the snippet above executes as expected.

Environment info

• [email protected]
• [email protected]

it should return [] instead. i'm not sure if this is mathematically defined, but it might just be an edge worth testing for.

very nice little library, thank you :)

I am not able to generate base N for the following combinations.

cmb = Combinatorics.baseN(["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "G", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"], 6);
// console.log("All data", cmb.toArray());
//debugger;
console.log("All data", cmb.toArray().slice(1,5));

console.log("done!!");

Getting uncaught exception: out of memory in firefox

and tried in node as well using

node --max-old-space-size=7168 index.js

But can't get it to work. Please advice on how can I fetch first N number of records, without performing a toArray.

<--- Last few GCs --->

  292719 ms: Mark-sweep 7067.8 (7202.5) -> 7067.8 (7202.5) MB, 37117.6 / 0 ms [allocation failure] [GC in old space requested].
  331128 ms: Mark-sweep 7067.8 (7202.5) -> 7067.8 (7202.5) MB, 38409.3 / 0 ms [allocation failure] [GC in old space requested].
  370411 ms: Mark-sweep 7067.8 (7202.5) -> 7067.8 (7202.5) MB, 39283.0 / 0 ms [last resort gc].
  406547 ms: Mark-sweep 7067.8 (7202.5) -> 7067.8 (7202.5) MB, 36136.2 / 0 ms [last resort gc].


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x2f681adc9e31 <JS Object>
    1: toArray [/Volumes/256gb/diksha/combination-cli/node_modules/js-combinatorics/combinatorics.js:~67] [pc=0x1b628d0965c9] (this=0x364faa3580d9 <an Object with map 0x2b5341a31289>,f=0x2f681ad04189 <undefined>)
    2: arguments adaptor frame: 0->1
    3: /* anonymous */(aka /* anonymous */) [/Volumes/256gb/diksha/combination-cli/index.js:121] [pc=0x1b628d08f1a8] (this=0x2f681ad04189 <undefine...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/Users/Sachdev/.nvm/versions/node/v6.3.1/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/Users/Sachdev/.nvm/versions/node/v6.3.1/bin/node]
 3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/Users/Sachdev/.nvm/versions/node/v6.3.1/bin/node]
 4: v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [/Users/Sachdev/.nvm/versions/node/v6.3.1/bin/node]
 5: v8::internal::Runtime_AllocateInTargetSpace(int, v8::internal::Object**, v8::internal::Isolate*) [/Users/Sachdev/.nvm/versions/node/v6.3.1/bin/node]
 6: 0x1b628cf06338
 7: 0x1b628d0965c9
[1]    11802 abort      node --max-old-space-size=7168 index.js

I have generated a billion combinations using this.
What is an efficient way to quickly write them to disc.
So far i keep running out of memory while using fs methods.

For example, if I were to have:

const Combinatorics = require("js-combinatorics");

const group = ["Penelope", "Brad", "Ivan"];

const cmb = Combinatorics.combination(group, 2);

const pairings = cmb.reduce((acc, pair) => `${acc}${pair[0]} ${pair[1]}, `, "");

console.log(pairings);

The output would be P e, B r, I v, instead of the expected Penelope Brad, Penelope Ivan, Brad Ivan, .

Is there any specific reason why this happens besides that it's just a bug? Other array methods like forEach, filter, map, etc. seem to work fine; just not reduce.

Thanks! 😊

According to the documentation, the generators have a "next" function that returns "undefined" if there are no more elements. But, there is no way to check whether there are more elements, without consuming the next element.

Is it possible to add a boolean "hasNext" function (similar to the function with that name in Java) that returns "true" if there are more elements, but does not remove an element from the list?

using the npm version of this module does not work. The combinatorics.js file does not seem to have an export statement and perhaps that is causing the problem?

Node version is v0.12.4.

I have confirmed following tests.

/*
 * use mocha to test me
 * http://visionmedia.github.com/mocha/
 */
var assert, Combinatorics;
if (this['window'] !== this) {
    assert = require("assert");
    Combinatorics = require('../.');
}
var is_deeply = function (a, e, m) {
    return function () {
        assert.equal(JSON.stringify(a), JSON.stringify(e), m)
    }
};
describe('Combinatorics.power', function () {
    var a = [], c = Combinatorics.power(a);
    it(c, is_deeply(c.toArray(), [
        []
    ]));
    a = 'abc'.split(''), c = Combinatorics.power(a);
    it(a, is_deeply(c.toArray(), [
        [],
        ["a"],
        ["b"],
        ["a", "b"],
        ["c"],
        ["a", "c"],
        ["b", "c"],
        ["a", "b", "c"]
    ]));
    it(0+c, is_deeply(0+c, c.toArray().length));
    it(c.length, is_deeply(c.length, c.toArray().length));
    it(a, is_deeply(c.filter(function(a){return a.length === 2}),
                    Combinatorics.combination(a,2).toArray()
           ));

    a = ["a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9",
         "b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8", "b9",
         "c0", "c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9",
         "d0"]
    c = Combinatorics.power(a);
    it(a, is_deeply(c.toArray(), []));

    a = ["a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9",
         "b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8", "b9",
         "c0", "c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9",
         "d0", "d1"]
    c = Combinatorics.power(a);
    it(a, is_deeply(c.toArray(), [[]]));
});

I added two tests to test/power.js. But, I think that its two tests should not be passed.

I'll fork and create a pull request.

I found this when debugging a corner case in the solve24 module and I was able to trace it down to a call to baseN([], n) which results in [] rather than the expected [[]]. Here's an example to help explain: let's say we want to generate all possible ways to perform some set ops of binary operations (like +,-,*,/) on ops.length+1 numbers. To do so, one might call baseN(ops, ops.length) to find all ops.length-size combinations of ops for applying to the ops.length+1 numbers. However, in the case that ops is empty, there is still exactly one possible combination of ops, namely itself. The current, incorrect behavior of baseN([], n) returning [] should be changed to return [[]] instead.

Why not merge those two and simply call bigCombination if ary is bigger than 31? One less thing to think about.

I have a set of elements with possible duplication.

I need to get all possible permutations of combinations but removing duplicates.

Like so:

const all = ['a', 'a', 'b'];
const cmb = Combinatorics.permutationCombination(all);
console.log(cmb.toArray());

Expected output is:

[ [ 'a' ],
  [ 'b' ],
  [ 'a', 'a' ],
  [ 'a', 'b' ],
  [ 'b', 'a' ],
  [ 'a', 'a', 'b' ],
  [ 'a', 'b', 'a' ],
  [ 'b', 'a', 'a' ] ]

but instead, I am getting

[ [ 'a' ],
  [ 'a' ],
  [ 'b' ],
  [ 'a', 'a' ],
  [ 'a', 'a' ],
  [ 'a', 'b' ],
  [ 'b', 'a' ],
  [ 'a', 'b' ],
  [ 'b', 'a' ],
  [ 'a', 'a', 'b' ],
  [ 'a', 'b', 'a' ],
  [ 'a', 'a', 'b' ],
  [ 'a', 'b', 'a' ],
  [ 'b', 'a', 'a' ],
  [ 'b', 'a', 'a' ] ]

So far I have been able to work around this with a control list and checking while iterating. I could refactor this into a lazyFilter that checks such list, but it would pretty much be the same as I still need to externally keep track of the already visited permutations.

Any way to keep this contained within the library?

Expected Behavior

Script should throw an error (e.g. RangeError).

Actual Behavior

Scripts enters an infinite loop.

Steps to Reproduce the Problem

const Combinatorics = require('js-combinatorics');

Combinatorics.permutation(['a', 'b', 'c'], 1.5);

See demo at https://repl.it/repls/DigitalWorriedLinkedlist (press Run button)

Specifications

• Version: 0.5.3
• Platform: Node/Browser

The bigCombination function is not available in the version that exists on NPM, which suggests that the actual published code is out of sync with the published API.

See here: https://tonicdev.com/5709d318ded58c1100e6eb36/5709d318ded58c1100e6eb37

Example from README.md:

cp = Combinatorics.cartesianProduct([0, 1, 2], [0, 10, 20], [0, 100, 200]);

Is there a way to do like this?

var x = [[0, 1, 2], [0, 10, 20], [0, 100, 200]]
cp = Combinatorics.cartesianProduct(x);

Currently, the "filter" function of a generator actually generates all elements. This might take a long time if the power-set is large. Is this possible to add a filter function that returns a filtered generator, such that, the new generator returns filtered elements, but does not generate all elements in advance?

I would like to iterate over the result of baseN.

const baseN = require('js-combinatorics').baseN

for (let [a, b, c, d] of baseN([0, 1], 4)) {
   console.log(a, b, c, d)
}

Also Array.from(baseN([0, 1], 4)) produces a result different from baseN([0, 1], 4).toArray().

I believe that adding a Symbol.iterator property would fix this.

Doesn't seem to work in node 5.10.1. I ran the module's tests with mocha and that worked, so not sure what the issue is.

$ node --version
v5.10.1
$ node
> var Combinatorics = require('js-combinatorics');
undefined
> var cmb, a;
undefined
> cmb = Combinatorics.power(['a','b','c']);
[Number: 8]
> cmb.each(function(a){ console.log(a) });
TypeError: cmb.each is not a function
    at repl:1:5
    at REPLServer.defaultEval (repl.js:269:27)
    at bound (domain.js:287:14)
    at REPLServer.runBound [as eval] (domain.js:300:12)
    at REPLServer.<anonymous> (repl.js:439:12)
    at emitOne (events.js:95:20)
    at REPLServer.emit (events.js:182:7)
    at REPLServer.Interface._onLine (readline.js:211:10)
    at REPLServer.Interface._line (readline.js:550:8)
    at REPLServer.Interface._ttyWrite (readline.js:827:14)

This is probably intended due to the implementation, but it would be nice if the limitation could be removed, or at least well documented.

I followed the install directions:

1. install with bower
2. add script include in the html file.

I also added the 'Combinatorics' object into the core.module file

I get this error:

Module 'Combinatorics' is not available!

This does not seem to work as is in angular.js environment

combinations with repetition are currently not supported, right?
Something like that would be awesome!

Combinatorics.combinationWithRep(['a', 'b', 'c'], 4)
/*
=> [ 
  [ 'a', 'a', 'a', 'a' ],
  [ 'a', 'a', 'a', 'b' ],
  [ 'a', 'a', 'a', 'c' ],
  [ 'a', 'a', 'b', 'b' ],
  [ 'a', 'a', 'b', 'c' ],
  [ 'a', 'a', 'c', 'c' ],
  [ 'a', 'b', 'b', 'b' ],
  [ 'a', 'b', 'b', 'c' ],
  [ 'a', 'b', 'c', 'c' ],
  [ 'a', 'c', 'c', 'c' ],
  [ 'b', 'b', 'b', 'b' ],
  [ 'b', 'b', 'b', 'c' ],
  [ 'b', 'b', 'c', 'c' ],
  [ 'b', 'c', 'c', 'c' ],
  [ 'c', 'c', 'c', 'c' ] 
 ]
*/

Unless I am mistaken, if we have more than 31 items we should use bigCombination instead of combination? It might be helpful for people to clarify this in the README, for example.

Thanks for this great work! :)

Is there a way for this library to handle permutations in pairs?

const collection = ['a', 'b', 'c', 'd'];
const permutations = Combinatorics.permutation(collection, 2);
a b
a c
a d
b a
b c
......

permutation() behaves strangely with input arrays with more than 32 entries.

Somehow it seems to only consider the first number of entries as difference from a multiple of 32 - e.g. from an input of 71 entries it only used the first 7 [ 71 - 2 * 32 = 7 ].

Poking around permutation() function and noticing the bigCombination() variant, I found that using that instead of combination() makes it work correctly.

I don't know whether you want to introduce a new bigPermutation() function or maybe just patch existing permutation() function:

var permutation = function(ary, nelem, fun) {
        [...]
        addProperties(that, {
            valueOf: function() {
                return size;
            },
            init: function() {
                this.cmb = (ary.length <= 32 ? combination(ary, nelem) : bigCombination(ary, nelem));
                this.per = _permutation(this.cmb.next());
            },
        [...]
}

If you run npm publish from the root project it will be installable direcly from command line without using git.

hello, i guess this is not a normal behavior:

var _ = require('underscore');
var Combinatorics = require('js-combinatorics');

> console.log(Combinatorics.combination(_.range(500), 2).toArray().length)
190
> console.log(Combinatorics.bigCombination(_.range(500), 2).toArray().length)
124750

Latest version on npm is 0.3.0, could you please publish the latest version?

It would be great to write an html page with interactive documentation of js-combinatorics.

This is really simple to do that with the klipse plugin.

Disclaimer: I'm the author of KLIPSE

Hi,

It would be helpful for us if you also commit source file. Right now, there is only minified file present in repo.

Thanks,
Pavan

I currently have to apply some hackery to be able to input an array of arrays:

Combinatorics.cartesianProduct().apply(this, [[1,2,3],[4,5,6],[7,8,9]])

It would be nice to also allow for this kind of input:

Combinatorics.cartesianProduct([[1,2,3],[4,5,6],[7,8,9]])

I'm requesting that this project be registered as bower.io package. As it is already a node package & meets the naming & versioning requirements, I don't believe there are any major difficulties in getting this done.

I would be happy to submit a PR with bower.json if you agree.

Thanks for your consideration!