J'ai quatre groupes (qui se chevauchent partiellement) de huit candidats uniques qui ont postulé pour 20%, 30%, 40% et 50% du travail que je dois attribuer:
g20 <- c("a","b","c","d","e","f")
g30 <- c("a","b","c","d","e","f","g","h")
g40 <- c("c","d","e","f","g","h")
g50 <- c("e","f","g","h")
Parce que je ne peux attribuer le travail que dans ces quatre incréments et que je dois choisir pas moins de deux personnes et pas plus de quatre, j'ai six scénarios pour attribuer 100% du travail:
Pour chaque scénario, je dois trouver toutes les combinaisons possibles (sans remplacement) pour attribuer le travail aux candidats dans les groupes correspondants.
Je peux facilement accomplir cela pour le premier scénario utilisant t (combn (g50,2)) mais je ne sais pas comment gérer les autres scénarios où je dois tirer des combinaisons de différents vecteurs ET m'assurer qu'un candidat n'est sélectionné qu'une seule fois dans un cas donné combinaison. Le résultat doit être les combinaisons réelles, pas seulement le nombre de combinaisons.
En utilisant R, comment puis-je obtenir ces combinaisons tirées de quatre groupes différents et (en utilisant le scénario 5 comme exemple) m'assurer que " cdef "," cedf "," cfed "," cfde "etc. sont tous traités comme le même résultat?
Est-ce possible?
3 Réponses :
Oui! Ce n'est en aucun cas la solution la plus élégante ou la plus efficace, mais c'est possible. Cela prend environ 1 seconde avec ces données, mais ce sera plus lent si vous avez des données réelles qui sont plus compliquées.
D'abord, j'établis les possibilités pour chaque candidat. Je pense qu'il est plus intuitif de le présenter de cette façon, car nous devons faire un devoir (y compris la possibilité de zéro) pour chaque candidat.
# A tibble: 132 x 7 team `30/30/20/20` `40/20/20/20` `40/30/30` `40/40/20` `50/30/20` `50/50` <chr> <int> <int> <int> <int> <int> <int> 1 abc NA NA 126 NA NA NA 2 abcd 1 71 NA NA NA NA 3 abce 2 72 NA NA NA NA 4 abcf 3 73 NA NA NA NA 5 abcg 4 74 NA NA NA NA 6 abch 5 75 NA NA NA NA 7 abd NA NA 127 NA NA NA 8 abde 6 76 NA NA NA NA 9 abdf 7 77 NA NA NA NA 10 abdg 8 78 NA NA NA NA # ... with 122 more rows
Ensuite, j'énumère toutes les possibilités d'assigner le travail, en utilisant expand.grid , puis de filtrer pour n'inclure que celles où 100% du travail est effectué.
soln_distinct_teams <- soln_with_permutations %>% filter(assignment > 0) %>% group_by(rowname) %>% # Get team composition, alphabetical mutate(team = paste0(applicant, collapse = "")) %>% # Get allocation structure, descending arrange(-assignment) %>% mutate(allocation = paste0(assignment, collapse = "/")) %>% ungroup() %>% # Distinct teams / allocations only distinct(team, allocation) %>% arrange(allocation, team) %>% mutate(soln_num = row_number()) %>% # select(soln_num, team, allocation) %>% spread(allocation, soln_num)
Chaque rowname décrit une solution distincte en termes de répartition du travail entre les candidats, mais beaucoup sont des permutations où le travail est réparti différemment entre les mêmes équipes. Pour voir combien d'équipes différentes sont formées et combien de scénarios différents pourraient fonctionner pour cette équipe, j'étiquette chaque solution avec l'équipe (étiquetée par ordre alphabétique) et le scénario (étiqueté par part décroissante).
library(tidyverse) soln_with_permutations <- expand.grid(a,b,c,d,e,f,g,h) %>% # the Applicants come in as Var1, Var2... here, will rename below as.tibble() %>% rownames_to_column() %>% # This number tracks each row / potential solution # gather into long format to make summing simpler gather(applicant, assignment, -rowname) %>% # rename Var1 as "a", Var2 as "b", and so on. mutate(applicant = str_sub(applicant, start = -1) %>% as.integer %>% letters[.]) %>% group_by(rowname) %>% # keep only solutions adding to 100% filter(sum(assignment) == 100) %>% # keep only solutions involving four or fewer applicants filter(sum(assignment > 0) <= 4) %>% ungroup()
Je viens de relire la question et j'ai remarqué la nécessité d'utiliser quatre personnes ou moins. Pour ce faire, nous devons filtrer la solution 6 ci-dessus.
Cela produit des résultats indésirables. Si vous examinez votre sortie, vous verrez qu'il y a des résultats comme a b c et a c b (c'est-à-dire des permutations).
Vous avez de nombreux résultats en double (parlant en combinaisons). Essayez length (unique (apply (solution, 1, function (x) {paste0 (letters [sort (which (x> 0))], collapse = "")}))) ... il renvoie 138 (et non 645).
Il n'y a pas d'affectations dupliquées, si vous comptez différentes attributions d'heures dans la même équipe comme différentes solutions. solution%>% distinct (a, b, c, d, e, f, g, h) est toujours de 645 lignes.
En prenant votre sortie comme exemple avec le scénario 6: 30/30/20/20 , vous avez 2 54 30 30 20 20 qui correspond à abcd , 3 60 30 20 30 20 qui correspond à acbd et 4 62 20 30 30 20 qui correspond à cabd . Ceci est spécifiquement interdit par l'OP "" cdef "," cedf "," cfed "," cfde "etc. sont tous traités comme le même résultat" . Je vous suggère de jeter un œil à la sortie de ce que j'ai posté ci-dessus: apply (solution [ - 1], 1, function (x) {paste0 (letters [sort (which (x> 0))], collapse = "")}) . N'oubliez pas que l'ordre n'a pas d'importance avec les combinaisons.
Merci de me l'avoir signalé. Pour une raison quelconque, j'ai lu OP plusieurs fois en pensant que l'idée était d'éviter les solutions où un ensemble de candidats se voit attribuer les mêmes heures, mais cette solution est présentée dans un ordre différent. Maintenant mis à jour pour montrer qu'il n'y a que 132 "équipes" de 2-4 qui peuvent être créées, ce qui correspond au résultat de @ chinsoon12
Créer également toutes les combinaisons possibles comme la solution de Jon Spring mais en utilisant data.table et suppression du candidat dupe.
Si vos dimensions réelles sont par OP, vous pouvez envisager de développer toutes les combinaisons possibles et de supprimer les lignes où un candidat est dupliqué:
[[1]]
g50 g50
1: e f
2: e g
3: e h
4: f g
5: f h
6: g h
[[2]]
g50 g30 g20
1: e a b
2: e a c
3: e a d
4: e a f
5: e b a
---
128: h g b
129: h g c
130: h g d
131: h g e
132: h g f
[[3]]
g40 g40 g20
1: c d a
2: c d b
3: c d e
4: c d f
5: c e a
6: c e b
7: c e d
8: c e f
9: c f a
10: c f b
11: c f d
12: c f e
13: c g a
14: c g b
15: c g d
16: c g e
17: c g f
18: c h a
19: c h b
20: c h d
21: c h e
22: c h f
23: d e a
24: d e b
25: d e c
26: d e f
27: d f a
28: d f b
29: d f c
30: d f e
31: d g a
32: d g b
33: d g c
34: d g e
35: d g f
36: d h a
37: d h b
38: d h c
39: d h e
40: d h f
41: e f a
42: e f b
43: e f c
44: e f d
45: e g a
46: e g b
47: e g c
48: e g d
49: e g f
50: e h a
51: e h b
52: e h c
53: e h d
54: e h f
55: f g a
56: f g b
57: f g c
58: f g d
59: f g e
60: f h a
61: f h b
62: f h c
63: f h d
64: f h e
65: g h a
66: g h b
67: g h c
68: g h d
69: g h e
70: g h f
g40 g40 g20
[[4]]
g40 g30 g30
1: c a b
2: c a d
3: c a e
4: c a f
5: c a g
---
122: h d f
123: h d g
124: h e f
125: h e g
126: h f g
[[5]]
g40 g20 g20 g20
1: c a b d
2: c a b e
3: c a b f
4: c a d e
5: c a d f
6: c a e f
7: c b d e
8: c b d f
9: c b e f
10: c d e f
11: d a b c
12: d a b e
13: d a b f
14: d a c e
15: d a c f
16: d a e f
17: d b c e
18: d b c f
19: d b e f
20: d c e f
21: e a b c
22: e a b d
23: e a b f
24: e a c d
25: e a c f
26: e a d f
27: e b c d
28: e b c f
29: e b d f
30: e c d f
31: f a b c
32: f a b d
33: f a b e
34: f a c d
35: f a c e
36: f a d e
37: f b c d
38: f b c e
39: f b d e
40: f c d e
41: g a b c
42: g a b d
43: g a b e
44: g a b f
45: g a c d
46: g a c e
47: g a c f
48: g a d e
49: g a d f
50: g a e f
51: g b c d
52: g b c e
53: g b c f
54: g b d e
55: g b d f
56: g b e f
57: g c d e
58: g c d f
59: g c e f
60: g d e f
61: h a b c
62: h a b d
63: h a b e
64: h a b f
65: h a c d
66: h a c e
67: h a c f
68: h a d e
69: h a d f
70: h a e f
71: h b c d
72: h b c e
73: h b c f
74: h b d e
75: h b d f
76: h b e f
77: h c d e
78: h c d f
79: h c e f
80: h d e f
g40 g20 g20 g20
[[6]]
g30 g30 g20 g20
1: a b c d
2: a b c e
3: a b c f
4: a b d e
5: a b d f
---
221: g h c e
222: g h c f
223: g h d e
224: g h d f
225: g h e f
résultat: p >
scenarios <- list(c(50,50),
c(50,30,20),
c(40,40,20),
c(40,30,30),
c(40,20,20,20),
c(30,30,20,20))
lapply(scenarios,
function(scen) {
scen <- paste0("g", scen)
allcombi <- do.call(CJ, mget(scen, envir=.GlobalEnv))
setnames(allcombi, paste0("V", 1L:length(allcombi)))
nodupe <- allcombi[
allcombi[, .I[anyDuplicated(unlist(.SD)) == 0L],
by=1:allcombi[,.N]]$V1]
for(cols in split(names(nodupe), scen))
nodupe[, (cols) := sort(.SD), by=seq_len(nodupe[,.N]), .SDcols=cols]
ans <- unique(nodupe)
setnames(ans, scen)[]
})
Code et résultats de l'exécution pour les 6 scénarios:
g30 g30 g20 g20 1: a b c d 2: a b c e 3: a b c f 4: a b d e 5: a b d f --- 221: g h c e 222: g h c f 223: g h d e 224: g h d f 225: g h e f
résultat:
library(data.table)
g20 <- c("a","b","c","d","e","f")
g30 <- c("a","b","c","d","e","f","g","h")
g40 <- c("c","d","e","f","g","h")
g50 <- c("e","f","g","h")
scen <- paste0("g", c(30, 30, 20, 20))
allcombi <- do.call(CJ, mget(scen))
setnames(allcombi, paste0("V", 1L:length(allcombi)))
#remove rows with applicants that are repeated in different columns
nodupe <- allcombi[
allcombi[, .I[anyDuplicated(unlist(.SD)) == 0L],
by=1:allcombi[,.N]]$V1]
#sort within columns with the same percentage of work
for(cols in split(names(nodupe), scen))
nodupe[, (cols) := sort(.SD), by=seq_len(nodupe[,.N]), .SDcols=cols]
#remove identical combinations
ans <- unique(nodupe)
setnames(ans, scen)[]
Je ne pense pas que ce soit correct. Si vous triez chaque ligne et supprimez les doublons, vous n'obtiendrez que 70 combinaisons. N'oubliez pas que l'ordre n'a pas d'importance. Encore une fois, je ne suis pas sûr.
@JosephWood, merci, vous avez raison. J'ai groupé par cols, trie et supprime les dupes maintenant.
Je pense toujours que cette approche est incorrecte. Tout d'abord, cela produit toujours des résultats en double. Prenez par exemple le scénario 2, il devrait y avoir 96 résultats: length (unique (apply (t (apply (expand.grid (g50, g30, g20), 1, sort)), 1, paste0, collapse = "" ))) [1] 96 . Et si vous prenez votre résultat (la réponse de @JonSpring également), triez chaque ligne et supprimez les doublons, vous n'obtiendrez que 52 résultats: nrow (unique (t (apply (as.matrix (ans2 [[2]] ), 1, sort)))) ( ans2 est la sortie de votre lapply (scénarios, ... ).
quand je lance (unique (apply (t (apply (expand.grid (g50, g30, g20), 1, sort)), 1, paste0, collapse = ""))) , le premier l'élément est aae , ce qui n'est pas correct.
Je pense que c'est acceptable dans ce cas car a est à la fois dans g20 et g30 . Le fait est que nous ne produisons plus aae (ce que nous ne ferons pas car il n'y a qu'une seule possibilité). Un meilleur exemple serait comme eef . Puisque e et f se produisent dans g50 , g30 et g20 , il est possible pour produire eef , efe et fee .
Une chose que vous devez noter est que cela semble être un cas particulier de combinaison avec répétition. Il y avait un excellent article traitant de ce problème. Consultez cette question: Choisir des combinaisons non ordonnées dans des pools avec chevauchement . Notez que la réponse est loin d'être anodine.
Qu'à cela ne tienne, je viens de relire où l'OP déclare qu'ils recherchent des combinaisons sans remplacement car il serait impossible pour un candidat d'apparaître deux fois dans un scénario. Pourtant, c'est un problème net.
Je suis d'accord avec vos commentaires. le cas où vous avez évoqué est vraiment intéressant. sonne aussi comme un bon qn à publier. OP n'est pas très clair sur le fait que le demandeur effectue 2 parties du travail. J'utiliserais combn avec chaque pourcentage de travail dans votre cas
Je dirai une dernière chose. Regardez votre sortie pour [[3]] . La ligne 54 est 54: e h f et la ligne 64 64: f h e . Ceci doit être évité. Je ne connais pas assez bien data.table pour donner des conseils sur la manière de contourner ce problème.
oui, nous pouvons également supprimer les lignes dupliquées après avoir trié chaque ligne, mais je ne pense pas que cela atteindra ce que vous voulez.
Merci pour toute l'aide sur celui-ci! La solution de chinsoon12 a été la plus utile pour moi. Comme indiqué, cette solution renvoyait encore des doublons (dans les scénarios 40/40/20 ou 40/30/30, elle ne supprimait pas les doublons où le pourcentage apparaissait deux fois dans le scénario).
Bien que ce ne soit peut-être pas la solution la plus élégante , J'ai modifié la solution de chinsoon12. En utilisant 40/40/20 comme exemple, j'ai d'abord créé toutes les combinaisons possibles de 40/40 puis créé les combinaisons de 40/40 et 20. J'ai ensuite pu supprimer avec précision les doublons.
# Create 40/40 combos
combs_40 <- t(combn(g40,2))
c40 <- paste0(combs_40[,1],combs_40[,2])
# Create combos of 40/40 and 20
scen <- c("c40","g20")
allcombi <- do.call(CJ, mget(scen, envir=.GlobalEnv))
allcombi <- as.data.frame(allcombi)
# Split into cols
x <- t(as.data.frame(strsplit(allcombi$c40,split="")))
allcombi <- as.data.table(cbind(x[,1],x[,2],allcombi$g20))
setnames(allcombi, paste0("V", 1L:length(allcombi)))
# Remove rows with applicants that are repeated in different columns
nodupe <- allcombi[
allcombi[, .I[anyDuplicated(unlist(.SD)) == 0L],
by=1:allcombi[,.N]]$V1]
# Redefine scen
scen <- c("g40","g40","g20")
# Sort within columns with the same percentage of work
for(cols in split(names(nodupe), scen))
nodupe[, (cols) := sort(.SD), by=seq_len(nodupe[,.N]), .SDcols=cols]
# Set names, write results
setnames(nodupe, scen)[]
results_404020 <- nodupe
Je suis encore un peu confus. Si vous regardez votre sortie, il y a encore des valeurs en double. Prenons par exemple la 3e ( cde ), la 7e ( ced ) et la 11e ligne ( dec ) de results_404020 . Ce sont toutes des permutations, ce que je pensais être évité.
Oui, bien que ce soient des permutations, vous devez tenir compte de la différence des pourcentages. Si j'attribuais un tiers du travail à chacun, vous auriez raison, car toute permutation aurait le même résultat final (chaque candidat obtient 33,3%). Ici cependant, les deux premiers obtiennent 40% chacun, et les 20 derniers%. Par conséquent, cde et ced sont différents, mais cde et dce sont identiques.
pouvez-vous partager avec nous la dimension réelle de votre problème?
Doit-on comprendre que le candidat
aest prêt à travailler 20% ou 30%, mais pas 40% ou 50%? J'ai utilisé cette contrainte pour ma réponse, mais je ne sais pas si c'était la bonne interprétation.Oui c'est correct. Certaines personnes n'ont que la capacité de faire de petites portions de travail, d'autres ne veulent faire que beaucoup de travail. D'autres encore sont prêts à faire tout le travail qu'ils peuvent obtenir.
Ne serait-il pas permis d'attribuer 20% de travail chacun à cinq personnes, par exemple abcde ou bcdef? Vous ne l'avez pas inclus dans vos six scénarios, mais je ne savais pas si c'était intentionnel ou non.
C'était intentionnel. Avoir quatre personnes ou moins facilite la gestion et le contrôle du flux de travail.Par conséquent, 20/20/20/20/20 n'est pas une option valable pour moi.
@ user10892378 alors vous voulez également savoir quels candidats ont été affectés à quelles parties du travail?