A Somewhat More Efficient Gift-Giving Algorithm

Posted on by

After reading the Wikipedia article on derangements and seeing how one goes about finding the number of derangements of a given size, I figured out how to generate a random size-n derangement without generating all size-n derangements and picking one. This made my Secret Santa program rather more efficient (O(n) is just a little better than exponential time!)

Also, in writing this program, I found a point in Python where two of its paradigms don’t mix well. Like most languages with first-order functions, python has map() and reduce() functions. However, method calls are handled more like C++ or Java: you call them as object.methodname(). If you want to get a list of results of a method applied to each element of a list, there doesn’t appear to be a straightforward way to do it. In this case, I wanted to strip whitespace from a list of strings. I ended up using a lambda that takes a string s and returns s.strip(), which isn’t too clumsy.

Edit: One of my friends noted that this could be handled nicely with a list comprehension. D’oh! Fixed, though the original line has been left in, commented.

For those who are interested:

#!/usr/bin/python
#
#     derange-strings.py
#
#     Takes a list of strings on standard input (one per line)
#     and prints it out alongside a random derangement of the list.
#     Can be used for secret-Santa-type gift-giving arrangements.
# 
#     Copyright (C) 2007  Neal Groothuis
# 
#     This program is free software: you can redistribute it and/or modify
#     it under the terms of the GNU General Public License as published by
#     the Free Software Foundation, either version 3 of the License, or
#     (at your option) any later version.
# 
#     This program is distributed in the hope that it will be useful,
#     but WITHOUT ANY WARRANTY; without even the implied warranty of
#     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#     GNU General Public License for more details.
# 
#     You should have received a copy of the GNU General Public License
#     along with this program.  If not, see <http ://www.gnu.org/licenses/>.

import sys
import random

def swapElements(i, j, l):
    l[i], l[j] = l[j], l[i]
    return l

def randomDerangement(n):
    if n==2:
        return [1, 0]
    else:
        k=int(random.random()*(n-1))
        return swapElements(k, n-1, randomDerangement(n-1)+[n-1])

#names=map(lambda(s): s.strip(), sys.stdin.readlines())
names=[s.strip() for s in sys.stdin.readlines()]
n=len(names)
assignments=randomDerangement(n)
for i in range(n):
    sys.stdout.write(names[i]+"\\t"+names[assignments[i]]+"\\n")

Leave a Reply