Python: алгоритм добавления каждого n-го элемента в список с проверкой коллизий

Question

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

Мыпо умолчанию список целых 0 значений .Затем укажите целевую строку « XXX » и шаг вставки, значение 3 в данном случае.

Вот мой код, который в основном работает.

my_list = [0,0,0,0,0,0,0,0,0,0,0,0,0]
target = "XXX"
step = 3

for index, value in enumerate(my_list):
    if value == 0 and index % step == 0:
        my_list[index] = target

print(my_list)

Выходные данные

'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX'

Однако, если что-то уже присутствует в индексе списка, алгоритм должен проверить конфликт и выполнить ту же операцию, начиная со следующего свободного индекса,Вот где я застрял.

Пытался сделать код ниже (изменил my_list, добавил elif).

my_list_changed = ["AAA",0,0,0,0,0,0,0,0,0,0,0,0]
target = "XXX"
step = 3

for index, value in enumerate(my_list_changed):
    if value == 0 and index % step == 0:
        my_list_changed[index] = target
    elif value != 0 and index % step ==0:
        index += 1
        my_list_changed[index] = target

print(my_list_changed)

Вывод

['AAA', 'XXX', 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']

Но это не работает так, как яв розыске.Он добавляет объект в следующий свободный слот, но не сохраняет шаг для остальной части цикла.

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

Буду признателен, если вы сможете улучшить мой код.

Если есть еще несколько способов сделать это, я буду рад их изучить.

Редактировать:Желаемый вывод должен быть как ниже.Параметр step = 3 и в какой-то момент происходит столкновение с «AAA» (индекс 6), поэтому алгоритм запускается со следующего свободного слота (индекс 2), что позволяет ему завершить цикл без столкновений.Выход:

['AAA', 0, 'XXX', 0, 0, 'XXX', 'AAA', 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0] 

Answer 1

В Python, когда вы просматриваете коллекцию с помощью цикла for, вы не можете изменять индекс, который в настоящее время повторяется, как вы сделали с index += 1 (аналогично для каждого цикла в других языках).Чтобы управлять индексами, самый простой способ сделать это - использовать цикл while.

Этот пример позволяет избежать коллизий, пробуя следующий возможный индекс:

my_list_changed = ["AAA",0,0,0,0,0,0,0,0,0,0,0,0]
target = "XXX"
step = 3

index = 0
while index < len(my_list_changed):
    if my_list_changed[index] == 0:
        my_list_changed[index] = target
        index += step
    else:
        index += 1

print(my_list_changed)
# ['AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0]

Редактировать: После дальнейшего объяснения ожидаемого результата кажется, что этот алгоритм должен сначала найти минимальное начальное значениеИндекс, который позволяет обходить список по шагам без каких-либо коллизий.Это можно сделать, сначала попытавшись найти этот действительный start_index, а затем использовать его для изменения значений при обходе списка по шагам.

my_list_changed = ["AAA",0,0,0,"AAA",0,0,0,0,0,0,0,0]
target = 'XXX'
step = 3    

start_index = None
cur_index = 0
# Attempt traversal at each starting index
while cur_index < len(my_list_changed):
    index = cur_index
    # While current attempt hasn't reached end of list
    while index < len(my_list_changed):
        if my_list_changed[index] == 0:
            index += step
        else:
            break  # Stop traversal because invalid
    if index >= len(my_list_changed):
        start_index = cur_index  # Found our valid start_index
        break
    cur_index += 1

# If found a valid path, then change the values
if start_index is not None:
    while start_index < len(my_list_changed):
        my_list_changed[start_index] = target
        start_index += step

print(my_list_changed)
# ['AAA', 0, 'XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0]

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

Answer 2

Дано:

my_list = ['NO!',0,0,0,0,0,0,0,0,0,0,0,0]
target = "XXX"
step = 3

Вы можете использовать назначение среза с троичным :

my_list[::step]=[target if item==0 else item for item in my_list[::step]]
>>> my_list
['NO!', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']

---

Учитывая несколькокомментарии, я думаю вы ищете 1) проверить, если вставка 'XXX' каждые три элемента возможна без столкновения;2) переместитесь на 1 элемент и попробуйте еще раз, если нет.(Теперь вам нужно определить, как далеко вы должны продвинуться, но это другая проблема, чем изначально описанная)

Если я правильно понял, вы все равно можете использовать назначение срезов.Вам просто нужно добавить механизм для проверки и добавить смещение:

def f(my_list, offset=0, step=3):
    while offset<len(my_list):
        if any(item!=0 for item in my_list[offset::step]):
            offset+=1
        else:
            my_list[offset::step]=[target for item in my_list[offset::step]]
            break
    return my_list        

Проверьте это:

for i in range(13):
    l=[0]*13
    l[i]='AAA'
    print '{} => {}'.format(l,f(l[:]))

Отпечатки:

['AAA', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] => ['AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0]
[0, 'AAA', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] => ['XXX', 'AAA', 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']
[0, 0, 'AAA', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] => ['XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']
[0, 0, 0, 'AAA', 0, 0, 0, 0, 0, 0, 0, 0, 0] => [0, 'XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0]
[0, 0, 0, 0, 'AAA', 0, 0, 0, 0, 0, 0, 0, 0] => ['XXX', 0, 0, 'XXX', 'AAA', 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']
[0, 0, 0, 0, 0, 'AAA', 0, 0, 0, 0, 0, 0, 0] => ['XXX', 0, 0, 'XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX', 0, 0, 'XXX']
[0, 0, 0, 0, 0, 0, 'AAA', 0, 0, 0, 0, 0, 0] => [0, 'XXX', 0, 0, 'XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX', 0, 0]
[0, 0, 0, 0, 0, 0, 0, 'AAA', 0, 0, 0, 0, 0] => ['XXX', 0, 0, 'XXX', 0, 0, 'XXX', 'AAA', 0, 'XXX', 0, 0, 'XXX']
[0, 0, 0, 0, 0, 0, 0, 0, 'AAA', 0, 0, 0, 0] => ['XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 'AAA', 'XXX', 0, 0, 'XXX']
[0, 0, 0, 0, 0, 0, 0, 0, 0, 'AAA', 0, 0, 0] => [0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 'AAA', 'XXX', 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 'AAA', 0, 0] => ['XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 'AAA', 0, 'XXX']
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 'AAA', 0] => ['XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 'AAA', 'XXX']
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 'AAA'] => [0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 0, 'XXX', 0, 'AAA']

Answer 3

Вы можете попробовать что-то вроде этого:

idx = 0
while idx < len(my_list):
    if my_list[idx] == 0:
        my_list[idx] = target
        idx += step
    else:
        idx += 1