Обнаружение повторяющегося цикла в последовательности чисел (питон) - PullRequest
Новая
       31

Обнаружение повторяющегося цикла в последовательности чисел (питон)

9 голосов
/ 30 декабря 2011

Мне было интересно, что будет довольно «обычным» или нормальным способом сделать это.На самом деле не искал кратчайшего ответа, например, 2-строчный или что-то в этом роде.Я просто быстро соединил этот кусок кода, но я не могу не чувствовать, что там слишком много.Также, если есть какие-либо библиотеки, которые могут помочь с этим, это было бы очень хорошо. 

def get_cycle(line):
    nums = line.strip().split(' ')

    # 2 main loops, for x and y
    for x in range(2, len(nums)): # (starts at 2, assuming the sequence requires at least 2 members)
        for y in range(0, x):
            # if x is already in numbers before it
            if nums[x] == nums[y]:
                seq = [nums[x]] # (re)start the sequence
                adder = 1       # (re)set the adder to 1
                ok = True       # (re)set ok to be True
                # while the sequence still matches (is ok) and
                # tail of y hasn't reached start of x
                while ok and y + adder < x:
                    if nums[x + adder] == nums[y + adder]:  # if next y and x match
                        seq.append(nums[x + adder])         # add the number to sequence
                        adder += 1                          # increase adder
                    else:
                        ok = False                          # else the sequence is broken
                # if the sequence wasn't broken and has at least 2 members
                if ok and len(seq) > 1:
                    print(' '.join(seq))    # print it out, separated by an empty space
                    return

Ответы [ 2 ]

18 голосов
/ 30 декабря 2011

Возможно, я не совсем правильно понимаю, но я думаю, что есть очень простое решение с регулярным выражением. 

(.+ .+)( \1)+

Вот пример: 

>>> regex = re.compile(r'(.+ .+)( \1)+')
>>> match = regex.search('3 0 5 5 1 5 1 6 8')
>>> match.group(0)    # entire match
'5 1 5 1'
>>> match.group(1)    # repeating portion
'5 1'
>>> match.start()     # start index of repeating portion
6

>>> match = regex.search('2 0 6 3 1 6 3 1 6 3 1')
>>> match.group(1)
'6 3 1'

Вот как этоработает, (.+ .+) будет соответствовать как минимум двум числам (как можно большему количеству) и помещать результат в группу захвата 1. ( \1)+ будет совпадать с пробелом, за которым следует содержимое группы захвата 1, хотя бы один раз.

И расширенное объяснение для строки '3 0 5 5 1 5 1 6 8':

  • (.+ .+) первоначально будет соответствовать всей строке, но с конца откажется от символов, потому что ( \1)+ не удастся, этот возврат будетпроисходить до тех пор, пока (.+ .+) не сможет найти совпадение в начале строки, и в этот момент механизм регулярных выражений будет двигаться вперед в строке и будет пытаться снова
  • Это будет происходить до тех пор, пока группа захвата не начнется во второй 5, это даствверх символов в конце, пока '5 1' не будет захвачено, и в этот момент регулярное выражение ищет любое число ' 5 1' для ( \1)+, оно, конечно, найдет это, и совпадение будет успешнымизд
3 голосов
/ 30 декабря 2011

Ваш вопрос на самом деле "сделать все элементы из x: x + k подходящими элементами из y: y + k".То есть подмножество длины k встречается дважды в строке?

И вы хотите, чтобы x: x + k не перекрывалось с y: y + k.Самый простой способ сделать это - определить y как x плюс некоторое смещение, d.Если вы гарантируете, что k <= d <len (line) -xk, то вы всегда будете смотреть за пределы линии. </p>

Затем вы будете изменять k от 1 до len (line) //2, ищет дубликаты различной длины с заданным смещением друг от друга.

Смещение от x до y, d будет варьироваться от 1 до len (line) -xk.

Начальная позиция для x также будет варьироваться от 0 до len (строка) // 2.

Итак, часть "all" выглядит примерно так: all( line[i] == line[i+d] for i in range(x,x+k) ) для различных юридическихзначения d, x и k.

...