前端之家

  1. 首页
  2. 问答

将列表中的项目子列表移到新位置

• 问答

我已经解决这个问题已有一段时间了，并在Google上进行了广泛的搜索，但从未提出过令人满意的，干净的解决方案。这个问题似乎很简单，解决方案似乎总是非常诱人，但到目前为止，它使我难以捉摸。

问题

考虑从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,... ]

对 moveitems（[8，2，7，4，0]，6）的调用应将其转换为：

[1,... ]

具有以下（或等效的）移动指令序列：

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,4，...] 。我们不知道远程列表的长度，但是它必须至少与列表 from_indices 和索引 to_index 中出现的最大索引一样长。 / p>

然后我们遍历要移动的项目（ from_indices ）-每次 item 是要移动的项目，而 last 是先前移动的项目。想法是从列表中的任意位置弹出该项目，并将其插入到最后移动的项目旁边。由于Python中的列表插入会在插入点之前在当前项目之前插入项目，因此我们以相反的顺序遍历 from_indices 。我们在列表 lst 中搜索 item 和 last ，以获取其位置 source 和 dest ，然后从位置 source 中弹出 item ，并将其插入到先前移动的位置 dest 之前的项目之前。当目标位置高于源位置时，需要进行较小的校正，以补偿弹出 source 时目标位置向下偏移1的情况。

此解决方案有效-从某种意义上说，它产生的列表等同于上述（ expr1 ）和（ expr2 ）产生的列表-但存在3个主要问题：

  • 这很丑；
  • 这很丑；和
  • 对于大索引来说是不切实际的。

因为只要最大兴趣索引，该算法就会构造一个临时索引列表，因此即使移动一个较大的列表中的几个项目也会引起可观的时间和空间。考虑一下类似的东西：

moveitems([56,19],1000000)

挑战

我正在寻找一种算法，该算法可以直接计算所需的 moveitem 指令序列，从而在移动项目时正确跟踪索引，因为它们在更改时无需操纵和重复搜索（可能非常大）的临时索引列表。如果算法按照列表 from_indices 中列出的顺序移动项目，则奖励积分。

上下文

这些项目代表远程服务器上的文档。用户可以浏览列表，选择文档的随机子列表，然后将它们拖到列表中的新位置。然后，客户端必须向服务器发送一系列 moveitem 指令，以对列表进行相应的重新排序。文档必须保留选择时的顺序（不是原始顺序）。

dongjian_011 回答：将列表中的项目子列表移到新位置

考虑I要移动的物品，J下一个相邻的物品，以及N您的目标idx

两种情况：

  • 情况1：项目在N之前
    I|J| | | |N
    J| | | |N|I

您在I+1和N（包括）之间的所有元素都被翻译到左侧

  • 情况2：项目在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 ',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,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,0],6)    #[1,12]
move_items([0,10],6) #[1,[1,8],6) #[0,12]
,

感谢user753642提供上述答案。我已经重写了他的算法，使其使用与原始问题相同的符号名，并使代码的编码更加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
algorithmlist
本文链接：https://www.f2er.com/3125953.html

大家都在问