验证数组上的移动位置是否有效

Question

谁能帮帮我？

我需要实现一个例程来测试数组是否可以移动位置字段请看图

规则是：

类型F字段可以在任意位置
类型 X 的字段不能在开始和结束字段之间
并且在Start和End之间，不能包含另一个start-end

我希望你给我一些关于如何实现这个算法的想法。如果需要示例代码，它可以是任何语言...

坦克！

Answer 1

这个想法很简单。我会创建一个索引范围数组来编码 (Start,End) 位置。我假设输入是遵循位置相关规则的有效形式。

InputArray: [X1, F1, Start, F2, F3, End, F6, X2, Start, F4, End]
Encoding: [(2,5), (8,10)]

现在可以查询上面的编码是否允许移动

function query(currentPosition, targetPosition, Encoding):

    type = type of InputArray[currentPosition]

    if type == F:
        return True if targetPosition in bounds of InputArray

    if type == X:
        return True if binary search of the targetPosition doesn't overlap with any range in Encoding        
        
        #e.g. if targetPosition is 3 for above Encoding, then it overlaps with range (2,5). 

    if type == Start:
        index = Binary search for currentPosition in Encoding
        return targetPosition <= currentPosition and (index == 0 or targetPosition > Encoding[index-1].second)
        
        #e.g. if query(8, 6, Encoding) returns True
        #    index => 1
        #    Encoding[index-1].second => 5

    if type == End:
        index = Binary search for currentPosition in Encoding
        return targetPosition >= currentPosition and (index == len(Encoding)-1 or targetPosition < Encoding[index+1].first)

        #e.g. if query(5, 6, Encoding) returns True
        #    index => 0
        #    Encoding[index+1].first => 8

    return False

每个查询的时间复杂度：O(log(n))。所以，我认为这是最有效的解决方案。

Answer 2

这里有两个提议的算法，在 python 中实现。我通过假设您交换两个元素而不是移动一个元素来改变规则。这是因为在 python 中交换元素很容易，但是插入和删除元素（有效地移动整个数组的一部分）真的很烦人。

# DUMMY FUNCTIONS TO CHECK TYPE, REPLACE WITH YOUR OWN
def is_x(e):
    return e.startswith('x')

def is_f(e):
    return e.startswith('f')

def is_start(e):
    return e.startswith('s')

def is_end(e):
    return e.startswith('e')

# CHECK THE ARRAY RESPECTS RULES 2,3: NO TWO CONSECUTIVE STARTS OR ENDS
#                                     NO X IN BETWEEN START-END
def is_valid_array(a):
    state = 'end'
    for e in a:
        if ((is_start(state) and (is_start(e) or is_x(e))) or
            (is_end(state) and is_end(e))):
            return False
        elif is_start(e):
            state = 'start'
        elif is_end(e):
            state = 'end'
    return is_end(state)

# FIRST ALGORITHM
# straightforward, easy to debug
# time complexity always proportional to array size
def is_valid_move_firstalgorithm(a, i, j):
    a[i], a[j] = a[j], a[i]      # perform move
    is_valid = is_valid_array(a) # check whole array
    a[j], a[i] = a[i], a[j]      # undo move
    return is_valid

# check if position i is inbetween start-end
def follows_start(a, i):
    for k in range(i-1, -1, -1):
        if is_start(a[k]):
            return True
        elif is_end(a[k]):
            return False
    return False

# SECOND ALGORITHM
# messy, could easily have forgotten an edge case
# time complexity sometimes much smaller than array size
# worst-case time complexity proportional to array size
def is_valid_move_secondalgorithm(a, i, j):
    i, j = min(i, j), max(i, j)  # reorder i,j if j<i
    for is_type in (is_x, is_f, is_start, is_end):
        if is_type(a[i]) and is_type(a[j]):
            return True
    if is_x(a[i]) and not is_x(a[j]) and (is_start(a[j]) or follows_start(a, j) or follows_start(a, i)):
        return False
    elif is_x(a[j]) and not is_x(a[i]) and (is_end(a[i])   or follows_start(a, j) or follows_start(a, i)):
        return False
    elif is_start(a[i]) and is_end(a[j]) or is_end(a[i]) and is_start(a[j]):
        return False
    for k in (i, j):
        if is_start(a[k]) and any(is_end(e) or is_x(e) for e in a[i+1:j]):
            return False
        elif is_end(a[k]) and any(is_start(e) or is_x(e) for e in a[i+1:j]):
            return False
    return True

测试：

from itertools import combinations

arr = ['x1', 'f1', 's', 'f2', 'f3', 'e', 'f6', 'x2', 's', 'f4', 'e']

for i, j in combinations(range(len(arr)), 2):
    b1 = is_valid_move_firstalgorithm(arr, i, j)
    b2 = is_valid_move_secondalgorithm(arr, i, j)
    if b1 == b2:
        print('# {:2} {:2d} {:5s}'.format(i, j, str(b1)))
    else:
        print('# {:2} {:2d} {:5s} {:5s}  DISAGREE'.format(i, j, str(b1), str(b2)))
#  0  1 True 
#  0  2 False
#  0  3 False
#  0  4 False
#  0  5 False
#  0  6 True 
#  0  7 True 
#  0  8 False
#  0  9 False
#  0 10 False
#  1  2 True 
#  1  3 True 
#  1  4 True 
#  1  5 False
#  1  6 True 
#  1  7 True 
#  1  8 False
#  1  9 True 
#  1 10 False
#  2  3 True 
#  2  4 True 
#  2  5 False
#  2  6 False
#  2  7 False
#  2  8 True 
#  2  9 False
#  2 10 False
#  3  4 True 
#  3  5 True 
#  3  6 True 
#  3  7 False
#  3  8 False
#  3  9 True 
#  3 10 False
#  4  5 True 
#  4  6 True 
#  4  7 False
#  4  8 False
#  4  9 True 
#  4 10 False
#  5  6 True 
#  5  7 False
#  5  8 False
#  5  9 False
#  5 10 True 
#  6  7 True 
#  6  8 False
#  6  9 True 
#  6 10 False
#  7  8 False
#  7  9 False
#  7 10 False
#  8  9 True 
#  8 10 False
#  9 10 True

验证数组上的移动位置是否有效

verifying if a move position on an array is valid

arrays

algorithm

insert

move