N种有序二进制掩码排列-解网

问：

我有“理想”的二进制掩码，例如：，我需要获得它最相似的变体。在相似性意义上，更改左位更可取。因此，如果 n == 5，那么我将得到以下变体：0000n

我想过回溯算法，但是我该如何维持秩序呢？哪种算法最适合此情况？

Python 算法与语言无关

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)

你可以像这样使用它：

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

如果你想要第一个列表，你可以使用如下函数：n

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

在您的样品理想面膜上，这给出了：

print(list_of_masks('0101', 6))

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

N种有序二进制掩码排列

N permutations of binary mask with order

评论

评论