Pythonic способ удалить элемент списка, который является «подсписком» другого

Question

У меня есть этот метод, который получает все действительные ходы с шашечной доски.

def get_all_moves(self) -> list:
    moves = []
    pieces = self.__get_all_turn_pieces()

    for p in pieces:
        self.__jump_moves(p.coord, moves)
        self.__b.wipe()
        self.__simple_moves(p, moves)

    moves.sort(key=len, reverse=True)
    for i in range(len(moves)):
        for j in range(len(moves)):
            if moves[i][:len(moves[j])] == moves[j] and len(moves[i]) > len(moves[j]):
                moves.remove(moves[j])
    return moves

Проблема в том, что по правилам шашек игрок должен выполнить наибольшее количество захватов за ход.Поэтому мне нужно удалить неверные ходы.

Позволяет проанализировать этот вывод:

[[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

Первый и второй элементы списка вывода содержат, соответственно, два последних.Поэтому мне нужно удалить их, потому что они являются «подсписком» первых.

Проблема в том, что мой вложенный цикл не может решить эту проблему.Программа выдает эту ошибку:

Traceback (most recent call last):
  File "damas.py", line 435, in <module>
    print(m.get_all_moves())
  File "damas.py", line 418, in get_all_moves
    if moves[i][:len(moves[j])] == moves[j] and len(moves[i]) > len(moves[j]):
IndexError: list index out of range

Через некоторое время мне интересно, какой самый питонический способ решить эту проблему.

Answer 1

Я не знаю, является ли это наиболее питоническим способом выполнения вещей, но это вариант того, что я использовал для проверки подстрок, что довольно лаконично:

def check_for_sublist(sub_list,longer_list): 
    return any(sub_list == longer_list[offset:offset+len(sub_list)] for offset in range(len(longer_list)))

Или лямбда-версия, который мне посоветовали не использовать в комментариях.Оставьте это здесь как инструмент обучения, когда я узнал кое-что из комментария!

x_sublist_y = lambda x, y: any(x == y[offset:offset+len(x)] for offset in range(len(y)))

И тогда я думаю, что это поможет.Он создает список записей, для которых arraycheck не возвращает значение True (исключая проверку условий относительно себя).

moves = [[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

filtered_moves = [move1 for move1 in moves if all([not check_for_sublist(move1, move2) for move2 in moves if move1 != move2])]

Answer 2

Вот решение, использующее понимание списка, которое часто является полезным подходом, когда вы хотите сделать вещи как можно более Pythonic

def is_sublist( seq, lists ):
    for candidate in lists:
        if len( candidate ) > len( seq ) and candidate[ :len( seq ) ] == seq:
            return True
    return False

moves = [[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

# here comes the list comprehension:
pruned = [ eachMove for eachMove in moves if not is_sublist( eachMove, moves ) ]

Чтобы изменить последовательность moves на месте, вы должны назначитьна moves[:] вместо новой переменной pruned.

Однако приведенное выше решение не является наиболее эффективным, что может быть проблемой, если число потенциальных ходов велико.Подход менее элегантно выглядящий, как, например, следующий, может быть целесообразным, потому что, поскольку ходы кандидатов отклоняются, мы уменьшаем количество потенциальных суперсписков, по которым должен проверяться каждый будущий потенциальный подсписок:

accepted = []
while moves:
    eachMove = moves.pop( 0 )
    if not is_sublist( eachMove, moves ) and not is_sublist( eachMove, accepted ):
        accepted.append( eachMove )

moves[:] = accepted

Если упорядочениеиз списка ходов не важно, выполнение moves.sort() в верхней части этой подпрограммы сделает ее более эффективной (на самом деле, тогда мы могли бы оптимизировать код еще дальше, потому что каждое движение только когда-либо должно сравниваться с следующий переместиться в списке).

Answer 3

Как вы, возможно, уже поняли, проблема в том, что вы проверяете длину moves для i только один раз в начале.Когда вы удаляете из него элементы, вы сокращаете его, в результате чего переменная цикла i в конечном итоге выходит за пределы размера списка.

Существует множество способов исправить это.Мой обычный подход для такой ситуации, когда вам нужно оценить каждый элемент в списке для удаления, - это начать с конца списка и вернуться к началу.

for i in reversed(range(len(moves))):
    for j in range(len(moves)):
        if i != j and moves[i] == moves[j][:len(moves[i])]:
            del moves[i]
            break

Обратите внимание, что я оцениваю moves[i] на удаление, а не moves[j].Если я обнаружил, что хочу удалить его, я делаю это, а затем немедленно вырываюсь из внутреннего цикла for.Это повлияет только на структуру списка в и после позиция i (элементы, которые мы уже рассмотрели и решили сохранить), но не ранее (элементы, которые мы еще должны рассмотреть).Поэтому мы не будем сталкиваться с какими-либо противными ошибками IndexErrors.