How do I create a schedule for n-pastors visiting n-churches?

Question

I want to make a schedule for many pastors. The conditions are:

1. Every month, each pastor must must go to another church,
2. The pastor must not go to same church where he came
3. In 1 year he must go to 12 different churches
4. There is 13 churches and 13 pastors and every church accepts only 1 pastor every month

I can't use random(1 to 12) because there is a chance the pastor could go to the same church (8,3% chance he goes to the same church).

I want to make the chance small (around 3% or less) that he goes to same church.

Answer 1

Your conditions don't require that the next church for a given pastor be randomly selected. Couldn't you just iterate through the church list?

That is, assign each pastor a number, 0-12. Assign each church a number, 0-12. The first month:

Month 0:
pastor-0 --> church-0
pastor-1 --> church-1
pastor-2 --> church-2
...
pastor-n --> church-n

The next month, just increment one of the counters (with wrap-around)

Month 1:
pastor-0 --> church-1
pastor-1 --> church-2
pastor-2 --> church-3
...
pastor-n --> church-0

Then repeat for the remaining months:

Month 3:
pastor-0 --> church-2
pastor-1 --> church-3
pastor-2 --> church-4
...
pastor-(n-1) --> church-0
pastor-n --> church-1

There's a very simple loop to all this (O(n)). If it's confusing to you, I suggest trying the loop on paper with say n=3.

If the randomness is a requirement then please update your question.

EDIT BY PAX

I'm deleting my answer and up-voting this one since it's O(n) and the expansion of mine to cater for the edits would have been at least O(n^2).

You can still have randomness by making the pastor-0 through pastor-N values indexes into an array of pastors that has been randomly sorted so that makes this solution at least as good as mine.

END EDIT BY PAX

Answer 2

Given that you have the same number of pastors and churches, here's a really simple algorithm:

1. Number each church from 0 to 12

2. Construct an array with the elements 0 to 12 in it.

3. Perform a Knuth Shuffle (see below) on the array, producing a randomly shuffled list of churches.

4. Each pastor starts off in their own church (if pastors don't have assigned churches, just arbitrarially number the pastors 0 to 12 and match them with the church with the same number). Each month, every pastor moves to the next church on the list. If they're at the last church on the list, they go to the first one.

This has the bonus of being really easy to explain: Just present each pastor with the shuffled list and tell them where to start.

A Knuth shuffle is (roughly) this:

def knuth_shuffle(l):
    for i in range(len(l)):
        j = random.randint(i, len(l))
        l[i], l[j] = l[j], l[i]

It's really important to note that on each iteration, you're swapping the current item in the list with a random element selected from only those that have not already been selected. This ensures that the number of possible shuffles exactly matches the number of permutations (and thus, that they all have equal probability), something naive shuffles based on swapping random elements, or swapping the current element with any element from the entire list, don't have.