5
\$\begingroup\$

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:

  1. perms(n), which gives me all permutations of 0, ..., n- 1 which have one fixed point,
  2. fixtest(L,m), which tests if the permutation L has m fixed points,
  3. rot(L), which rotates the permutation L, i.e. [1,2,3] becomes [2,3,1] and
  4. 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 < 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'
\$\endgroup\$
6
  • \$\begingroup\$ So you have to rotate a permutation n times? \$\endgroup\$ Mar 29 '20 at 17:07
  • \$\begingroup\$ @DaniMesejo To find a counterexample, we need to find a permutation such that after every rotation there's only one fixed point. \$\endgroup\$
    – Ramanujan
    Mar 29 '20 at 18:48
  • \$\begingroup\$ Yep, that is correct but isn't the rotation another permutation? That you could have check already? \$\endgroup\$ Mar 29 '20 at 18:49
  • \$\begingroup\$ @DaniMesejo Yes. I haven't found a good way to eliminate them, though. \$\endgroup\$
    – Ramanujan
    Mar 29 '20 at 18:55
  • 3
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Ramanujan
    Mar 29 '20 at 19:13
3
+50
\$\begingroup\$

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) -> 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
) -> 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) -> 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) -> 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)]
\$\endgroup\$
2
  • \$\begingroup\$ Since I don't know generators and typing it wil take time for me to understand this. But thanks for your help. \$\endgroup\$
    – Ramanujan
    Apr 6 '20 at 16:53
  • \$\begingroup\$ seems like I misunderstood the original question. I corrected my algorithm. \$\endgroup\$ Apr 6 '20 at 19:42
1
\$\begingroup\$

You're checking way too much in your program. In your test function, the all is going through every single element in the list and checking if it's True. What you should do is do the check yourself, and return on the very first instance of a False value. With the other optimizations made, this speed up runtime from 18 seconds to about four seconds.

You can do the same check above in the fixtest function. Simply return on the very first time that the value is above the points parameter passed. This reduces the amount of iterations needed. Let's say points was 1, as you wrote. At the end of the loop, after checking a lot of permutations, the if statement check is now if 1 == 1467811728:, or some arbitrarily large number. With returning on the first instance of it being above the points parameter, it's a lot faster.

You shouldn't need to convert the list to a deque to just shift the list. Use list slicing, it's better. You also pass a list as an argument to a function, then convert that list to a list, even when you just passed one! This unnecessary converting can slow down your program.

Also, use better variable names and type hinting. Makes your program a lot clearer and easier to understand.

At the end of the day, for n=10 the program takes about four seconds to run, give or take a few hundred milliseconds.

from itertools import permutations
from typing import List, Tuple, Union

def perms(number_of_permutations: int):
    """
    Returns a list of all permutations of `n` with one fixed point.
    """
    P = (perm for perm in permutations(range(number_of_permutations)))
    return [
        perm for perm in P if sum(1 if idx == k else 0 for idx, k in enumerate(perm)) == 1
    ]

def fixtest(sequence: List[int], points: int) -> bool:
    """
    Tests if a sequence has `points` fixed points.
    """
    count = 0
    for index, value in enumerate(sequence):
        if index == value:
            count += 1
        if count > points:
            return False
    return True

def rotate(sequence: List[int]) -> List[int]:
    """
    Rotates the sequence by one position
    """
    return sequence[-1:] + sequence[:-1]

def test(number: int) -> Union[Tuple[int, str], Tuple[int, str, List[int]]]:
    """
    Run numerous tests for this code.
    """
    for f in perms(number):
        C = []
        for _ in range(number - 1):
            f = rotate(f)
            C.append(fixtest(f, 1))
        for value in C:
            if not value:
                return number, 'no counterexamples found'
        return number, 'Counterexample found:', f

# [START] 21.5174s
# [END] 4.6866s

Edit: That Union type hint may look confusing, so let me clear that up. It's essentially saying that the function will either return a tuple of an int and a string, or a tuple of an int, a string, and a list of integers. It depends on what the outcome of the tests are.

\$\endgroup\$
3
  • \$\begingroup\$ I believe your indentation is wrong as it will only test 1 permutation as written \$\endgroup\$ Apr 6 '20 at 4:08
  • \$\begingroup\$ you can replace 1 if idx == k else 0 with a simple idx==k. True counts as 1, False as 0 \$\endgroup\$ Apr 6 '20 at 11:46
  • \$\begingroup\$ No need to make the arguments of rotate into List. This also works for tuples, or any contained which you can slice on index \$\endgroup\$ Apr 6 '20 at 11:47
1
\$\begingroup\$

The next big improvement is also an algorithmic one. Rather than rotating a permutation n times, to check for fixed points, we can instead look the distribution of (index-value) % n. If two different elements of the permutation have the same value x for this, it means that rotating by x will produce 2 fixed points. This means that for each permutation, rather than doing n rotations (O(n^2)), we can instead hash all values of this quantity, and check for colsions (O(n)).

