Перемещение подсписка элементов в списке на новую позицию

Question

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

Проблема

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

moveitem(from_index, to_index)

, который для списка lst концептуально эквивалентен Python:

lst.insert(to_index, lst.pop(from_index))

Задача состоит в том, чтобы написать функцию

moveitems(from_indices, to_index)

который, учитывая:

• from_indices - список индексов элементов, а
• to_index - целевой индекс

генерирует последовательность moveitem (from_index, to_index) инструкций, которые перемещают элементы с указанными индексами на целевую позицию в списке, сохраняя порядок, в котором индексы перечислены в from_indices .

Если удаленный список равен lst , то суммарный эффект вызова moveitems (from_indices, to_index) должен быть эквивалентным следующему Pythonвыражение ( expr1 ):

[x for x in lst[:to_index] if x not in from_indices] +
from_indices +
[x for x in lst[to_index:] if x not in from_indices]

или датьВ следующем определении разности списков:

diff = lambda l1, l2: [x for x in l1 if x not in l2]

желаемый результат равен ( expr2 ):

diff(lst[:to_index], from_indices) +
from_indices +
diff(lst[to_index:], from_indices)

Таким образом, если удаленный список содержал элементы:

[0,1,2,3,4,5,6,7,8,9,10,11,12, ... ]

вызов к элементам движения ([8, 2, 7, 4, 0], 6) должен преобразовать его в:

[1, 3, 5, 8, 2, 7, 4, 0, 6, 9, 10, 11, 12, ... ]

со следующим- или эквивалентная - последовательность инструкций перемещения:

moveitem(0,5)
moveitem(3,4)
moveitem(7,4)
moveitem(1,3)
moveitem(8,3)

Обратите внимание, что в приведенном выше примере элементы перемещаются в обратном порядке, они отображаются в списке индексов ( from_indices ). Это приемлемо, если в преобразованном списке сохраняется порядок, в котором элементы перечислены в from_indices .

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

Сортировочное решение

В настоящее время используемое мной решение выглядит следующим образом (в Python):

def moveitems(from_indices, to_index):

    lst_len = max(from_indices + [to_index])+1
    lst = list(range(lst_len))

    last = to_index
    for item in from_indices[::-1]:
        source = lst.index(item)
        dest = lst.index(last)
        if dest > source: dest -= 1
        lst.insert(dest, lst.pop(source))
        last = item
        moveitem(source, dest)

Он начинается с составления списка индексов lst = [0,1,2,3,4, ...] . Мы не имеем представления о длине удаленного списка, но он должен быть не меньше максимального индекса, указанного в списке from_indices , и индекса to_index .

Затем мы перебираем элементы, которые нужно переместить ( from_indices ) - каждый раз item - это элемент, который нужно переместить, а last - это ранее перемещенныйпредмет. Идея состоит в том, чтобы вытолкнуть элемент из любого места в списке и вставить его рядом с последним перемещенным элементом. Поскольку вставка списка в Python вставляет элементы ДО элемента, который в данный момент находится в точке вставки, мы перебираем from_indices в обратном порядке. Мы ищем item и last в списке lst , чтобы получить их позиции source и dest , а затемизвлеките элемент из позиции source и вставьте его перед ранее перемещенным элементом в позиции dest . Небольшая коррекция необходима, когда адресат выше источника, чтобы компенсировать смещение адресата вниз на 1, когда source выталкивается.

Это решение работает - в том смысле, что оно производитсписок, эквивалентный списку, созданному ( expr1 ) и ( expr2 ) выше, но имеет 3 основных проблемы:

• Это ужасно;
• это безобразно;и
• нецелесообразно для больших индексов.

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

moveitems([56, 12, 19], 1000000)

Задача

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

Context

Элементы представляют документы на удаленном сервере. Пользователи могут просматривать список, выбирать случайный подсписок документов, а затем перетаскивать их на новую позицию в списке. Затем клиент должен отправить на сервер последовательность инструкций moveitem , чтобы соответствующим образом изменить порядок списка. Документы должны сохранять порядок, в котором они были выбраны (НЕ их первоначальный порядок).

Answer 1

Рассмотрим I предмет для перемещения, J следующий смежный предмет и N вашу цель idx

Два случая:

• вариант 1: элементдо N

    I|J| | | |N
    J| | | |N|I

Все ваши элементы между I+1 и N (включены) переведены влево

• case 2: item isпосле N

    N| | | |I|J
    N|I| | | |J

Все элементы между N+1 и I-1 переведены вправо.

На данный момент приблизительно псевдокод (об индексах) выглядит так:

while el = L.pop()
    moveItem(el, N)
    if el < N
        for all indices of L > el and el < N
            indices--
    else
        for all indices of L < el and > N
            indices++
    N+=1 #target our last elem

---

Ниже (предполагаемого) правильного инструмента

def move_item(lst, src, dst):
    print('move ', src, dst)
    el = lst.pop(src)
    lst.insert(dst, el)

def move_items(arr, indices, N):
    while(len(indices)):
        el = indices.pop(0)
        if el == N:
            #our elem is in place
            #target is the elem after
            N += 1
            continue

        if el < N:
            #pop effect
            N -=1

            #insert the elem after N (
            move_item(arr, el, N)
            for j in range(len(indices)):
                el2 = indices[j]
                if el2 > el and el2 <= N:
                    indices[j] -= 1
        else:
            move_item(arr, el, N)
            for j in range(len(indices)):
                el2 = indices[j]
                if el2 > N and el2 < el:
                    indices[j] += 1

        #we have inserted an elem after N
        #next target is our last elem
        N += 1
        print('now', arr, 'indices', indices)


move_items([0,1,2,3,4,5,6,7,8,9,10,11,12], [8,2,7,4,0],6)    #[1, 3, 5, 8, 2, 7, 4, 0, 6, 9, 10, 11, 12]
move_items([0,1,2,3,4,5,6,7,8,9,10,11,12], [8,2,7,4,0,10],6) #[1, 3, 5, 8, 2, 7, 4, 0, 10, 6, 9, 11, 12]
move_items([0,1,2,3,4,5,6,7,8,9,10,11,12], [1,10,5,7,3,8],6) #[0, 2, 3, 4, 1, 10, 5, 6, 7, 8, 9, 11, 12]

Answer 2

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

def moveitems(from_indices, to_index):

    while from_indices:
        el = from_indices.pop(0)
        if el != to_index:
            if el < to_index: to_index -=1

            moveitem(el,to_index)
            for i in range(len(from_indices)):
                el2 = from_indices[i]
                if (el < to_index) and (el2 > el) and (el2 <= to_index):
                    from_indices[i] -= 1
                elif (el > to_index) and (el2 > to_index) and (el2 < el):
                    from_indices[i] += 1

        to_index += 1