Check whether a permutation with one fixed point can be rotated into one with two fixed points
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)]