python - 在 Python 中翻转压缩列表中的对

Question

我是 Python 的新手，几天来我一直在思考一个问题。我一直在考虑将其留空并等待教授的回答，但我们仍然没有收到上一次作业(3 个月前)的答案，我真的很想进步。

设置:

我做了以下功能，可以根据重复次数压缩列表:

def compress(list: List[T]) -> List[Tuple[T, int]] :
    """Returns the compressed list"""
    if len(list) == 1 :
        return [(list[0], 1)]
    result: List[Tuple[T, int]] = []
    count: int = 1
    i: int
    for i in range(1, len(list)) :
        if list[i] != list[i-1] :
            result.append((list[i-1], count))
            count = 1
        else :
            count = count + 1
            if i == len(list)-1 :
                result.append((list[i], count))
    return result

assert compress([3, 3, 3, 3, 1, 1, 2, 3, 3]) == [(3, 4), (1, 2), (2, 1), (3, 2)]
assert compress(['a','a','c','c','c','d','c','c','c','c']) == [('a', 2), ('c', 3), ('d', 1), ('c', 4)]

我还做了如下的解压功能:

def decompress(code: List[Tuple[T, int]]) -> List[T] :
    """Returns the decompressed list"""
    return [value for (value, nb) in code for i in range(nb)]

assert decompress([(3, 4), (1, 2), (2, 1), (3, 2)]) == [3, 3, 3, 3, 1, 1, 2, 3, 3]
assert decompress([('a', 2), ('c', 3), ('d', 1), ('c', 4)]) == ['a', 'a', 'c', 'c', 'c', 'd', 'c', 'c', 'c', 'c']

然后我做了一个“翻转”功能，翻转列表中的所有其他项目(我知道它没用但是嘿，练习说我必须这样做......):

def flipping(liste:List[T]) -> List[T] :
    """Returns the list after flipping every other item"""
    length:int = len(liste)
    quotient: int = length // 2
    i:int
    result: List[T] = []
    for i in range(quotient) :
        resultat = result + [liste[2*i+1], liste[2*i]]
    if length % 2 == 1 :
        result = result + [liste[-1]]
    return result

assert flipping([1, 2, 3]) == [2, 1, 3]
assert flipping([1, 2, 3, 4]) == [2, 1, 4, 3]
assert flipping(['a', 'a', 'a', 'a', 'c', 'c', 'd', 'c', 'c']) == ['a', 'a', 'a', 'a', 'c', 'c', 'c', 'd', 'c']

问题:

我现在被要求制作一个可以以相同方式翻转项目的函数，但是来自压缩列表并且不解压缩它(是的，我知道，没有乐趣)。

我唯一确定的是它应该是这样的:

def flipping_compressed(code:List[Tuple[T, int]]) -> List[Tuple[T, int]] :
    #does magic
    return result

assert flipping_compressed([('a', 1), ('c', 1), ('d', 1)]) == [('c', 1), ('a', 1), ('d', 1)]
assert flipping_compressed([('a', 1), ('c', 1), ('d', 1), ('a', 1)]) == [('c', 1), ('a', 2), ('d', 1)]
assert flipping_compressed([(3, 4), (1, 2), (2, 1), (3, 2)]) == [(3, 4), (1, 2), (3, 1), (2, 1), (3, 1)]

我已经尝试了好几天，每次都以一个充满嵌套 if 的庞大函数结束，但无论如何都无法正常工作。整个作业应该在两个小时内完成，所以我显然在这里遗漏了一些东西。

我很感激有经验的同志们的任何帮助，他们喜欢一个很好的问题:)

干杯!

Answer 1

这叫做“游程编码”；在主题中搜索资源。

这对原始列表中的简单分区对进行操作:位置 0 和 1、2 和 3、4 和 5，... 要在不解压缩列表的情况下进行交换，您需要在所有交换点对列表进行分区。例如，给定您的压缩列表

[(3, 4), (1, 2), (2, 1), (3, 2)]

您需要在需要与相邻元素交换的地方打断单个元素。在这个例子中，

(3, 4)   pos 0-3, no need to break
(1, 2)   pos 4-5, no need to break
(2, 1)   pos 6 .. needs a partner
(3, 2)   pos 7-8, needs the first element separated.

一次需要的休息给了你

[(3, 4), (1, 2), (2, 1), (3, 1), (3, 1)]

在组内交换没有任何作用；唯一需要的操作是 pair 元素具有不同值的地方。这里是 (2, 1), (3, 1)。

[(3, 4), (1, 2), (3, 1), (2, 1), (3, 1)]

碰巧，这是您的最终结果。

让我们看看你给出的另一个案例:

[('a', 2), ('c', 3), ('d', 1), ('c', 4)]

有了所需的奇偶校验中断，这就变成了

[('a', 2), ('c', 2), ('c', 1), ('d', 1), ('c', 4)]

现在，交换相邻的奇偶索引对:

[('a', 2), ('c', 2), ('d', 1), ('c', 1), ('c', 4)]

要获得最终结果，您现在需要遍历列表，检查您为与相邻元素“绑定(bind)”而交换的项目。在这个例子中，唯一的连接是单独的 c，给你

[('a', 2), ('c', 2), ('d', 1), ('c', 5)]

这是期望的结果。

我相信您可以根据这个算法大纲编写一些代码。