程序员的算法趣题Q48: 翻转得到交错排列

目录

1. 问题描述

2. 解题分析

2.1 圆圈排列的表示

2.2 翻转运算

 2.3 算法流程

3. 代码及测试

4. 后记


1. 问题描述

程序员的算法趣题Q48: 翻转得到交错排列_第1张图片

2. 解题分析

        本题关键在于围成一圈的排列以及翻转运算如何表示。

2.1 圆圈排列的表示

        从某处剪开形成线性排列是常用套路。具体从哪里剪开看处理方便。

     由于初始位置是黑白各连续N个,用1表示黑,0表示白。标示2*N个位置分别为pos0,pos1,...,pos(2N-1)。令初始状态中,pos0~pos(N-1)为1(即黑色卡片),posN~pos(2N-1)为0(即白色卡片)。

        从pos0和pos(2N-1)中间剪开,这个排列可以用一个2N比特的无符号整数{pos(2N-1}, pos(2N-2}, ... , pos0}表示,约定pos0为LSB,pos(2N-1}为MSB。

        由此可得:

        初始状态为0b000...0111...1 = 2**N-1

        终止状态(黑白或01交错)有两种,分别是:0b1010...10, 0b010...101

2.2 翻转运算

        在圆圈上翻转连续3张牌,可以用一个2*N比特的有3个比特为1的整数(称为掩码)与表示排列状态的整数进行按比特异或运算得到。

        在每个状态下,“翻转连续3张牌”的可能位置有2*N种,对应的整数为7, 14, ...。但是要注意翻转位置跨越剪开的那个位置时的处理。比特数比较少的时候,用手动计算出掩码也是可以的。也可以找出规律用代码来实现(这样代码可扩展性更好)。本题解中用以下方式来求2*N种掩码:

        (7<

 2.3 算法流程

        基于以上讨论,这个问题就转化成了图搜索问题中的最短路径问题了,可以用广度优先搜索来解决。

        算法流程如下:

程序员的算法趣题Q48: 翻转得到交错排列_第2张图片

  

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Fri Oct  8 07:40:08 2021

@author: chenxy
"""

# import sys
import time
# import datetime
# import math
# import random
# from   typing import List
# from   queue import Queue
from   collections import deque
# import itertools as it
# import numpy as np

N       = 8
target1 = 0b1010_1010_1010_1010
target2 = 0b0101_0101_0101_0101
start   = 0b0000_0000_1111_1111

mask    = 2*N*[0]
for k in range(2*N):
    mask[k] = (7 << k) // (2**16) + (7 << k) % (2**16)

step    = 0
q       = deque()
visited = set()

q.append((start,step))
visited.add(start)

while len(q) > 0:
    cur,step = q.popleft()
    # print('cur={0}, step={1}'.format(cur,step))
    if cur == target1 or cur == target2:
        break
    for k in range(2*N):
        nxt = cur ^ mask[k]
        if nxt not in visited:
            # print('\t{0}-->{1}'.format(cur,nxt))
            q.append((nxt,step+1))
            visited.add(nxt)

print('N = {0}, step = {1}'.format(N,step))

4. 后记

        长假归来。。。Q48轻松搞定。呃,那一定是我的水平涨了嘛^-^老兵不死他只是慢慢凋零。。。

        上一篇:程序员的算法趣题Q47: 格雷码循环

        

        本系列总目录参见:程序员的算法趣题:详细分析和Python全解

你可能感兴趣的