4

If not, then a canonical name for a function? 'Cycle' makes sense to me, but that's taken.

The example in the header is written for clarity and brevity. Real cases I'm working with have a lot of repetition. (e.g., I want [1, 1, 0, 0, 0, 2, 1] to "match" [0, 0, 2, 1, 1, 1, 0])

This type of thing is obscuring my algorithm and filling my code with otherwise useless repetition.

Shay
  • 1,368
  • 11
  • 17
  • 2
    Do you want to match any permutation of 0,1,2 or only certain ones? E.g. in your example you don't have [1,0,2], [0,2,1] etc – Steve Nov 21 '12 at 16:10
  • 1
    Not permutations. Just a circular list. – Shay Nov 21 '12 at 16:18
  • The optimal solution for this is probably dynamic programming, but that may be overcomplicated if the simple solution is fast enough. – Katriel Nov 21 '12 at 16:22

3 Answers3

8

You can get the cycles of the list with:

def cycles(a):
    return [ a[i:] + a[:i] for i in range(len(a)) ]

You can then check if b is a cycle of a with:

b in cycles(a)

If the length of the list is long, or if want to make multiple comparison to the same cycles, it may be beneficial (performance wise) to embed the results in a set.

set_cycles = set(cycles(a))
b in set_cycles

You can prevent necessarily constructing all the cycles by embedding the equality check in the list and using any:

any( b == a[i:]+a[:i] for i in range(len(a)))

You could also achieve this effect by turning the cycles function into a generator.

cmh
  • 10,612
  • 5
  • 30
  • 40
  • 1
    You could probably do better if you stored your cycles as tuples which you could pack into a `set`. As long as the `cycles` are small enough to reasonably store them all at once, I don't see any reason to not use a set... – mgilson Nov 21 '12 at 16:07
  • 3
    Or, you could do `any( b == a[i:]+a[:i] for i in range(len(a)))` which gets you short-circuiting :) – mgilson Nov 21 '12 at 16:08
  • @mgilson. Nice. But the asker seemed after the general function. – cmh Nov 21 '12 at 16:08
  • Think I'll go with a generator. That'll make it easier to guess how I'm using it when I see the function by itself. Don't think I've used a generator with 'in' or 'any' before, but that part should be easy to guess. Now for a name: ouroboros maybe? ha. Thanks for the help. – Shay Nov 21 '12 at 16:42
5

Misunderstood your question earlier. If you want to check if any cycle of a list l1 matches a list l2 the best (cleanest/most pythonic) method is probably any(l1 == l2[i:] + l2[:i] for i in xrange(len(l2))). There is also a rotate method in collections.deque that you might find useful.

arshajii
  • 127,459
  • 24
  • 238
  • 287
0

You could use cycle from itertools, together with islice to cut it up. This basically puts this answer in a list comprehension so the list is shifted once for every element.

>>> from itertools import islice, cycle
>>> l = [0,1,2]
>>> [tuple(islice(cycle(t),i,i+len(t))) for i,_ in enumerate(l)]
[(0, 1, 2), (1, 2, 0), (2, 0, 1)]
Community
  • 1
  • 1
Junuxx
  • 14,011
  • 5
  • 41
  • 71