Tough Algorithm?
Author
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]
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.
~ 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]
[edited by - rayno on October 13, 2003 12:36:44 AM]
It isn''t as complicated as it sounds.
Observe:
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.
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!
Because if you really want to use your "special" system, the binary operators won''t help!
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]))
Oops, an unfortunate typo!
for num in range(number**2):
This should be
for num in range(2**number):
for num in range(number**2):
This should be
for num in range(2**number):
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
