JavaScript - efficiently create array of binaries strings with number of bits set

Question

Two arguments

string length
number of bits set

example input: 5, 2

output: ["00011", "00101", "00110", "01001", "01010", "01100", "10001", "10010", "10100", "11000"]

example input: 7, 3

output: ["0000111", "0001011", "0001101", "0001110", "0010011", "0010101", "0010110", "0011001", "0011010", "0011100", "0100011", "0100101", "0100110", "0101001", "0101010", "0101100", "0110001", "0110010", "0110100", "0111000", "1000011", "1000101", "1000110", "1001001", "1001010", "1001100", "1010001", "1010010", "1010100", "1011000", "1100001", "1100010", "1100100", "1101000", "1110000"]

Eager algorithm that I created becomes very inefficient starting from length more than 20

const getBinaries = (length, numberOfBitsSet) => {
    const ones = new Array(length).fill(1).join('');
    const max = parseInt(ones, 2) + 1;
    const binaries = [];
    for (let i = 1; i < max; i++) {
        let bin = parseInt(i).toString(2);
        const match = bin.match(/1/g);
        if (!match || match.length !== numberOfBitsSet) {
            continue;
        }
        const strLen = bin.split('').length;
        const zeros = new Array(length - strLen).fill(0).join('');
        bin = `${zeros}${bin}`;
        binaries.push(bin);
    }
    return binaries;
};

Nina Scholz · Accepted Answer · 2021-03-14 22:24:06Z

2

You could take a Generator and create arrays of indices and return at the final step the binary string.

function* g(length, bits, pattern = [], i = 0) {
    if (!bits) {
        yield Array.from({ length }, (_, i) => +pattern.includes(i)).join('');
        return;
    }
    while (i < length) yield* g(length, bits - 1, [...pattern, i], ++i);
}

console.log([...g(5, 2)]);
console.log([...g(7, 3)]);
console.log([...g(21, 5)]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Mar 14, 2021 at 22:24

answered Mar 14, 2021 at 10:42

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Xitroff Over a year ago

that is awesome, very elegant!

Sirko · Accepted Answer · 2021-03-14 10:26:52Z

0

I'd see this as a combinatorics problem. One can interpret this as integer numbers that are the sum of exactly numberOfBitsSet powers of two. So an algorithm could look like this:

Create a list of all powers of two from 2^0 to 2^(length - 1).
Select all subsets from that contain exactly numberOfBitsSet from that set.
Sum up the elements of the previous sets.
Convert the numbers to a binary string using num.toString(2)
Left-pad the results with zeros, such that all contain length characters.

However, with the default JavaScript number type, this will only scale to length of 51 (the default number type's integer precision ends at about 2^51). Afterwards, you might need to resort to the new BigInt type

answered Mar 14, 2021 at 10:26

Sirko

74.3k19 gold badges157 silver badges194 bronze badges

2 Comments

nico Over a year ago

Wouldn't all powers of two always contain just 1 bit set by definition? I think you might want to add a step between 1 and 2. I agree this is a better general approach though!

Sirko Over a year ago

@nico yes, the set in (1) always contains just a single bit set, that's why in you you pick numberOfBitsSet-many of them in (2) and sum them in (3). This should get you the number of bits set.

Collectives™ on Stack Overflow

JavaScript - efficiently create array of binaries strings with number of bits set

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related