Comment créer un calendrier pour les n-pasteurs visitant des églises?

Question

Je veux faire un calendrier pour beaucoup de pasteurs. Les conditions sont les suivantes:

1. Chaque mois, chaque pasteur doit doit aller à une autre église,
2. Le pasteur ne doit pas aller à même église où il venait
3. en 1 an, il doit aller à 12 églises différentes
4. Il y a 13 églises et 13 pasteurs et chaque église accepte seulement 1 pasteur chaque mois

Je ne peux pas utiliser au hasard (1 à 12) parce qu'il ya une chance que le pasteur pouvait aller à la même église (8 , 3% de chance qu'il se rende au même église). Je veux faire une petite chance (environ 3% ou moins) qu'il va à la même église.

Answer 1

Vos conditions n'exigent pas que la prochaine église pour un pasteur donné soit choisie au hasard. Ne pourriez-vous pas parcourir la liste de l'église? En d'autres termes, affectez à chaque pasteur un nombre de 0 à 12. Attribuez un numéro à chaque église, 0-12. Le premier mois:

Mois 0:
pasteur-0 -> église 0
pasteur-1 -> église-1
pasteur-2 -> église 2
.. .
pasteur-n -> église n

Le mois prochain, incrémenter seulement l'un des compteurs (avec wrap-around)

Mois 1:
pasteur-0 -> église-1
pasteur-1 -> église-2
pasteur-2 -> église 3
...
pasteur-n - > église-0

répéter ensuite pour les mois restants:

mois 3:
pasteur-0 -> église-2
pasteur-1 -> église-3
pasteur-2 -> église-4

... pastor- (n-1) -> église-0
pasteur-n -> église-1

Il y a une très simple boucle à tout cela (O (n)). Si cela vous déroute, je suggère d'essayer la boucle sur papier avec say n = 3.

Si le caractère aléatoire est une exigence, veuillez mettre à jour votre question.

EDIT PAR PAX

Je supprimer ma réponse et en votant celui-ci puisqu'il est O (n) et l'expansion de la mine pour répondre aux modifications aurait été au moins O (n^2) .

Vous pouvez toujours avoir hasard en faisant le pasteur-0 par le pasteur-N indices de valeurs dans un tableau de pasteurs qui a été triés au hasard pour que cette solution fait au moins aussi bonne que la mienne.

FIN EDIT PAX

Answer 2

Étant donné que vous avez le même nombre de pasteurs et églises, voici un algorithme très simple:

1. Numéro chaque église de 0 à 12

2. Construct un tableau avec les éléments 0 à 12 dedans.

3. Effectuez un Knuth Shuffle (voir ci-dessous) sur la matrice, en produisant une liste aléatoire aléatoire des églises. Chaque pasteur commence dans sa propre église (si les pasteurs n'ont pas d'églises assignées, il suffit de numéroter arbitrairement les pasteurs de 0 à 12 et de les faire correspondre avec l'église avec le même nombre). Chaque mois, chaque pasteur se déplace à l'église suivante sur la liste. S'ils sont à la dernière église sur la liste, ils vont au premier.

Ceci a le mérite d'être vraiment facile à expliquer: Présentez simplement chaque pasteur avec la liste mélangée et dites-leur par où commencer.

Un Knuth aléatoire est (à peu près) ceci:

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

Il est vraiment important de noter que chaque itération, vous permutant l'élément en cours dans la liste avec un élément aléatoire sélectionné uniquement à celles qui ont pas déjà sélectionné. Cela garantit que le nombre de shuffles possibles correspond exactement au nombre de permutations (et donc, qu'ils ont tous une probabilité égale), quelque chose de naïf à partir d'éléments aléatoires échangés, ou permuter l'élément courant avec n'importe quel élément de la liste entière. t avoir.