Fair 2-combinazioni

Question

Fair 2-combinazioni

#1 da (1 voti)
#2 da (0 voti)

1

Devo assegnare in modo imparziale 2 esperti di x esperti ( x è piuttosto piccolo - meno di 50) per ogni n di domande, in modo che:

ogni esperto ha lo stesso numero di applicazioni (+ -1);
ogni coppia di esperti (2-combinazione di x ) ha lo stesso numero di applicazioni (+ -1);

È semplice generare tutte le 2 combinazioni:

for (i=0; i<n; i++) {
  for (j=i+1; j<n; j++) {
    combinations.append(tuple(i,j));
  }
}

Ma per assegnare gli esperti in modo equo ho bisogno di assegnare una combinazione a un'applicazione per correggere l'ordine, ad esempio:

experts: 0 1 2 3 4

fair combinations:
     counts
     01234

01   11000
23   11110
04   21111
12   22211
34   22222
02   32322
13   33332
14   34333
03   44343
24   44444

Non riesco a trovare un buon algoritmo per questo (il migliore che ho trovato è piuttosto complicato e con O(x⁴) complessità). Potresti aiutarmi?

algorithms

posta Tometzky 03.07.2013 - 15:58

fonte

2 risposte

Leggi altre domande sui tag algorithms

È possibile utilizzare 2 moduli Python rilasciati con licenza LGPL e BSD in un programma? Prova di pagamento PayPal: è necessario archiviarla sul nostro server?

score 1 · Answer 1

Hai solo bisogno di scorrere le coppie possibili in un ordine che garantisce che il conteggio dell'utilizzo per ogni persona differisca di non più di uno. Questo è lo stesso problema della generazione di abbinamenti per un torneo round robin. Se hai un numero pari di persone, una tecnica semplice per generare abbinamenti è organizzarli in due file. Tieni ferma la persona in alto a sinistra e ruota il resto.

1) a b c
   f e d

2) a c d
   b f e

3) a d e
   c b f

4) a e f
   d c b

5) a f b
   e d c

In ogni ciclo, "a" è fisso e le altre persone ruotano. Leggi gli accoppiamenti in verticale. Quindi dovresti scorrere gli abbinamenti come segue:

af be cd ab cf de ac bd ef ...

Con un numero dispari di persone, lascia vuota la casella fissa e ignora quella colonna.

score 0 · Answer 2

Ecco alcune riflessioni e idee, anche se nessun codice:

Dato x experts , n applications e each expert has the same number of applications (+-1) , puoi banalmente ricavare che ogni esperto apporterà media% di% di applicazioni. Se questa è una frazione, alcuni esperti si radunano e gli altri si arrotondano.

Quindi definisci (n/x) Questi sono i tuoi unici valori consentiti per il numero di applicazioni di ciascun esperto. Inoltre, sai che tutti i a = floor(n/x); b = a+1; e a combinati devono sommare a b .

Quando scegli le tuple, devi semplicemente abbinare ciascun esperto di n con un esperto di a fino a quando non finisci l'uno o l'altro, quindi abbina il resto.