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")