N permutations of binary mask with order-CodePudding

I have 'ideal' binary mask, eg: 0000, and I need to get n most similar variations of it. Change of a left bit is more preferable in sense of similarity. So if n == 5, then I will get following variations:

I thought about backtracking algorithm, but how can I maintain order then? What algorithm is the best fit for this?

CodePudding user response：

All you need is this.

binval = 1
base = binval
BITWIDTH = 4

for i in range(5):
    if binval & 1:
        binval = base >> 1 | 1 << (BITWIDTH-1)
        base = binval
    else:
        binval >>= 1
    print(f'{binval:0{BITWIDTH}b}')

Output:

CodePudding user response：

You can take advantage of the fact that itertools.combinations returns the combinations in the definite order that you're looking for.

We can generate combinations of 0, 1, 2 ... 4 positions where the '1' bits have to be, and create your string accordingly.

A generator yielding your masks could be:

def masks(ideal):
    size = len(ideal)
    positions = list(range(size))  # will be for example [0, 1, 2, 3]

    # we start with 0 flipped bit, then one, up to all
    for nb_flipped in range(0, size 1):
        # we get all combinations of positions where to flip that many bits
        for flipped_positions in combinations(positions, r=nb_flipped):
            out = list(ideal)
            # and we flip the bits at these positions
            for pos in flipped_positions:
                out[pos] =  '1' if out[pos] == '0' else '0'
            yield ''.join(out)

And you can use it like this:

for m in masks('0000'):
    print(m)
    
# 0000
# 1000
# 0100
# 0010
# 0001
# 1100
# 1010
# 1001
# 0110
# 0101
# 0011
# 1110
# 1101
# 1011
# 0111 
# 1111

If you want a list of the n first ones, you could use a function like:

def list_of_masks(ideal, n):
    return list(islice(masks(ideal), n))

On your sample ideal mask, this gives:

print(list_of_masks('0101', 6))

# ['0101', '1101', '0001', '0111', '0100', '1001']