Get all combinations of a binary string with bit flips at specific indices (Python)-CodePudding

I have a binary string. I have a list of bit indices to flip. How can I generate all possible combinations of binary strings with flips at those specific indices? The output list should contain 2^n unique elements where n is the length of the indices list. I believe itertools.product() could be used here, but I can't figure out how to line up all the parameters, especially since the length of the indices list is variable.

Example:

binaryString = "0000000000"
indicesToFlip = [0,1,9]

outputCombinations = magic()

print(outputCombinations)

["0000000000",
 "1000000000",
 "0100000000",
 "1100000000",
 "0000000001",
 "0100000001",
 "1000000001",
 "1100000001"]

CodePudding user response：

You could iterate all binary representations with the number of binary digits that corresponds to the number of indices (like 000, 001, 010, 011, ...) and then use a regular expression replacement that injects those digits in the larger binary string.

import re
    
def combis(binaryString, indicesToFlip):
    # Prepare the regex...
    n = len(indicesToFlip)
    regex = re.compile("(.)" * n)
    # ... and the replacement pattern
    mask = list(binaryString)
    for i, idx in enumerate(indicesToFlip):
        mask[idx] = rf"\g<{i 1}>"
    replacer = "".join(mask)
    # Apply that transformation to each number in the range [0..2^n)
    return [regex.sub(replacer, f"{num:>0{n}b}") for num in range(1 << n)]

binaryString = "0000000000"
indicesToFlip = [0,1,9]
print(combis(binaryString, indicesToFlip))

CodePudding user response：

Try:

from itertools import combinations

binaryString = "0000000000"
indicesToFlip = [0, 1, 9]

out = []
for i in range(len(indicesToFlip)   1):
    for c in combinations(indicesToFlip, i):
        out.append(
            "".join(
                ("1" if ch == "0" else "0") if i in c else ch
                for i, ch in enumerate(binaryString)
            )
        )

print(*out, sep="\n")

Prints:

CodePudding user response：

There's answer that cycles through the all combinations of indices to toggle using itertools but here's a recursive implementation of your magic() function.

def magic(S, indices):
    L = list(S) # convert to list of binary characters for mutation
    def recurse(L, indices, curr):
        if curr == len(indices): # done
            return [''.join(L)]  # return as list in order to accumulate results
            
        res = recurse(L, indices, curr   1)          # do not flip
        og = L[indices[curr]]
        L[indices[curr]] = '1' if og == '0' else '0' # change
        res  = recurse(L, indices, curr   1)         # re-run, effectively doing a flip
        L[indices[curr]] = og                        # revert
        return res
        
    return recurse(L, list(reversed(indices)), 0)    # reversed input indices to get desired order
    
for elm in magic("0" * 10, [0, 1, 9]): # your test case
    print(elm)

Prints: