Algoritmo di assegnazione di gruppo settimanale

Un mio amico chi è un insegnante ha 23 studenti in una classe. Vogliono un algoritmo che assegni gli studenti a gruppi di 2 e un gruppo di 3 (gestire il numero dispari di studenti) per 14 settimane in modo che non si ripetano due coppie nelle 14 settimane (una coppia viene assegnata a una settimana).Algoritmo di assegnazione di gruppo settimanale

Un approccio a forza bruta sarebbe troppo inefficiente, quindi stavo pensando ad altri approcci, la rappresentazione di matrice suona accattivante e la teoria dei grafi. Qualcuno ha qualche idea? I problemi che ho potuto trovare riguardano solo 1 settimana e this answer che ho potuto capire.

fonte

2013-03-07 mihajlv

Si prega di chiarire - "non si ripetono due coppie per le 14 settimane" - coppie diverse ogni giorno o coppie diverse ogni settimana? – Serg

Le coppie @Serg vengono assegnate su base settimanale. – mihajlv

Round-robin algorithm farà il trucco credo.

Aggiungere lo studente rimanente al secondo gruppo e il gioco è fatto.

First run 
1 2 3 4 5 6 7 8 9 10 11 12 
23 22 21 20 19 18 17 16 15 14 13 

Second run 
1 23 2 3 4 5 6 7 8 9 10 11 
22 21 20 19 18 17 16 15 14 13 12

...

fonte

2013-03-07 15:29:32 solidrevolution

+1 Molto più elegante degli altri suggerimenti, oltre a liste iniziali randomizzate ci forniranno accoppiamenti casuali. –

La migliore soluzione qui: stai collegando una pagina che spiega l'algoritmo in modo che possano implementarlo da soli e mostrare l'esempio delle corse in modo che il risultato finale sia chiaro. –

@solidrevolution Funziona solo con un numero pari di studenti. Il numero dispari di studenti non funziona provato a confrontare l'ultimo con il secondo gruppo e molti altri modi in cui non ha funzionato, ma grazie per la risposta. – mihajlv

-1

Provare a descrivere il problema in termini di vincoli.

Quindi passare i vincoli a uno strumento come ECLiPSe (non Eclipse), vedere http://eclipseclp.org/.

In realtà, il problema sembra simile a quello dell'esempio Golf su quel sito (http://eclipseclp.org/examples/golf.ecl.txt).

fonte

2013-03-07 14:18:23 Patrick

Hm, la programmazione dei vincoli di intero non ha tempi di esecuzione piuttosto abissali? Pensavo di aver ricordato qualcosa lì. –

Non necessariamente. Gli ambienti di programmazione dei vincoli hanno regole per condurre l'applicazione alla soluzione, piuttosto che utilizzare l'approccio a forza bruta che semplicemente scorre su tutte le dimensioni. Per esempio. nel problema 8-queen, il motore del vincolo in genere esegue il ciclo sulla dimensione con il dominio risultante più piccolo. – Patrick

-1

Iniziare con un set (forse una mappatura bitset per gli studenti per un minor consumo di memoria) per ogni studente che ha tutti gli altri studenti in esso. Ripeti 14 volte, selezionando ogni volta 11 studenti (per gli 11 gruppi che formerai) per i quali sceglierai partner. Per ogni studente, scegli un partner con il quale non hanno ancora fatto parte di un gruppo. Per uno studente a caso di questi 11, scegli un secondo partner, ma assicurati che nessuno studente abbia meno partner rimanenti di quanti ne siano rimasti. Per ogni scelta, regola i set.

fonte

2013-03-07 14:18:53

-1

Ecco un esempio in Haskell che produrrà gruppi di 14 11-pair combinazioni non multipli. Il valore 'coppie' è tutte le combinazioni di coppie da 1 a 23 (ad es. [1,2], [1,3] ecc.). Quindi il programma crea elenchi in cui ogni lista contiene 14 elenchi di 11 coppie (scegliendo dal valore 'coppie') in modo tale che nessuna coppia venga ripetuta e nessun numero singolo venga ripetuto in una lista di 11 coppie. Spetta a te semplicemente posizionare l'ultimo studente mancante per ogni settimana come meglio credi. (Ci sono voluti circa tre minuti per calcolare prima che cominciasse a risultati di output):

import Data.List 
import Control.Monad 

pairs = nubBy (\x y -> reverse x == y) 
     $ filter (\x -> length (nub x) == length x) $ replicateM 2 [1..23] 

solve = solve' [] where 
    solve' results = 
    if length results == 14 
     then return results 
     else solveOne [] where 
     solveOne result = 
      if length result == 11 
       then solve' (result:results) 
       else do next <- pairs 
         guard (notElem (head next) result' 
          && notElem (last next) result' 
          && notElem next results') 
         solveOne (next:result) 
         where result' = concat result 
           results' = concat results

Un campione dall'output:

[[[12,17],[10,19],[9,18],[8,22],[7,21],[6,23],[5,11],[4,14],[3,13],[2,16],[1,15]], 
[[12,18],[11,19],[9,17],[8,21],[7,23],[6,22],[5,10],[4,15],[3,16],[2,13],[1,14]], 
[[12,19],[11,18],[10,17],[8,23],[7,22],[6,21],[5,9],[4,16],[3,15],[2,14],[1,13]], 
[[15,23],[14,22],[13,17],[8,18],[7,19],[6,20],[5,16],[4,9],[3,10],[2,11],[1,12]], 
[[16,23],[14,21],[13,18],[8,17],[7,20],[6,19],[5,15],[4,10],[3,9],[2,12],[1,11]], 
[[16,21],[15,22],[13,19],[8,20],[7,17],[6,18],[5,14],[4,11],[3,12],[2,9],[1,10]], 
[[16,22],[15,21],[14,20],[8,19],[7,18],[6,17],[5,13],[4,12],[3,11],[2,10],[1,9]], 
[[20,21],[19,22],[18,23],[12,13],[11,14],[10,15],[9,16],[4,5],[3,6],[2,7],[1,8]], 
[[20,22],[19,21],[17,23],[12,14],[11,13],[10,16],[9,15],[4,6],[3,5],[2,8],[1,7]], 
[[20,23],[18,21],[17,22],[12,15],[11,16],[10,13],[9,14],[4,7],[3,8],[2,5],[1,6]], 
[[19,23],[18,22],[17,21],[12,16],[11,15],[10,14],[9,13],[4,8],[3,7],[2,6],[1,5]], 
[[22,23],[18,19],[17,20],[14,15],[13,16],[10,11],[9,12],[6,7],[5,8],[2,3],[1,4]], 
[[21,23],[18,20],[17,19],[14,16],[13,15],[10,12],[9,11],[6,8],[5,7],[2,4],[1,3]], 
[[21,22],[19,20],[17,18],[15,16],[13,14],[11,12],[9,10],[7,8],[5,6],[3,4],[1,2]]]

fonte

2013-03-07 16:59:19

Ora spiega quale algoritmo sta usando e esattamente quello che sta facendo. –

Un'altra possibilità potrebbe essere sarebbero necessari graph matching, 14 distinti abbinamenti grafico.

fonte

2013-03-08 14:43:15 mihajlv

Algoritmo di assegnazione di gruppo settimanale

risposta

Problemi correlati