Générer des groupes de personnes, selon un paramètre

Version imprimable

Bonjour,

Je dispose d'un dataframe qui représente des personnes, et leurs deux souhaits d'appartenance à un groupe de travail (il y a 5 groupes de travail, et ils doivent se départager. Pour cela, ils énoncent 2 souhaits). On a donc une première colonne de nom de personnes, une deuxième colonne (qui représente un premier vœux d'appartenance à un groupe) où ces personnes devaient entrer un numéro de groupe (de 1 à 5), et une troisième colonne (qui représente un second vœux d'appartenance à un groupe) où les personnes devaient entrer un numéro de groupe (de 1 à 5).

Voici un exemple reproductible :
Code:

1 2 3 4 5 6 import pandas as pd import numpy as np from numpy import random data = pd.DataFrame({"prenom" : ["personne1", "personne2", "personne3", "personne4", "personne5", "personne6", "personne7", "personne8", "personne9", "personne10", "personne11", "personne12", "personne13", "personne14", "personne15", "personne16", "personne17", "personne18", "personne19", "personne20"], "choix1" : np.random.randint(low=1, high=5, size=(20,)), "choix2" : np.random.randint(low=1, high=5, size=(20,))})
Je souhaite créer un programme qui répartissent aléatoirement ces personnes dans ces 5 groupes de travail (5 groupes de 4 personnes) en prenant en compte leurs choix. En priorité, on se base sur leur premier vœux ; sinon, on se base sur leur deuxième vœux. L'objectif, c'est que les 5 groupes possèdent bien 4 personnes.

Est-il possible de faire cela sur Python ?
Merci.

09/10/2020, 14h38
flapili

bonjour,

j'avais vu il y a quelque temps une vidéo de David Louapre qui semble traiter du même sujet (avec comme exemple parcoursup et les universités)
https://www.youtube.com/watch?v=dO1pLi2Dedw

en espérant que ça aide 😅

Bonjour

Citation:

Envoyé par preliator

Est-il possible de faire cela sur Python ?

Si tu peux le faire avec un papier et un crayon alors tu peux le faire avec Python (on nomme ça un algo "Turing complet"). Mais perso je m'interroge sur la contrainte "placer les personnes selon leur choix" (je présume que les choix sont les choix de numéro de groupe). Que se passe-t-il si tout le monde veut être dans le groupe (par exemple) 1 ???
En tout cas, pour placer les personnes selon leur choix, il faut commencer par trier les personnes selon leur choix.

Accessoirement ton choix est incomplet car la valeur "high" est une valeur exclue. Donc si tu veux que tes bonhommes choisissent un groupe entre 1 et 5, il te faut mettre high=6

Et comme je trouvais ta description trop rigide, j'ai réécrit ta structure pour lui permettre d'être plus modulaire (peut-être demain tu voudras passer à 50 personnes avec 4 choix). Ca donne ceci
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 data=tuple( ( "personne %d" % i, tuple(random.randint(1, 6) for i in range(2)), ) for i in range(1, 21) ) data2=dict( ( ("prenom", tuple(x[0] for x in data)), ) + tuple( ("choix%d" % (i+1), tuple(x[1][i] for x in data)) for i in range(2) ) ) frame = pd.DataFrame(data2) print(frame)
La variable "data2" n'est pas nécessaire (on peut appeler directement frame = pd.DataFrame(dict(...)) mais m'a permis de vérifier le résultat. Le seul souci c'est que je répète "2" (le nombre de choix) mais je n'arrive pas à l'éviter.

10/10/2020, 09h22
preliator

Merci pour vos réponses.

Dans le cas où il n'y aurait pas assez de combinaisons possibles pour remplir tous les groupes, le programme me renverrait un message du type "Erreur, impossible de remplir tous les groupes". Ca, je pense pouvoir le faire.

Merci.

Citation:

Envoyé par preliator

Dans le cas où il n'y aurait pas assez de combinaisons possibles pour remplir tous les groupes, le programme me renverrait un message du type "Erreur, impossible de remplir tous les groupes".

Ca roule.
Dans ce cas, tu tries les personnes selon leurs choix. Ensuite suffit de traiter les personnes triées et remplir les groupe au fur et à mesure.

Exemple...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import pandas as pd
import numpy as np
from numpy import random
 
