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

Просто интересно, какой самый эффективный способ создания всех циклических сдвигов списка в 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 есть что-то, что поможет? Или, может быть, двусторонняя очередь для второго случая?


python list algorithm permutation
person ztangent    schedule 15.03.2011    source источник
comment
Ваша реализация не работает - они добавляют список (целые числа) и списки, что невозможно. Кроме того, они добавляют один и тот же экземпляр списка на каждой итерации, поэтому вы получите квадрат, состоящий из n раз одной и той же строки.   -  person Sven Marnach    schedule 15.03.2011
comment
Упс, пропустил, спасибо. На самом деле не тестировал код: p   -  person ztangent    schedule 15.03.2011

Ответы (7)


arrow_upward
11
arrow_downward

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

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

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

person Sven Marnach    schedule 15.03.2011
comment
Ничего себе, не думал, что вы можете сделать это, используя понимание списка! Возможно, мне следовало подумать сильнее. Реквизит для того, чтобы не использовать какие-либо дополнительные модули. - person ztangent; 15.03.2011

arrow_upward
18
arrow_downward

Вы можете использовать collections.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).

person Maciej Ziarko    schedule 15.03.2011
comment
Этот метод rotate довольно крут. Никогда не знал, что очереди могут сделать это. Опять же, я, вероятно, должен был тщательно прочитать документацию, прежде чем спрашивать. - person ztangent; 15.03.2011
comment
Поскольку это двусторонняя очередь, операция rotate, вероятно, реализована эффективно. - person Maciej Ziarko; 15.03.2011
comment
А документация действительно наши лучшие друзья. :) - person Maciej Ziarko; 15.03.2011

arrow_upward
6
arrow_downward

вариация нарезки "закона сохранения" 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]]
person f5r5e5d    schedule 13.02.2017

arrow_upward
1
arrow_downward

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

См. также Википедию:

Циклический сдвиг — это особый вид циклической перестановки, которая, в свою очередь, является особым видом перестановки.

person pylang    schedule 22.01.2018

arrow_upward
0
arrow_downward

Использование itertools, чтобы избежать индексации:

x = itertools.cycle(a)
[[x.next() for i in a] for j in a]
person Bruno Lenzi    schedule 08.06.2012

arrow_upward
0
arrow_downward

Ответ @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 из соображений синхронизации.

person user2487951    schedule 16.02.2017

arrow_upward
0
arrow_downward

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

#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, чтобы лучше понять Нарезка списка.

person Anivarth    schedule 15.05.2016