Генерация круговых сдвигов / уменьшенных латинских квадратов в Python

Question

Было просто интересно, каков наиболее эффективный способ генерации всех циклических сдвигов списка в Python.В любом направлении.Например, учитывая список [1, 2, 3, 4], я хочу сгенерировать либо:

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

, где следующая перестановка генерируется путем перемещения последнего элемента вперед, либо:

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

где следующая перестановка генерируется путем перемещения первого элемента назад.

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

Текущая реализация, которую я имею для первого случая:

def gen_latin_square(mylist):
    tmplist = mylist[:]
    latin_square = []
    for i in range(len(mylist)):
        latin_square.append(tmplist[:])
        tmplist = [tmplist.pop()] + tmplist
    return latin_square

Для второго случая это:

def gen_latin_square(mylist):
    tmplist = mylist[:]
    latin_square = []
    for i in range(len(mylist)):
        latin_square.append(tmplist[:])
        tmplist = tmplist[1:] + [tmplist[0]]
    return latin_square

Первый случай кажется мне достаточно эффективным, поскольку он использует pop(), но вы не можете сделать это во второмслучай, поэтому я хотел бы услышать идеи о том, как сделать это более эффективно.Может быть, в itertools есть что-то, что поможет?Или, может быть, двусторонняя очередь для второго случая?

Answer 1

Вы можете использовать collection.deque:

from collections import deque

g = deque([1, 2, 3, 4])

for i in range(len(g)):
    print list(g) #or do anything with permutation
    g.rotate(1) #for right rotation
    #or g.rotate(-1) for left rotation

Он печатает:

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

Чтобы изменить его для левого вращения, просто замените g.rotate(1) на g.rotate(-1).

Answer 2

Для первой части, вероятно, самый краткий способ -

a = [1, 2, 3, 4]
n = len(a)
[[a[i - j] for i in range(n)] for j in range(n)]
# [[1, 2, 3, 4], [4, 1, 2, 3], [3, 4, 1, 2], [2, 3, 4, 1]]

, а для второй части

[[a[i - j] for i in range(n)] for j in range(n, 0, -1)]
# [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

Они также должны быть намного эффективнее, чем ваш код, хотя яне делал никаких таймингов.

Answer 3

вариация нарезки "закон сохранения" a = a[:i] + a[i:]

ns = list(range(5))
ns
Out[34]: [0, 1, 2, 3, 4]

[ns[i:] + ns[:i] for i in range(len(ns))]
Out[36]: 
[[0, 1, 2, 3, 4],
 [1, 2, 3, 4, 0],
 [2, 3, 4, 0, 1],
 [3, 4, 0, 1, 2],
 [4, 0, 1, 2, 3]]


[ns[-i:] + ns[:-i] for i in range(len(ns))]
Out[38]: 
[[0, 1, 2, 3, 4],
 [4, 0, 1, 2, 3],
 [3, 4, 0, 1, 2],
 [2, 3, 4, 0, 1],
 [1, 2, 3, 4, 0]]

Answer 4

more_itertools - сторонняя библиотека, которая предлагает инструмент для циклических перестановок :

import more_itertools as mit


mit.circular_shifts(range(1, 5))
# [(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)]

См. Также Википедия :

Круговой сдвиг - это особая разновидность циклической перестановки, которая, в свою очередь, является особой разновидностью перестановок.

Answer 5

Ответ @Bruno Lenzi не работает:

In [10]: from itertools import cycle

In [11]: x = cycle('ABCD')

In [12]: print [[x.next() for _ in range(4)] for _ in range(4)]
[['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D']]

Ниже приведена правильная версия, однако решение @ f5r5e5d быстрее.

In [45]: def use_cycle(a):
    x=cycle(a)
    for _ in a:
        x.next()
        print [x.next() for _ in a]
   ....:         

In [46]: use_cycle([1,2,3,4])
[2, 3, 4, 1]
[3, 4, 1, 2]
[4, 1, 2, 3]
[1, 2, 3, 4]

In [50]: def use_slice(a):
    print [ a[n:] + a[:n] for n in range(len(a)) ]
  ....:     

In [51]: use_slice([1,2,3,4])
[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

In [54]: timeit.timeit('use_cycle([1,2,3,4])','from __main__ import use_cycle',number=100000)
Out[54]: 0.4884989261627197

In [55]: timeit.timeit('use_slice([1,2,3,4])','from __main__ import use_slice',number=100000)
Out[55]: 0.3103291988372803

In [58]: timeit.timeit('use_cycle([1,2,3,4]*100)','from __main__ import use_cycle',number=100)
Out[58]: 2.4427831172943115

In [59]: timeit.timeit('use_slice([1,2,3,4]*100)','from __main__ import use_slice',number=100)
Out[59]: 0.12029695510864258

Я удалил оператор печати в use_cycle и use_slice для целей синхронизации.

Answer 6

Это будет мое решение.

#given list
a = [1,2,3,4]
#looping through list
for i in xrange(len(a)):
    #inserting last element at the starting
    a.insert(0,a[len(a)-1])
    #removing the last element
    a = a[:len(a)-1]
    #printing if you want to
    print a

Будет выведено следующее:

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

Вы также можете использовать pop вместо нарезки списка, но проблема с pop заключается в том, что он что-то вернет.

Также приведенный выше код будет работать для любой длины списка. Я не проверил на выполнение кода. Я предполагаю, что это будет работать лучше.

Вам следует взглянуть на Документы Python , чтобы получить хорошее представление о нарезке списка.

Answer 7

Использование itertools для исключения индексации:

x = itertools.cycle(a)
[[x.next() for i in a] for j in a]