Я новичок в 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)]
 

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

Я был бы признателен за любую помощь от более опытных товарищей, которым нравится хорошая проблема 🙂

Приветствия!

Это называется «кодирование длины выполнения»; найдите в теме ресурсы.

Это работает с просто разделенными парами в исходном списке: позиции 0 amp; 1, 2 amp; 3, 4 amp; 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)]
 

Обмен внутри группы ничего не делает; единственные необходимые операции — это когда элементы пары имеют разные значения. Это (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)]
 

Чтобы получить конечный результат, теперь вам нужно пройти по списку, проверяя элементы, которые вы поменяли местами, на предмет «склеивания» с соседними элементами. В этом примере единственным соединением является соло c , дающее вам

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

Это желаемый результат.

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

 import itertools
from typing import Sequence, Tuple, TypeVar, MutableSequence

T = TypeVar('T') 

def compress(items: Sequence[T]) -> Sequence[Tuple[T, int]]:
    compressed = []
    for i in range(len(items)):
        last = 0
        if i > 0 and items[i] == items[i - 1]:
            last = compressed.pop()[1]
            
        compressed.append((items[i], last   1))
    return compressed
    

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 flip(items: Sequence[T]) -> Sequence[T]:
    flipped = []
    n = len(items)
    it = itertools.islice(range(n), 0, None, 2)
    for i in it:
        if i   1 < n:
            flipped.append(items[i   1])
        flipped.append(items[i])
    return flipped
    
assert flip([1, 2, 3]) == [2, 1, 3]
assert flip([1, 2, 3, 4]) == [2, 1, 4, 3]
assert flip(['a', 'a', 'a', 'a', 'c', 'c', 'd', 'c', 'c']) == ['a', 'a', 'a', 'a', 'c', 'c', 'c', 'd', 'c']
    

def flip_compressed(items: MutableSequence[Tuple[T, int]]) -> Sequence[Tuple[T, int]]:
    flipped = []
    n = len(items)
    
    def append_or_merge(v: T, i: int) -> None:
        x = i
        if flipped and flipped[-1][0] == v:
            x  = flipped.pop()[1]
        
        flipped.append((v, x))
        
    
    for i in range(n):
        val, cnt = items[i]
        if cnt == 0:
            continue
        times = cnt // 2
        rem = cnt % 2
    
        if times > 0:
            append_or_merge(val, times * 2)
        if rem == 1:
            if i   1 < n:
                nxt_val, nxt_cnt = items[i   1]
                append_or_merge(nxt_val, 1)
                items[i   1] = (nxt_val, nxt_cnt - 1)
            append_or_merge(val, 1)
    
    return flipped
    
assert flip_compressed([('a', 1), ('c', 1), ('d', 1)]) == [('c', 1), ('a', 1), ('d', 1)]
assert flip_compressed([('a', 1), ('c', 1), ('d', 1), ('a', 1)]) == [('c', 1), ('a', 2), ('d', 1)]
assert flip_compressed([(3, 4), (1, 2), (2, 1), (3, 2)]) == [(3, 4), (1, 2), (3, 1), (2, 1), (3, 1)]
 

Это был отличный проект для работы. Спасибо за публикацию вопроса. Я поддержал и добавил в закладки ваш вопрос.

Я правильно понял все 4 процесса. Вот мой код для 4 элементов:

1. сжатый список
2. распаковать список [понимание списка]
3. переворачивал элементы в списке при изменении последовательности
4. перевернул сжатый список при изменении последовательности. Очевидно, сделал это без распаковки

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

сжатие списка

 def compress(lst):
    total = 1
    compressed = []
    for i in range(1, len(lst)):
        if lst[i-1] != lst[i]:
            compressed.append((lst[i-1],total))
            total = 1
        else:
            total  = 1
            if i == len(lst)-1: compressed.append((lst[i],total))
    return compressed

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)]

print ('Run Length Encoding : compression :')
print ()
print ("[3, 3, 3, 3, 1, 1, 2, 3, 3]")
print (compress([3, 3, 3, 3, 1, 1, 2, 3, 3]))
print ()
print ("['a','a','c','c','c','d','c','c','c','c']")
print (compress(['a','a','c','c','c','d','c','c','c','c']))
print ()
 

Вывод для приведенного выше кода:

 Run Length Encoding : compression :

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

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

распаковать список

 def decompress(lst):
    return [a[0] for a in lst for i in range(a[1])]

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']

print ('Run Length Encoding : decompression :')
print ()
print ("[(3, 4), (1, 2), (2, 1), (3, 2)]")
print (decompress([(3, 4), (1, 2), (2, 1), (3, 2)]))
print ()
print ("[('a', 2), ('c', 3), ('d', 1), ('c', 4)]")
print (decompress([('a', 2), ('c', 3), ('d', 1), ('c', 4)]))
print ()
 

Вывод для приведенного выше кода:

 Run Length Encoding : decompression :

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

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

переключение значений в списке при изменении значения

 def flipping(lst):
    i = 0
    while i < len(lst)-1:
        if lst[i] != lst[i 1]:
            lst[i],lst[i 1] = lst[i 1],lst[i]
        i =2
    return lst

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']

print ('Run Length Encoding : flipping :')
print ()
print ("[1, 2, 3]")
print (flipping([1, 2, 3]))
print ()
print ("[1, 2, 3, 4]")
print (flipping([1, 2, 3, 4]))
print ()
print ("['a','a','a','a','c', 'c','d','c','c']")
print (flipping(['a','a','a','a','c', 'c','d','c','c']))
print ()
 

Вывод для приведенного выше кода:

 Run Length Encoding : flipping :

[1, 2, 3]
[2, 1, 3]

[1, 2, 3, 4]
[2, 1, 4, 3]

['a','a','a','a','c', 'c','d','c','c']
['a', 'a', 'a', 'a', 'c', 'c', 'c', 'd', 'c']
 

переворачивайте сжатый список без распаковки

 def flip_compressed(lst):    
    i = 0
    j = len(lst)
    flst = [[a[0],a[1]] for a in lst] #convert tuples to lists for ease of manipulation

    while i < len(flst)-1:   #flip based on position. flip only if value is 1
        if flst[i][1] == 1:
            if flst[i 1][1] > 1:
                flst[i 1][1] -=1
                flst.insert(i 1,[flst[i 1][0],1])
            flst[i][0],flst[i 1][0] = flst[i 1][0],flst[i][0]
        i  =2
    i = 0
    while i < len(flst)-1:    #check if we need to merge any of the compressed items
        if flst[i][0] == flst[i 1][0]:
            flst[i][1]  = flst[i 1][1]
            flst.pop(i 1)
        else:
            i =1

    flst = [(a[0],a[1]) for a in flst] #convert it back to tuples
    return flst

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

print ('Run Length Encoding : flip compressed :')
print ()
print ("[('a', 1), ('c', 1), ('d', 1)]")
print (flip_compressed([('a', 1), ('c', 1), ('d', 1)]))
print ()
print ("[('a', 1), ('c', 1), ('d', 1), ('a', 1)]")
print (flip_compressed([('a', 1), ('c', 1), ('d', 1), ('a', 1)]))
print ()
print ("[(3, 4), (1, 2), (2, 1), (3, 2)]")
print (flip_compressed([(3, 4), (1, 2), (2, 1), (3, 2)]))
print ()
 

Вывод для приведенного выше кода:

 Run Length Encoding : flip compressed :

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

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

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