Come generare (in modo efficiente) set disgiunti mentre le coppie di elementi usanti una sola volta?

Question

Quello che vorrei fare è dividere un gruppo di (n) elementi in gruppi di uguali dimensioni (gruppi di dimensioni m, e per semplicità supponiamo che non ci sono avanzi, cioè n è divisibile di m). Facendo questo più volte, vorrei assicurarmi che nessun paio di elementi sia nello stesso gruppo insieme due volte.

per rendere questo un po 'più concreto, per la costruzione di gruppi di due dei sei elementi A..F, una volta potrebbe partizionare il set per cinque volte in modi diversi:

• (A, B), (C, D), (E, F)
• (A, C), (B, E), (D, F)
• (A, D), (B, F), (C, E)
• (A, E), (B, D), (C, F)
• (A, F), (B, C), (D, E)

Lo stesso gruppo di elementi può essere partizionato sola volta in gruppi di tre colpo coppie sovrapposte:

• (A, B, C), (D, E, F)

_{(As @DavidHam gli uomini sottolineano di seguito, ci sono diversi modi di rendere la partizione in questo esempio. Tuttavia, dopo aver creato la partizione una volta, non c'è mai un'altra suddivisione, che mantiene separate tutte le coppie di oggetti. C'è un modo: - Va bene la mia applicazione non necessita di generare tutte possibilmente modi di partizionamento del set a livello globale, una soluzione incontro i vincoli faranno)}

---

La mia domanda, ora, è questo di farlo in modo efficiente? Ci sono trucchi per accelerare la generazione di questi set?

Quindi, finora, ho considerato questo come un problema exact cover e lo risolvo con un backtracking algorithm (una variante di DLX). Questo funziona molto bene per le coppie, ma man mano che i gruppi diventano più grandi il numero di possibilità che l'algoritmo deve considerare esplode, e l'elaborazione diventa molto ingombrante.

Quello che sto cercando sono i trucchi per velocizzare le cose. Tutte le idee sono i benvenuti, in particolare (ma non solo):

• Ottimizzazioni e euristica per ridurre il numero di possibilità che devono essere considerati prima di risolvere (ad esempio, è chiaro dagli esempi sopra che la prima divisione può essere fatta semplicemente arbitrariamente, e la prima serie di ciascuna partizione [la prima colonna sopra] può essere generata automaticamente).
• Esistono varianti di backtracking che possono far fronte a enormi quantità di candidati? (non avendo bisogno di generare tutte le possibilità in anticipo)
• Altri algoritmi , approcci o concetti matematici che dovrei considerare?

Qualsiasi idea e suggerimento è molto gradita. Grazie mille per aver considerato questo!

---

Aggiornamento

Ok, quindi questo è stato un po ', ma ho speso molto più tempo su questo e voleva tornare a voi. @ david-eisenstat mi ha messo sulla strada giusta dandomi il termine di ricerca corretto (grazie mille!) - Da allora ho letto abbastanza sul problema del golfista sociale.

Una delle migliori risorse che ho trovato, che mi piacerebbe condividere qui, è il lavoro di Markus Triska, che discute diversi approcci (e poi continua a presentare un algoritmo molto carino) nella sua tesi. Questo è altamente raccomandato se qualcuno si imbatte in un problema simile!

Answer 1

Questo problema viene studiato con il nome Social Golfer Problem. La letteratura ha dimensioni non banale, ma ci sono tre approcci principali:

1. locali metodi di ricerca, in grado di gestire i casi in cui molte coppie non sono presenti.

2. Metodi di ricerca completi come la riduzione per la copertura esatta. Da quello che ricordo, la ricerca qui ruota attorno a metodi efficienti per la rottura della simmetria, di cui la tua idea di fissare la prima riga è probabilmente la più semplice.

3. Costruzioni matematiche. Quando q è una potenza primaria, esiste una costruzione per q gruppi di q che coinvolge lo finite affine planes che non è troppo difficile da implementare. Oltre a questo, ci sono molte costruzioni uniche. Il manuale dei disegni combinatori è probabilmente la soluzione migliore per riassumere ciò che è noto.

Answer 2

Lasciate n=m*k, la partizione ha m gruppi con k elementi.

Dopo le partizioni x, ogni articolo è in un gruppo con x*(k-1) altri elementi. Dopo aver creato t-1 partizioni, nel prossimo partizione A può scegliere di:

second element : n - (t-1)*(k-1) - 1 items 
third element : n - 2*(t-1)*(k-1) - 2 items 
fourth element : n - 3*(t-1)*(k-1) - 3 items 
... 
k'th element : n - (t-1)*(k-1)^2 - (k-1) items 

Per creare t'th partizione abbiamo bisogno:

n - (t-1)*(k-1)^2 - (k-1) > 0 
=> 
t < (n - k + 1)/((k-1)^2) + 1 

numero di possibili partizioni diminuisce con il quadrato della lunghezza del gruppo. Ciò significa che non ci sono troppe partizioni possibili :-)

Vorrei andare con un approccio avido. Memorizza per ciascun set di articoli che sono disponibili e crea una nuova partizione aggiungendo il primo elemento disponibile a un gruppo.