Creating a custom binary pattern from a given number

Question

Given n, I have a binary pattern to be generated like this in a part of my application:

n = 0

0 -> 0

n = 1

0 -> 0
1 -> 1

n = 2

0 -> 00
1 -> 01
2 -> 10
3 -> 11

n = 3

0 -> 000
1 -> 001
2 -> 010
3 -> 100
4 -> 011
5 -> 101
6 -> 110
7 -> 111

n = 4

0 -> 0000
1 -> 0001
2 -> 0010
3 -> 0100
4 -> 1000
5 -> 0011
6 -> 0101
7 -> 1001
8 -> 0110
9 -> 1010
10 -> 1100
11 -> 0111
12 -> 1011
13 -> 1101
14 -> 1110
15 -> 1111

n = 5

0 -> 00000
1 -> 00001
2 -> 00010
3 -> 00100
4 -> 01000
5 -> 10000
6 -> 00011
7 -> 00101
8 -> 01001
9 -> 10001
10 -> 00110
11 -> 01010
12 -> 10010
13 -> 01100
14 -> 10100
15 -> 11000
16 -> 00111
17 -> 01011
18 -> 10011
19 -> 01101
20 -> 10101
21 -> 11001
22 -> 01110
23 -> 10110
24 -> 11010
25 -> 11100
26 -> 01111
27 -> 10111
28 -> 11011
29 -> 11101
30 -> 11110
31 -> 11111

I'll try to explain this algorithm the best way I can:

The algorithm has loops. In each loop, an extra bit is flipped. Then combinations are to be made out of it.

So in the first loop, no bits are 1s.

In the second loop, only one bit is 1. We need to first go through all possible combinations, in such an order that the leftmost bits are lit only after all combinations for the rightmost bits are over.

Similarly keep proceeding to further loops.

I'm not sure how to write an efficient code for it. One thing I could think of is like a DP solution to this problem. But could there be a more elegant, something like a mathematical solution, where I could put in 'n' and get the binary pattern equivalent?

Answer 1

You could use a recursive approach. In the main routine, increase the number of one-bits you want to produce (from 1 to n), and then call a recursive function that will do that job as follows:

It chooses a bit to set to 1, and then calls the function recursively to use the remaining bits at the right of it, to place one fewer one-bits.

Here is an implementation in JavaScript, with a demo run for n=4:

function * generateOnes(numDigits, numOnes) {
    if (numDigits === 0 || numOnes === 0) {
        yield 0;
    } else {
        for (let pos = numOnes - 1; pos < numDigits; pos++) {
            for (let result of generateOnes(pos, numOnes - 1)) {
                yield (1 << pos) | result;
            }            
        }
    }
}

function * generate(numDigits) {
    for (let numOnes = 1; numOnes <= numDigits; numOnes++) {
        yield * generateOnes(numDigits, numOnes);
    }
}

// Demo with n=4:
for (let result of generate(4)) {
    console.log(result.toString(2).padStart(4, "0"));
}

Here is the equivalent in Python:

def generate_ones(num_digits, num_ones):
    if num_digits == 0 or num_ones == 0:
        yield 0
    else:
        for pos in range(num_ones - 1, num_digits):
            for result in generate_ones(pos, num_ones - 1):
                yield (1 << pos) | result

def generate(num_digits):
    for num_ones in range(1, num_digits + 1):
        yield from generate_ones(num_digits, num_ones)

# Demo with n=4:
for result in generate(4):
    print('{0:04b}'.format(result))

Answer 2

n=int(input())
a=[]
for i in range(2**n):
    Str = bin(i).replace('0b','')
    a.append(Str)
for i in range(len(a)):
    a[i] = '0'*(n-len(a[i])) + a[i]
for i in range(len(a)):
    print(a[i])

If you have any doubts related to the code comment down

Answer 3

Supposing “We need to first go through all possible combinations, in such an order that the leftmost bits are lit only after all combinations for the rightmost bits are over” is correct and the example shown for n=4:

7 -> 1001
8 -> 0110

is wrong, then here is C code to iterate through the values as desired:

#include <stdio.h>


//  Print the n-bit binary numeral for x.
static void PrintBinary(int n, unsigned x)
{
    putchar('\t');

    //  Iterate through bit positions from high to low.
    for (int p = n-1; 0 <= p; --p)
        putchar('0' + ((x >> p) & 1));

    putchar('\n');
}


/*  This is from Hacker’s Delight by Henry S. Warren, Jr., 2003,
    Addison-Wesley, Chapter 2 (“Basics”), Section 2-1 “Manipulating Rightmost
    Bits”, page 14.
*/
static unsigned snoob(unsigned x)
{
    /*  Consider some bits in x dddd011...1100...00, where d is “do not care”
        and there are t bits in that trailing group of 1s.  Then, in the code
        below:

            smallest is set to the trailing 1 bit.

            ripple adds to that bit, carrying to the next 0, producing
            dddd100...0000...00.  Note that t 1 bits changed to 0s and one 0
            changed to 1, so ripple has t-1 fewer 1 bits than x does.

            ones is set to all bits that changed, dddd111...1100...0.  It has
            t+1 bits set -- for the t 1s that changed to 0s and the 0 that
            changed to 1.

            ones/smallest aligns those bits to the right, leaving the lowest
            t+1 bits set.  Shifting right two bits leaves t-1 bits set.

            Then ripple | ones restores t-1 1 bits in the low positions,
            resulting in t bits set.
    */
    unsigned smallest = x & -x;        // Find trailing 1 bit.
    unsigned ripple   = x + smallest;  // Change it, carrying to next 0.
    unsigned ones     = x ^ ripple;    // Find all bits that changed.
    ones = ones/smallest >> 2;
    return ripple | ones;
}


/*  Give a number of bits n, iterate through all values of n bits in order
    first by the number of bits set then by the binary value.
*/
static void Iterate(int n)
{
    printf("Patterns for n = %d:\n", n);

    //  Iterate s through the numbers of bits set.
    for (int s = 0; s <= n; ++s)
    {
        /*  Set s low bits.  Note:  If n can equal (or exceed) the number of
            bits in unsigned, "1u << s" is not defined by the C standard, and
            some alternative must be used.
        */
        unsigned i = (1u << s) - 1;

        //  Find the highest value.
        unsigned h = i << n-s;

        PrintBinary(n, i);
        while (i < h)
        {
            i = snoob(i);
            PrintBinary(n, i);
        }
    }
}


int main(void)
{
    for (int n = 1; n <= 4; ++n)
        Iterate(n);
}