Check whether a permutation with one fixed point can be rotated into one with two fixed points A friend gave me the following riddle:


  Given n people with n distinct names, you place n names tags on a round table with n seats. If the n people now sit at those seats randomly such that exactly one person sits correctly (in the seat with the correct name tag with their name one it), can we rotate the table such that (at least) two people sit correctly?


For odd n this is false, which you can see by considering by placing the name tags 1, ..., n in order and seating the people as 1, n, n - 1, ... 2. I haven't been able that this true for even n so I wanted to try out small even n with a python script.

I wrote the following code. Unfortunately, it is very slow (n = 10 takes about 25 seconds, but n = 12 takes nearly 11 minutes!) so I am searching for libraries which can speed up the things I implemented from scratch or maybe a method which speeds things up.

I have 4 methods:


perms(n), which gives me all permutations of 0, ..., n- 1 which have one fixed point,
fixtest(L,m), which tests if the permutation L has m fixed points,
rot(L), which rotates the permutation L, i.e. [1,2,3] becomes [2,3,1] and
test(n) which, for a given n generates all permutations of 0, ..., n- 1 which have one fixed point with perms(n) and then for each one, performs all rotations and for every rotation checks the number of fixed points and writes them in a list C. If C only contains ones, we have found a counterexample to the riddle above.


My code looks like this

from itertools import permutations
from collections import deque

# find all permutations of [n] with 1 fixed point
def perms(n):
    P = (perm for perm in permutations(range(n)))
    D = []                        # D will contain the 'right' permutations (those with one fixed point)
    for perm in P:                # count fixed points (counter c)
        c = 0
        for idx, k in enumerate(perm):
            if idx == k:
                c +=1
        if c == 1:
            D.append(perm)          
    return D

 # tests if a sequence L has m fixed points
def fixtest(L,m):
    L = list(L)
    c = 0
    for idx, k in enumerate(L):
        if idx == k:
            c +=1
    if c == m:
        return True
    else:
        return False

# rotates the list L    
def rot(L):
    L = deque(L)
    a = L.pop()
    L.appendleft(a)
    return list(L)



def test(n): 
    for f in perms(n):
        k = 0
        C = []
        f_real = list(f)
        while k &lt; n - 1:
            f = rot(f)
            C.append(fixtest(f,1))
            k +=1
        if all(x == True for x in C): 
            return n, 'Counterexample found:', f_real
    return n, 'no counterexamples found'
Doc-string

You can add a docstring to the method using the convention of PEP-257 so IDE's etc can parse it and show it when looking at the method.

typing

By adding type annotations you can make it more clear to the user of the function what input the methods require and what to expect as answers, serving as extra documentation. It also allows static analysers like mypy to discover bugs.

generator

Instead of returning a list, you can have the permutation generate yield the correct permutations one by one

reduce the number of permutations

If any permutation where 1 person sits on the correct chair is ok, why not pick one where person 0 sits on the correct chair. This reduces the number of permutations to check n times

import itertools
import typing
def perms_gen(n: int) -&gt; typing.Iterator[typing.Sequence[int]]:
    """Yields the permutations where only the first person sits on his own seat."""
    for perm in itertools.permutations(range(1, n)):
        if any(i == j  for i,j in enumerate(perm, 1)):
            continue
        yield (0,) + perm


This is a generator function which yields a new permutation each time another function (next, for-loop, ..) asks for it,instead of all generating them in one go. This way, only those permutations that are needed are generated, and they occupy less memory. I you want a list of all permutations, you have to explicitly ask for it by list(perms_gen(10))

rotate

Rotating a list can be done by splice indexing. No need to call a deque. If you want to use a deque, then use its rotate method, instead of popping and appending yourself

Saving the 3 letters to type is also not useful.

def rotate(
    seq: typing.Sequence[typing.Any], n: int
) -&gt; typing.Sequence[typing.Any]:
    """Rotates `seq` `n` places."""
    n %= len(seq)
    return seq[n:] + seq[:n]


The in-place modulo is to make sure n is in the range [0, len(seq))

Testing further rotations

To see whether there is a rotation which allows more than 1 person in his or her seat, you can also count for each person how much spaces they need to go to their correct seat. If more than 1 person needs the same number of rotations, you have a match. To check whether there is no rotation of a permutation so 2 people sit in their correct seat, you can use this set comprehension {(i - j) % n for i, j in enumerate(permutation)} and test whether its length is n

return values

When there is no response, I would either raise an exception or a sentinel value. You do approximately the same, by your return n, 'Counterexample found:', f_real in case of success and in case of failure return n, 'no counterexamples found'. But using a string as sentinel value means the users of this function needs a complicated test, further complicated by the face that the lengths of the return tuples are different, so you can not use tuple unpacking.

Returning n has no use, since the user called the method with n as an argument. If he wants to produce a message with n included, he doesn't need to get it returned here.

As sentinel for failure I would return None or raise an exception.

putting it together:

def main(n: int) -&gt; typing.Optional[typing.Tuple[int, ...]]:
    """Tests whether there is a permutation so not more than 1 person
    return to their original seat when rotated.

    returns a counter example when found, or None.
    """
    for permutation in perms_gen(n):
        if len({(i - j) % n for i, j in enumerate(permutation)}) == n:
            return permutation


This either returns a tuple with an example, or None is implicitly returned when all permutations are tested.

timings

On my machine, for n == 10 this takes about 700ms compared to 30s for your original

Keeping it as a generator

If you rewrite it a bit, you can keep the rotations_to_place as a generator, only calculating as needed, and yielding the correct permutations

def main_generator(n: int) -&gt; typing.Iterator[typing.Tuple[int, ...]]:
    """Yields all complying permutations."""
    permutations = perms_gen(n)
    for permutation in perms_gen(n):
        if len({(i - j) % n for i, j in enumerate(permutation)}) == n:
            yield permutation


If you want to test if there is a permutation, you can do any(main(n)). If you want all permutations, you can do list(main(n))

For 9:

results = list(main_generator(9))



[(0, 2, 1, 6, 8, 7, 3, 5, 4),
 (0, 2, 1, 6, 8, 7, 4, 3, 5),
 (0, 2, 1, 7, 6, 8, 3, 5, 4),
 (0, 2, 1, 7, 6, 8, 4, 3, 5),
 ...
 (0, 8, 6, 5, 3, 2, 7, 1, 4),
 (0, 8, 7, 4, 6, 2, 5, 1, 3),
 (0, 8, 7, 5, 3, 6, 1, 4, 2),
 (0, 8, 7, 6, 5, 4, 3, 2, 1)]