I am trying to write a knapsack algorithm to generate all possible combinations of four letters (ATGC) and no letter (represented by a space) that's length totals x. This is part of an error correction program for digital data storage I am working on. My current method uses itertools.product, but it generates a massive number of possibilities that takes too long to process. I want to replace this with a knapsack algorithm, but I'm not sure where to start. My current implementation is below.
for error in itertools.product(" ATGC", repeat=errors):
print(error)
errorTest = list(error).remove(' ')
print(errorTest)
if len(errorTest) == constrain:
for ps in error:
for pos in errorPos:
if ps == " ":
fseqL[pos] = ""
else:
fseqL[pos] = ps
ffseq = ""
ffseq = ffseq.join(fseqL)