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.

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 on other sites
go learn what the bitwise operators (&, |, and ~) do. this is not a difficult problem.

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 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 on other sites
I''m not all that advanced now

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

Observe:
...unsigned short SomeVar = 5; //0000000000000101 in binarySomeVar = ~SomeVar; //SomeVar now equals 1111111111111010 in binary because ~ just flips all the bits.//That is 65530 in decimal numbers, by the way.

Share on other sites
Does it have to be fast? And how big is the list of numbers?

- Josh

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 on other sites
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 bitsdef 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 resdef sumCombinations(numbers):    return fillDict(rangeSubsets(len(numbers)),                    keyFn=lambda comb: sum([numbers[x] for x in comb]))

Share on other sites
Oops, an unfortunate typo!

for num in range(number**2):

This should be

for num in range(2**number):

Share on other sites
<Code>

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

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>

• Forum Statistics

• Total Topics
628675
• Total Posts
2984169

• 13
• 12
• 9
• 10
• 9