Can I generate all possible binary strings with specified number of bit flips in python-CodePudding

I'm trying to write a program, where the input is a binary string with arbitrary length, as well as the number of bit flips desired, and the output is all the possible strings with the specified number of bit flips (in a list). For example, if the input is '110' and 2, the output is ['000','101','011']. I'm new to python and didn't find any similar programs. I really have no idea how I can do that. Could anyone give me some hints? Many thanks for the help!!

CodePudding user response：

Integer xor version of Ice Griffin's answer.

from itertools import combinations
 
input_bits = '110'
flip_count = 2
# get all available single bit flips
flips = [1 << i for i in range(len(input_bits))]
combs = combinations(flips, flip_count)
 
# flip given bit string
def flip(bit_str, comb):
    n = int(bit_str, 2) ^ sum(comb)
    return f'{n:0{len(bit_str)}b}'

# implement combination
for comb in list(combs):
    flipped = flip(input_bits, comb)
    print(flipped)

CodePudding user response：

You can use a combination algorithm to generate all possible cases.

from itertools import combinations
 
input_bits = '110'
flip_count = 2
# get all available flip positions
flip_positions = [_ for _ in range(len(input_bits))]
combs = combinations(flip_positions, flip_count)
 
# flip given bit string
def flip(bit_str, comb):
    bit_arr = [_ for _ in bit_str]
    for i in comb:
        if bit_arr[i] == '0':
            bit_arr[i] = '1'
        else:
            bit_arr[i] = '0'
    return ''.join(bit_arr)

# implement combination
for comb in list(combs):
    flipped = flip(input_bits, comb)
    print(flipped)

CodePudding user response：

You can iterate directly on all possible 2**n numbers and find what you are looking for without using any library functions.

s, k = map(str,input().split())
k = int(k)
n = len(s)
ans = []
for i in range(2**n):
    num = bin(i)[2:]
    num = "0" * (n - len(num))   num
    if(num.count("1") == k):
        # Flip s at on positions of num
        res = ""
        for j in range(n):
            if(num[j] == "1"):
                res  = str(1 - int(s[j]))
            else:
                res  = s[j]
        ans.append(res)
print(*ans)