dankogai / js-combinatorics

power set, combination, permutation and more in JavaScript
MIT License
742 stars 97 forks source link

bitwiseIterator not working for some numbers #83

Closed diego0020 closed 2 years ago

diego0020 commented 3 years ago

The bitwise iterator is producing strange results in some cases, for example

            const items = [];
            for( let i = 0; i < 50; i++){
                items.push('aaa-'+i);
            }
            let c = new Combinatorics.Combination(items, 35);
            console.log(c);
            console.log(c.nth(0));
            const it = c.bitwiseIterator();
            console.log(it.next());

the .nth function produces a correct output of length 35,

but the iterator produces only an array of length 3

{
    "value": [
        "aaa-0",
        "aaa-1",
        "aaa-2"
    ],
    "done": false
}

Apparently it works as expected up to 30, the for 31 and 32 it produces only empty arrays, and for larger numbers it truncates the length of the resulting combinations.

Tested on chrome 91 and firefox 91

diego0020 commented 3 years ago

maybe it is related to integers being 32 bits long, can we use bigintegers for n > 30 ?

dankogai commented 2 years ago

It is because c.length = 2250829575120, which is larger than 0xFFFFFFFF or maximum Number that can safely apply bitwise operation. Now that all browsers support BigInt, I have made .bitwiseIterator() use BigInt so it works beyond 0xFFFFFFFF.

https://github.com/dankogai/js-combinatorics/commit/65cff7cc270e71ac18d9def280c0d8cd18078406