nb_choix=2
nb_groupes=5
personnes_by_groupe=4
 
# Initialisation des groupes
groupe=[[] for i in range(nb_groupes)]
 
# Création de n personnes
personnes=tuple(
	[
		"personne %d" % i,
		tuple(random.randint(1, nb_groupes+1) for i in range(nb_choix)),
		None,
	] for i in range(1, nb_groupes * personnes_by_groupe + 1)
)
 
# Traitement des personnes triées selon leurs choix
for p in sorted(
	personnes,
	key=lambda x: x[1],
	reverse=True,
):
	# Traitement des choix
	for c in p[1]:
		# Vérification place dans groupe
		if len(groupe[c-1]) < personnes_by_groupe:
			# La personne va dans le groupe de son choix
			groupe[c-1].append(p)
 
			# Le n° de groupe est enregistré dans la personne (ça ne mange pas de pain)
			p[2]=c
 
			# Arrêt de la recherche
			break
		# if
	else:
		# Pas de groupe dispo selon un des choix
		for (i, g) in enumerate(groupe):
			print("groupe %d (%d): %s" % (i+1, len(g), g))
		raise IOError(
			"Plus de place disponible pour %s selon ses choix %s" % (
				p[0],
				", ".join(map(str, p[1])),
			)
		)
	# for
# for
 
# Affichage des groupes remplis
for (i, g) in enumerate(groupe, 1):
	print("groupe %d (%d): %s" % (i, len(g), g))
 
 
data=dict(
	(
		("prenom", tuple(x[0] for x in personnes)),
	) + tuple(
		("choix%d" % (i+1), tuple(x[1][i] for x in personnes)) for i in range(nb_choix)
	)
)
frame=pd.DataFrame(data)
print(frame)

Bonjour, et merci beaucoup pour ce code ! Je me suis empressé de l'essayer sur un exemple concret, et de l'adapter sur un dataframe.
Le code marche bien.... à la différence près que j'ai systématiquement une personne qui disparait mystérieusement dans le résultat final. Effectivement, le programme me place 19 personnes (dont 1, la personne6, qui ne peut pas être placée, avec l'erreur qui le justifie). C'est la personne16 qui disparait, avec ses choix (1, 2), les mêmes choix que Personne6 qui ne peut pas être placée.

Voici la méthodologie que j'ai appliqué, en prenant le temps de générer un dataframe semblable au mien. J'ai également tenté d'adapter le dataframe au tuple que vous aviez généré. Je remarque également, que personne16 est toujours présente, avant "l'initialisation des groupes".

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
import pandas as pd
import numpy as np
from numpy import random
 
nb_choix=2
nb_groupes=5
personnes_by_groupe=4
liste = [] 
 
# Création du dataframe d'exemple
data = pd.DataFrame({
	"nom" : ["personne1", "personne2", "personne3", "personne4", "personne5", "personne6", "personne7", "personne8", "personne9", "personne10", "personne11", "personne12", "personne13", "personne14", "personne15", "personne16", "personne17", "personne18", "personne19", "personne20"],
	"choix1" : [4, 5, 4, 2, 1, 1, 2, 4, 2, 1, 1, 3, 2, 4, 4, 1, 4, 2, 2, 5],
	"choix2" : [2, 2, 2, 1, 3, 2, 1, 2, 3, 5, 5, 1, 3, 2, 2, 2, 1, 4, 4, 4]})
 
#Transformation du dataframe, pour l'adapter à votre tuple généré
a_concat = data.iloc[:,1:]
data["join"] = a_concat.values.tolist()
 
data = data[["nom", "join"]]
data["grou"] = None
 
for i in range(len(data)):
	data["join"][i] = tuple(data["join"][i])
 
test = [tuple(x) for x in data.values]
for i in range(len(test)):
	test[i] = list(test[i])
personnes = tuple(test)
 
 
# Initialisation des groupes
groupe=[[] for i in range(nb_groupes)]
 
