Sign in to follow this  
helloworld123

How to program all possibility in an array?

Recommended Posts

helloworld123    100
Sorry noob question (started learning programming on my own last week). I am learning C on my own, and want to do this as personal practice, but couldn't figure it out. I wish to have a file and populate it with this: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 (which is all combination that is possible with 0 and 1 as values). how do I go about it? thank you.

Share this post


Link to post
Share on other sites
jyk    2094
I'm assuming this is just an exercise you're doing and not an actual homework problem...

Anyway, here's a hint. What you've shown there are the binary representations of the integers in the range [0, 15]. So, you can generate those patterns by iterating over the integers in that range and using bitmasking to determine, for each, which bits are set to '1' and which bits are set to '0'.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
how to do bitmasking thing?
Google/search for 'c bit masking', 'c bitwise operators', etc.

There are other ways you could generate that sequence as well, such as a loop or set of (possibly implied) nested loops that iterated over all of the permutations.

Share this post


Link to post
Share on other sites
helloworld123    100
hello,

if i use loops within loops, for the sample above, i would need 4 loops right?

what if i need to populate something with 10 consecutive numbers (instead of the 4 numbers above where possible values are 0 and 1), then i need 10 loops? it's not efficient i think?

Share this post


Link to post
Share on other sites
lpcstr    127
Quote:
Original post by jyk
Quote:
how to do bitmasking thing?
Google/search for 'c bit masking', 'c bitwise operators', etc.

There are other ways you could generate that sequence as well, such as a loop or set of (possibly implied) nested loops that iterated over all of the permutations.


Correct me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach? In C++ I think you would define a union that contains an integer and a bit field structure.

Something like:


struct Bitfield
{
bool a : 1;
bool b : 1;
bool c : 1;
bool d : 1;
bool e : 1;
bool f : 1;
bool g : 1;
bool h : 1;
};

union ByteToBits
{
char Byte;
Bitfield Bits;
};


Or at least something to that effect.

Share this post


Link to post
Share on other sites
Zipster    2359
Quote:
Original post by lpcstr
Correct me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach? In C++ I think you would define a union that contains an integer and a bit field structure.

Something like:

<snip>

Or at least something to that effect.

Actually that would still be C. In C++ you'd make heavy use of templates just because you can:

template<size_t N>
class ToBinary {};

template<size_t N>
std::ostream& operator<<(std::ostream& str, const ToBinary<N>&)
{
str << ToBinary<N/2>();
str << (N & 1) ? '1' : '0';
return str;
}

template<>
std::ostream& operator<<(std::ostream& str, const ToBinary<0>&)
{
return str;
}

template<size_t N>
class RangeToBinary {};

template<size_t N>
std::ostream& operator<<(std::ostream& str, const RangeToBinary<N>&)
{
str << RangeToBinary<N-1>();
str << ToBinary<N>() << std::endl;
return str;
}

template<>
std::ostream& operator<<(std::ostream& str, const RangeToBinary<0>&)
{
return str;
}

int main()
{
std::cout << RangeToBinary<500>();
}

Note: The larger your range, the angrier your compiler gets as it has to expand all the templates :) You could also modify the code a bit to add zero padding but meh.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by lpcstr
Correct me if I'm wrong, but wouldn't bit masking with logical operators be more of a C approach?
Quote:
Original post by helloworld123
I am learning C on my own...
Emphasis added, of course :)

Anyway, the bitmasking approach is just one way of doing what the OP asked; it's not necessarily the 'best' or most elegant way. (Personally, I'd probably use a loop, which I also suggested.)

Share this post


Link to post
Share on other sites
alvaro    21246
You can also use backtracking, which is a mechanism that can be adapted for many other enumeration problems.

#include <stdio.h>

int array[4];

void backtrace(int n) {
if (n==4) {
for (int i=0; i<4; ++i)
printf("%d",array[i]);
printf("\n");
}
else {
for (array[n]=0; array[n]<2; ++array[n])
backtrace(n+1);
}
}

int main() {
backtrace(0);
}

Share this post


Link to post
Share on other sites
BrianLarsen    100
alternatively,....

the feilds are 8,4,2,1 in value


char MyString[4];
int MyValue
int WorkingValue

for (MyValue = 0 ; MyValue < 16 ; MyValue++)
{
WorkingValue = MyValue;
if (WorkingValue > 8)
{
MyString[0] = "1";
WorkingValue = WorkingValue - 8;
}else {
MyString[0] = "0" ;
}

// handle remaining fields


MyString[4] = 0; // Null terminate!

// String ready for printing or saving to file....

}

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by helloworld123
hello,

if i use loops within loops, for the sample above, i would need 4 loops right?

what if i need to populate something with 10 consecutive numbers (instead of the 4 numbers above where possible values are 0 and 1), then i need 10 loops? it's not efficient i think?


There's no reason to nest loops for each bit.

Instead, have one loop which loops over the numbers and figure out which bits are set for each number (using a second loop for each bit-position).

Share this post


Link to post
Share on other sites
DevFred    840
You can also treat the number as a string and do the increment yourself. Simply start on the right and flip the first bit. If it flips to 0, continue with the left neighbor. If you cross the left end, you have enumerated all possibilities.

#include <stdio.h>

void generate_four()
{
char array[] = {0, '0', '0', '0', '0', 0}, *p;
do
{
puts(array + 1);
for (p = array + 4; *p && (*p ^= 1) == '0'; --p)
{}
} while (*p);
}

If the length isn't known until runtime, the array allocation and initialization is a little more complicated:

#include <stdlib.h>
#include <string.h>

void generate(size_t length)
{
char *array, *p;
array = malloc(length + 2);
if (!array) return;

array[0] = 0;
memset(array + 1, '0', length);
array[length + 1] = 0;

do
{
puts(array + 1);
for (p = array + length; *p && (*p ^= 1) == '0'; --p)
{}
} while (*p);

free(array);
}

Share this post


Link to post
Share on other sites
DevFred    840
By the way, functional languages are made for these kinds of problems:

poss 0 = [""]

poss n = map ('0':) rest ++ map ('1':) rest where rest = poss (n-1)

> poss 4
["0000","0001","0010","0011","0100","0101","0110","0111",
"1000","1001","1010","1011","1100","1101","1110","1111"]

Share this post


Link to post
Share on other sites
Zahlman    1682
Indeed. That might look more familiar to some people spelled in Python:


def poss(n):
if n == 0: return ['']
rest = poss(n - 1)
return ['0' + x for x in rest] + ['1' + x for x in rest]

Share this post


Link to post
Share on other sites
taz0010    277
You can use cout to output in binary, but this is pretty much cheating. There's a simple algorithm for converting to binary that goes like this:

Divide the number by 2. If there's a remainder, output 1. If no remainder, output 0
Throw away fractional part and repeat process until the number equals 0

This gives the binary value, but in reverse order. If you output to a string, you can just call std::reverse to put it in the right order.

To come up with the "best" method, you can take advantage of the fact that checking if an integer is divisible by 2 is very fast. Just bitwise AND with the value 1, where a result of zero indicates no remainder. You can divide the number by 2 and discard the remainder simply by bit shifting, but if you use an actual division, the compiler will optimise with the faster bit shift operation automatically.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this