The result is

def rotfixtest(sequence: List[int], points: int):
    """
    Tests if a sequence has `points` fixed points.
    """
    n = len(sequence)
    offsets = Counter()
    for index, value in enumerate(sequence):
        offsets[(index - value) % n] += 1
    most_common = offsets.most_common(1)
    if most_common[0][1] >= points:
        return False
    return most_common[0][0]

def test(number: int) -> Union[Tuple[int, str], Tuple[int, str, List[int]]]:
    """
    Run numerous tests for this code.
    """
    for f in perms(number):
        rotations = rotfixtest(f, 2)
        if rotations:
            return number, 'Counterexample found:', f, rotations
    return number, 'no counterexamples found'
\$\endgroup\$
1
\$\begingroup\$

Your major issue here is the algorithm, in which the number of operations grows as the factorial as n. To avoid this you will, I believe, need to go inside the loops that generate permutations.

First, I'd like to restate the problem as: if n individuals are seated around a table and then rearranged randomly, is it possible to move them in such a way that everybody moves a different number of places? The number of places moved is counted clockwise, from 0 to n-1.

This is equivalent to your problem, because if any two are moved displaced the same number of places, they can be rotated back to their original places.

This means that we are looking for solutions in which each displacement 0 to n-1 is used once and only once. For any solution, we can generate another n-1 solutions by rotations: if there is a solution in which place 1 does not move, we can re-label to get a solution in which 0 does not move. It follows that it is enough to look only at the cases in which position 0 has 0 displacement.

The next step is to observe that if we select 0 for position 0, the normal set of permutations as n-1 options for place 1, namely 1 to n-1, but in this problem we have only n-2 options, 2 to n-1. Then when we make a selection for position 1, it will generally rule out two choices for position 2, so we only have n-4 options left to try for position 2. This starts to look like a problem with only the n/2 factorial options to search through.

The following code will loop through this algorithm recursively. The timing is 68 seconds for n=14, 0.083 seconds for n=10 (compared with 27 seconds for n=10 using your algorithm).

(Edited to take into account feedback below -- but the algorithm is unchanged).

def options(ring_length,options_used):
  """The options functions computes the available options at the 
         next position in a ring of length *ring_length* given places 
         taken specified in *options_used*, taking into account 
         that no index should be reused and no displacement should 
         be reused.
  """

  l1 = len(options_used)

  displacements_used = [ ( options_used[i] - i ) % ring_length for i in range(l1) ]

  options_next = [i for i in range(ring_length) if (i not in options_used) and ( (i - l1) % ring_length not in displacements_used)]

  return options_next

def _recurse(ring_length,options_used,result_set):
  """
    ring_length: length of ring (number of elements)
    options_used: options which have been set for some of 
             the places: this is a list of length 1 up to ring_length - 1
            specifying the elements which have been set so far;
    result_set: a set which is used to accumulate permutations 
                 which match the imposed constraint.
  """

  for i in options(ring_length,options_used):
    if len(options_used) == ring_length-1:
      result_set.add( tuple( options_used + [i,] ) )
    else:
      _recurse(ring_length,options_used + [i,],result_set)

def testn(ring_length,result_set):
  """Search for permutations of a ring of length *ring_length* with 
       the constraint that all displacements should be different.
  """
  _recurse(ring_length,[0,],result_set)


if __name__ == "__main__":
  import sys
  ring_length = int( sys.argv[1] )
  result_set = set()
  testn(ring_length,result_set)

  count = len( result_set )
  print( "%s: %s,:: %s" % (ring_length, count, count*ring_length) )

To verify that the code is doing the same as your algorithm, I have tweaked your code to count the solutions, rather than stopping at the first, and verified that the results are the same up to n=12. The results are zero for even numbers and the following for odd numbers (extended up to n=15):

n     # solutions
3           3
5          15
7         133
9        2025
11      37851
13    1030367
15   36362925

I've checked even numbers up to n=14: still no solutions. Despite these algorithmic improvements, checking n=16 would take several hours on my laptop. The cost is growing roughly as the factorial of n/2, which is a lot slower than n factorial, but still fast. I suspect that the efficiency of the options function could be improved, but it would be nice to know if there is a mathematical solution.

\$\endgroup\$
3
  • \$\begingroup\$ no need for the ´Callback´. you can do results = set(); testn(k, result.__add__), or make the purpose even clearer by just passing the result set along as argument \$\endgroup\$ Apr 6 '20 at 14:28
  • \$\begingroup\$ I have also difficulty following your algorithm. The obscure variable names don't really help \$\endgroup\$ Apr 6 '20 at 14:31
  • \$\begingroup\$ Fair comment. I was so pleased to get the algorithm working that I failed to tidy up the code. I've created clearer variable names and removed the callback function, as you suggested, and also simplified the logical structure of the options function. This doesn't change the timing of the script. \$\endgroup\$
    – M Juckes
    Apr 6 '20 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.