Archived

This topic is now archived and is closed to further replies.

Tough Algorithm?

This topic is 5171 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For some reason, I can't think of a way to do this. Say I have some numbers: (not necessarily in order) 0 1 2 3 4 and I want to find all the bit sequences that add up to a certain #. For example, if that # is 6. I would get the bit combitions: 11110 01110 10101 00101 .. this means that, for the bit combinations 11110, the numbers: 0 1 2 3 .. all add up to 6. For the bit combo 10101: 0 2 4 ... all add up to 6. Etc. How could I do this? I don't know if I explained this clearly, but thanks for any help you can give. [edited by - Gf11speed on October 13, 2003 12:01:17 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
go learn what the bitwise operators (&, |, and ~) do. this is not a difficult problem.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
go learn what the bitwise operators (&, |, and ~) do. this is not a difficult problem.


Do you mean ^ instead of ~? I have never heard of a ~ operator before.

Share this post


Link to post
Share on other sites
~ is the bitwise NOT operator. It gives you the opposite of a binary number. For example, the bitwise NOT of 100101 would be 011010.

[edited by - rayno on October 13, 2003 12:36:44 AM]

Share this post


Link to post
Share on other sites
It isn''t as complicated as it sounds.

Observe:

...
unsigned short SomeVar = 5; //0000000000000101 in binary

SomeVar = ~SomeVar; //SomeVar now equals 1111111111111010 in binary because ~ just flips all the bits.

//That is 65530 in decimal numbers, by the way.

Share this post


Link to post
Share on other sites
do you want to get the bits of the binary system or of the "special" system you have used within you examples???

Because if you really want to use your "special" system, the binary operators won''t help!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Here''s a solution in Python.. Unless you know Python, it may not be all that helpful - sorry. It prints result for the example input you gave like this:


>>> sumCombinations(range(5))[6]
[[1, 2, 3], [0, 1, 2, 3], [2, 4], [0, 2, 4]]


----


def rangeSubsets(number):
"""Generator that yields all subsets for range(number).

>>> list(combinations(3))
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3]]
"""
for num in range(number**2):
i = 0
bits = []
while num:
if num & 1:
bits.append(i)
num >>= 1
i += 1
yield bits


def fillDict(seq, keyFn=lambda x:x, valueFn=lambda x:x):
"""Return a dictionary in which each key maps to a sequence of values.

Arguments:
seq -- input sequence
keyFn -- Transforms sequence values into key values. Default = no-op
valueFn -- Transformas sequence values into real values. Default = no-op
"""
res = {}
for x in seq:
res.setdefault(keyFn(x), []).append(valueFn(x))
return res


def sumCombinations(numbers):
return fillDict(rangeSubsets(len(numbers)),
keyFn=lambda comb: sum([numbers[x] for x in comb]))

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oops, an unfortunate typo!

for num in range(number**2):

This should be

for num in range(2**number):

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
<Code>


int bitSeqTotal(int bitSeq)
{
int counter;
int total = 0;
for(counter = 0;counter < 8;counter++)
{
total += ((1 << counter) & bitSeq) ? counter : 0;
}
return total;
}

void fillBitSeqString(char *buf,int num)
{
for(int counter = 7;counter >= 0;counter--)
*(buf++) = ((1 << counter) & num) ? ''1'':''0'';
}

int _tmain()
{

int check = 0;
int num = 6;
char buf[20];

for(check = 0;check < 256;check++)
{
if(bitSeqTotal(check) == num)
{
fillBitSeqString(buf,check);
printf("%s\n",buf);
}
}

return 0;
}

</Code>

Share this post


Link to post
Share on other sites