Início / coding / Perguntas / 79560599
Accepted
David
Asked: 2025-04-08 03:02:29 +0800 CST

Algoritmo para detectar loop completo ao iterar sobre uma lista

  • 772

Atribuição:

Escreva uma função cycle_sublist(lst, start, step)onde:

  • lsté uma lista
  • starté um número que satisfaz:0 <= start < len(lst)
  • stepé a quantidade que aumentamos seu índice a cada iteração

sem usar : fatiamento, importação, compreensão de lista, funções integradas como mape filter.

A função funciona da seguinte maneira: começamos a iterar sobre a lista de itens quando voltamos ao início ou a cruzamos novamente. Por exemplo:

cycle_sublist([1], 0, 2) -> [1]
cycle_sublist([6, 5, 4, 3], 0, 2) -> [6, 4]
cycle_sublist([7, 6, 5, 4, 3], 3, 1) -> [4, 3, 7, 6, 5]
cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2) -> [2, 1, 9, 3]
cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3) -> [6, 3, 1]

Meu problema é detectar quando completei um ciclo. Tentei:

  • Verifique meu passo anterior e os passos atuais e compare-os com o início. O problema é que há alguns casos em que falha.
  • Contando meus passos e verificando se já havia cruzado o início.

Nenhuma delas funcionou.

Aqui está meu código - com a lógica faltante para detectar o ciclo:

def cycle_sublist(lst,start,step):
    index = start 
    length = len(last)

    cycle_complete = False
    res = []

    while True:
        index = index % length if index >= length else index

        if ...:
            cycle_complete = True

        if cycle_complete and index >= start:
            break

        res.append(lst[index])

        index += step

    return res

Se possível, gostaria que você respondesse com o algoritmo para detectar o ciclo somente para que eu mesmo possa escrever o código.

python

3 respostas

  1. Best Answer

    Esta é a minha tentativa baseada na sua. Consegui algo assim:

    def cycle_sublist(lst,start,step):
    index = start 
    length = len(lst)
    res = []

    while index < length + start:
        res.append(lst[index % length])
        index += step

    return res
    
print(cycle_sublist([1], 0, 2))                    # [1]
print(cycle_sublist([6, 5, 4, 3], 0, 2))           # [6, 4]
print(cycle_sublist([7, 6, 5, 4, 3], 3, 1))        # [4, 3, 7, 6, 5]
print(cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2))  # [2, 1, 9, 3]
print(cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3))  # [6, 3, 1]

    Basicamente, não há muita diferença entre o seu código e o meu. Você estava tentando manter o valor indexdentro de uma faixa válida, o que dificultava a detecção do fim do ciclo. A mudança que introduzi foi que permiti que o indexvalor fosse alterado em cada iteração passo a passo, sem tentar mantê-lo dentro de uma faixa válida, já que usei o restante ao indexar a lista. Acho que você sabe, mas o restante vai até, length - 1então sempre estará dentro de uma faixa válida. Além disso, removi algumas variáveis ​​não utilizadas.

    Pequena adição, não sei se é útil. Se quiser alternar várias vezes sob as condições que você definir, pode alterar a condição "while" para " while index < n * length + start:where " (onde n) e indicar quantas vezes você deseja alternar pela lista. Além disso, se quiser incluir o elemento inicial se a iteração final for definida nele, altere <para <="in while" (na condição "while").

    • 4

  2. Na verdade, você não precisa detectar se terminou de passar por um ciclo. Em vez disso, você pode tentar definir um "ciclo" primeiro e indexar por stepvez, por exemplo,

    def cycle_sublist(lst, start, step):
 return (lst[start:] + lst[:start])[::step]

print(f'cycle_sublist([1], 0, 2) --> {cycle_sublist([1], 0, 2)}')
print(f'cycle_sublist([6, 5, 4, 3], 0, 2) --> {cycle_sublist([6, 5, 4, 3], 0, 2)}')
print(f'cycle_sublist([7, 6, 5, 4, 3], 3, 1) --> {cycle_sublist([7, 6, 5, 4, 3], 3, 1)}')
print(f'cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2) --> {cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2)}')
print(f'cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3) --> {cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3)}')

    o que dá

    cycle_sublist([1], 0, 2) --> [1]
cycle_sublist([6, 5, 4, 3], 0, 2) --> [6, 4]
cycle_sublist([7, 6, 5, 4, 3], 3, 1) --> [4, 3, 7, 6, 5]
cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2) --> [2, 1, 9, 3]
cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3) --> [6, 3, 1]
    • 1

  3. O seguinte parece funcionar.

    def cycle_sublist(A, start, step):
    res = [A[start]]
    N = len(A)
    if step >= N or step <= 0:
        # degenerate cases
        return res
        
    # cycle_complete = False
    # handle elts to the right
    curr_index = start + step
    while curr_index < N:
        res.append(A[curr_index])
        curr_index += step
        
    # handle elts to the left
    # cycle_complete = True in your code
    curr_index %= N
    while curr_index < start:
        res.append(A[curr_index])
        curr_index += step
        
    return res
    
print(cycle_sublist([1], 0, 2))# -> [1]
print(cycle_sublist([6, 5, 4, 3], 0, 2))# -> [6, 4]
print(cycle_sublist([7, 6, 5, 4, 3], 3, 1))# -> [4, 3, 7, 6, 5]
print(cycle_sublist([4, 3, 2, 5, 1, 6, 9], 2, 2))# -> [2, 1, 9, 3]
print(cycle_sublist([4, 3, 2, 5, 1, 6, 9], 5, 3)) #-> [6, 3, 1]

    A principal observação é que, como você quer evitar "passar por cima", startvocê itera até atingir o fim do array e, em seguida, manipula todos os elementos à esquerda até alcançá-lo startou ultrapassá-lo novamente. O bom dessa abordagem é que o módulo é aplicado apenas uma vez e divide a iteração em dois loops em partes disjuntas do array, o que tem suas próprias vantagens e desvantagens.

    • 0

relate perguntas