Numero di combinazioni / permutazioni semi-casuali dato un insieme di vincoli

Question

Numero di combinazioni / permutazioni semi-casuali dato un insieme di vincoli

#1 da (4 voti)

8

Sfondo:

Ci sono circa 60 studenti nel collegio per cui lavoro. Il consulente ha chiesto alla mia collega e a me di escogitare un modo migliore per organizzare i posti a sedere per la cena che a mano. Vorrebbe incarichi per il resto dell'anno scolastico. Ci ha anche chiesto di provare a risolvere alcuni dei problemi di cui ha sentito parlare da studenti e docenti.

Vincoli:

La maggior parte degli studenti non proviene dagli Stati Uniti, quindi quando sono circondati da persone della stessa nazionalità (cioè a tavola), parlano la lingua in cui parlano fluentemente, invece di praticare l'inglese,
I reclami vengono fatti quando gli studenti si sono seduti a un certo tavolo "troppi" volte nel complesso,
o se si siedono allo stesso tavolo più di due volte di fila,
e alcuni studenti non vanno d'accordo, quindi non possono sedersi insieme.

ingresso:

In fase di esecuzione, il programma viene fornito con:

Un gruppo di persone,
Un insieme di tabelle e
Ogni tabella ha un diverso numero di postazioni (è consentita la ripetizione)

La dimensione di entrambi i set e le dimensioni di ogni tabella non cambiano tra ogni assegnazione.

Test:

Sto utilizzando 18 persone di nazionalità diverse e 4 tabelle da 3 a 6, inclusi. Ho scelto numeri che pensavo avesse senso per quel set di dati:

Non più di 3 persone della stessa nazionalità possono sedersi insieme in un momento
Nessuno può sedersi a un tavolo più di 4 volte

Risultati:

Ho eseguito il generatore circa 15 volte senza modificare i dati di input. Ogni volta, arriva da 6 a 12 "settimane" di incarichi.

Domande:

(almeno fino al più importante)

Perché ricevo un numero diverso di assegnazioni generate ogni volta che eseguo il programma? Il set di dati non cambia tra le esecuzioni.
Come trovo il ...
- numero minimo di persone della stessa nazionalità che possono sedere in una determinata tabella,
- numero minimo di volte complessive in cui si siedono su una data tabella, per tutto
- massimizzare il numero di assegnazioni generate?
Come garantisco che questi siano effettivamente i numeri corretti?

Modifica:

Ogni volta che creo un nuovo compito, chiamo Collections.shuffle(List) nell'elenco delle persone per rendere casuale il loro ordine. Passo quindi l'elenco di tabelle e persone a un metodo di backtracking basato su l'implementazione di otto regine di kapilid su github per assegnare le persone ai tavoli.

algorithms

posta Matthew D 20.12.2012 - 16:48

fonte

1 risposta

Leggi altre domande sui tag algorithms

Il "letterale stringa" è sempre uguale a "stringa hardcoded"? [chiuso] L'esperienza del programmatore può essere espressa in ore di codice come ore di volo per un pilota? [chiuso]

score 4 · Accepted Answer

Aggiornamento:

Mi sono reso conto che non rispondevo direttamente alle tue domande. Suppongo che aiuti a leggere tutti della domanda prima di sparare una risposta ...

Non si specifica quale algoritmo si sta utilizzando per generare le disposizioni dei posti. Presumibilmente vi è qualche elemento di variabilità / casualità al fine di creare diversi incarichi per la durata del termine. Quella casualità è molto probabilmente la ragione per cui ottieni risultati diversi per ogni corsa. Lo segnerei come working as designed invece di un bug.
a. Non si specifica l'algoritmo, quindi non lo sappiamo veramente. Inoltre, non conosciamo i conteggi per ogni nazionalità. Con la logica semplice, 0 o 1 sarebbe il minimo assoluto a una tabella, ma sospetto che non sia molto utile per te. In definitiva dipende dal numero di ogni nazionalità e dal modo in cui popolano le altre tabelle.
b. Esegui il tuo programma, pubblica i risultati in un database o foglio di calcolo e contali. O modificare il programma per tenere traccia di quelle cose.
c. La risposta qui dipenderà dal numero di ogni nazionalità e dagli altri vincoli che hai fornito. Anche le dimensioni della tabella influiscono su di essa. La risposta a questa parte è in realtà solo una moltiplicazione del numero di potenziali permutazioni. Fortunatamente (per me) questo è un sito sulla programmazione, non sulle statistiche.
Hai due problemi da affrontare qui. Innanzitutto, convalida che i tuoi vincoli riflettono accuratamente la realtà della situazione. Parla con il consulente per verificare che i tuoi vincoli siano corretti. In secondo luogo, verificare i risultati soddisfa i tuoi limiti. Scrivi alcuni metodi che controllano i grafici dei posti a sedere restituiti per i vincoli che hai fornito. E / o ispezionare manualmente i grafici per verificare che siano a posto.

Questa domanda SO ha una domanda simile e suggerisce che questo è equivalente a bin problema di imballaggio o il problema dello zaino

Questa domanda SO Gli ospiti dei posti sulla base di parametri prioritari sembrano rispondere esattamente a ciò che stai cercando.

Questa domanda SO illustra i problemi che l'autore ha avuto nel risolvere questo problema usando l'algoritmo di bin-packing. Ti suggerisco di leggere le risposte per avere una visione più chiara su come aggirarle.

E per il riferimento obbligatorio xkcd, ecco un link dai loro forum che parlano di posti a sedere pianificare l'ottimizzazione e utilizzare un algoritmo genetico modificato per risolvere il problema.

Se questo è uno scenario reale, allora buona fortuna. E se questo è solo un compito, allora hai materiale più che sufficiente per farti andare avanti.