C : 0 & 1 combinations using recursion

Question

I want to list combinations of o & 1 recursively using c depending on variables number (number)

the output I want is

000
001
010
011
100
101
110
111

I've tried many algorithms the last one is :

void permute(unsigned number)    {

    if(number == 0) {
        printf("\n");
        return;
    }

    permute(number - 1);
        printf("0");
    permute(number - 1);
        printf("1");


}   //permute ends here


void permuteN(unsigned number) {

    unsigned i;

    for(i = 0; i < number + 1; i++){
        permute(i);
    }
}   //permuteN ends here

I think it gives me the answer but not ordered because I don't know where to put \n;

need your help!

Answer 1

If you are indeed just looking for combinations of 1's and 0's I'd suggest you just count up the numbers and list them in binary.

Take the numerals 0...7 in binary and taking only the last 3 bits (apply mask maybe), and you end up with the same set you specified:

000
001
...
...
111

For n-digit combinations, you need to do 0..2^n - 1

---

Based off this answer, for one specific case of 3-bits (Credit to @ChrisLutz and @dirkgently)

#include <stdio.h>
int main(){
int numdigits = 3, j;
    for(j=1; j<8; j++)
        printbits(j);
}

void printbits(unsigned char v) {
  int i;
  for(i = 2; i >= 0; i--) putchar('0' + ((v >> i) & 1));
  printf("\n");
}

Output:

000
001
010
011
100
101
110
111

Answer 2

All you are actually doing is converting a number to binary.... A simple loop does this without any library calls (aside from printf)...

const unsigned int numbits = 3;
unsigned int bit;

for( bit = 1U << (numbits-1); bit != 0; bit >>= 1 ) {
    printf( number&bit ? "1" : "0" );
}
printf( "\n" );

---

Edited, since you seem to want recursion. You need to have some way to specify how many bits you require. You need to pass this into your recursive routine:

#include <stdio.h>

void permute(unsigned number, unsigned bits)
{
    if( bits == 0 ) return;
    permute(number / 2, bits-1);
    printf( "%d", number % 2 );
}   //permute ends here


void permuteN(unsigned number, unsigned bits ) {

    unsigned i;

    for(i = 0; i < number + 1; i++){
        permute(i, bits);
        printf("\n");
    }
}   //permuteN ends here

int main(void)
{
    permuteN(7, 3);
    return 0;   
}

To get the output in the order you require, you can't know when to write the newline. So in this case, you write it afterwards.

Answer 3

@paddy has a nice answer; only adding a bit (as of my toughs by your reply on my comment - was a bit late to the game). This rely on pow() , (and log10 for some nicety in print), tho so; if using gcc compile with -lm:

basemight be a bit confusing here - but guess you get the meaning.

gcc -Wall -Wextra -pedantic -o combo combo.c -lm

/* gcc - Wall -Wextra -pedantic  -o combo combo.c -lm */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static void prnt_combo(unsigned number, unsigned bits, int base)
{
    if (!bits)
        return;
    prnt_combo(number / base, --bits, base);
    printf("%d", number % base);
}


void prnt_combos(int bits, int base)
{
    int i;
    int n = pow(base, bits);
    int wp = log10(n) + 1;

    fprintf(stderr,
        "Printing all combinations of 0 to %d by width of %d numbers. "
        "Total %d.\n",
        base - 1, bits, n
    );

    for (i = 0; i < n; i++) {
        fprintf(stderr, "%*d : ", wp, i);
        prnt_combo(i, bits, base);
        printf("\n");
    }
}


/* Usage: ./combo [<bits> [<base>]]
 *        Defaults to ./combo 3 2
 * */
int main(int argc, char *argv[])
{
    int bits = argc > 1 ? strtol(argv[1], NULL, 10) : 3;
    int base = argc > 2 ? strtol(argv[2], NULL, 10) : 2;

    prnt_combos(bits, base);
    return 0;
}

Sample:

$ ./combo 4 2
Printing all combinations of 0 to 1 by width of 4 numbers. Total 16.
 0 : 0000
 1 : 0001
 2 : 0010
 3 : 0011
 4 : 0100
 5 : 0101
 6 : 0110
 7 : 0111
 8 : 1000
 9 : 1001
10 : 1010
11 : 1011
12 : 1100
13 : 1101
14 : 1110
15 : 1111

Or clean output:

$ ./combo 3 2 >&2-
000
001
010
011
100
101
110
111

You might like to add something like:

if (base > 10)
    printf("%x", number % base);
else
    printf("%d", number % base);

in prnt_combo(). This way you get i.e. by 2 16:

    0 : 00
    1 : 01
    2 : 02
    3 : 03
    4 : 04
  ...
  250 : fa
  251 : fb
  252 : fc
  253 : fd
  254 : fe
  255 : ff