# Traitement des personnes triées selon leurs choix
for p in sorted(
	personnes,
	key=lambda x: x[1],
	reverse=True,
):
	# Traitement des choix
	for c in p[1]:
		# Vérification place dans groupe
		if len(groupe[c-1]) < personnes_by_groupe:
			# La personne va dans le groupe
			groupe[c-1].append(p)
 
			# Le n° de groupe est enregistré dans la personne (ça ne mange pas de pain)
			p[2]=c
 
			# Arrêt de la recherche
			break
		# if
	else:
		# Pas de groupe dispo selon un des choix
		for (i, g) in enumerate(groupe):
			print("groupe %d (%d): %s" % (i+1, len(g), g))
		raise IOError(
			"Plus de place disponible pour %s selon ses choix %s" % (
				p[0],
				", ".join(map(str, p[1])),
			)
		)
	# for
# for
for (i, g) in enumerate(groupe):
	print("groupe %d (%d): %s" % (i+1, len(g), g))
 
 
data=dict(
	(
		("prenom", tuple(x[0] for x in personnes)),
	) + tuple(
		("choix%d" % (i+1), tuple(x[1][i] for x in personnes)) for i in range(nb_choix)
	)
)
 
frame=pd.DataFrame(data)
print(frame)

Je n'arrive pas à trouver l'endroit où Personne16 disparait, ni pourquoi.

Citation:

Envoyé par preliator

Je n'arrive pas à trouver l'endroit où Personne16 disparait, ni pourquoi.

Ben... quand je reprends ton code avec exactitude, il plante à la personne 6 où ses choix (1, 2) ne peuvent pas être respectés.

Voici tes personnes et leurs choix
Code:

1 2 3 4 5 6 data = pd.DataFrame({ "nom" : ["personne1", "personne2", "personne3", "personne4", "personne5", "personne6", "personne7", "personne8", "personne9", "personne10", "personne11", "personne12", "personne13", "personne14", "personne15", "personne16", "personne17", "personne18", "personne19", "personne20"], "choix1" : [4, 5, 4, 2, 1, 1, 2, 4, 2, 1, 1, 3, 2, 4, 4, 1, 4, 2, 2, 5], "choix2" : [2, 2, 2, 1, 3, 2, 1, 2, 3, 5, 5, 1, 3, 2, 2, 2, 1, 4, 4, 4], } )
Ces choix donnent le tri suivant (je mets en rouge celles qui auront le groupe 1 et en bleu celles qui auront le groupe 2
['personne20', (5, 4), 5]
['personne2', (5, 2), 5]
['personne1', (4, 2), 4]
['personne3', (4, 2), 4]
['personne8', (4, 2), 4]
['personne14', (4, 2), 4]
['personne15', (4, 2), 2]
['personne17', (4, 1), 1]
['personne12', (3, 1), 3]
['personne18', (2, 4), 2]
['personne19', (2, 4), 2]
['personne9', (2, 3), 2]
['personne13', (2, 3), 3]
['personne4', (2, 1), 1]
['personne7', (2, 1), 1]
['personne10', (1, 5), 1]
['personne11', (1, 5), 5]
['personne5', (1, 3), 3]
Et donc quand on arrive à "personne6", les groupes 1 et 2 sont complets.

Si je remplace (1, 2) par (1, 3) (car il reste de la place dans le groupe 3), alors c'est "personne16" (qui n'avait pas encore été traitée à l'essai précédent et qui veut elle-aussi un groupe 1 ou 2) qui n'a pas de place.
Et si je remplace pour "personne16" ses choix par (1, 5) (car il reste aussi de la place dans le groupe 5) alors ça marche et ça donne ceci
groupe 1 (4): [['personne17', (4, 1), 1], ['personne4', (2, 1), 1], ['personne7', (2, 1), 1], ['personne10', (1, 5), 1]]
groupe 2 (4): [['personne15', (4, 2), 2], ['personne18', (2, 4), 2], ['personne19', (2, 4), 2], ['personne9', (2, 3), 2]]
groupe 3 (4): [['personne12', (3, 1), 3], ['personne13', (2, 3), 3], ['personne5', (1, 3), 3], ['personne6', (1, 3), 3]]
groupe 4 (4): [['personne1', (4, 2), 4], ['personne3', (4, 2), 4], ['personne8', (4, 2), 4], ['personne14', (4, 2), 4]]
groupe 5 (4): [['personne20', (5, 4), 5], ['personne2', (5, 2), 5], ['personne11', (1, 5), 5], ['personne16', (1, 5), 5]]
Et là, "personne16" est bien présente.