Ciclo attraverso diversi set di permutazioni uniche

Question

Ho difficoltà a iniziare il codice di layout per questo problema.

Ho una quantità fissa di numeri casuali, in questo caso 8 numeri. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Che verranno posizionati in 3 serie di numeri, con il solo vincolo che ogni set contenga almeno un valore, e ogni valore può essere utilizzato solo una volta. Edit: tutte le 8 numeri devono essere utilizzati

Ad esempio:

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

Ho bisogno di scorrere tutte le possibili combinazioni di un set R1, R2, R3. Ordine non è importante, per cui se l'esempio precedente successo, non ho bisogno

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

Che cos'è un buon metodo?

Answer 1

Probabilmente non è l'approccio migliore ma dovrebbe funzionare.

determinare il numero di combinazioni di tre numeri che somma a 8:

1,1,6 
1,2,5 
1,3,4 
2,2,4 
2,3,3 

Per trovare quanto sopra ho iniziato con:

6,1,1 then subtracted 1 from six and added it to the next column... 
5,2,1 then subtracted 1 from second column and added to next column... 
5,1,2 then started again at first column... 
4,2,2 carry again from second to third 
4,1,3 again from first... 
3,2,3 second -> third 
3,1,4 

sapendo che meno della metà è 2 tutte le combinazioni devono essere stati trovato ... ma dato che la lista non è lunga, potremmo anche andare fino in fondo.

Ora ordina ogni elenco di 3 dal più grande al meno (o viceversa) Ora ordina ogni elenco di 3 l'uno relativo all'altro. Copia ogni elenco univoco in un elenco di elenchi univoci. Ora abbiamo tutte le combinazioni che aggiungono a 8 (cinque liste penso).

Ora consideriamo un elenco nel set sopra

6,1,1 tutte le possibili combinazioni sono trovati da:

8 accompagnamento 6, (poiché abbiamo scelto sei c'è solo 2 rimasti cui scegliere) 2 scegli 1, 1 scegli 1 che funziona a 28 * 2 * 1 = 56, vale la pena conoscere quante possibilità ci sono in modo da poter testare.

n scegliere r (scegliere gli elementi R da opzioni n totale)

n C r = n!/[(n-r)! r!]

Così ora avete il numero totale di iterazioni per ogni componente della lista per il primo è il 28 ...

Bene raccogliendo 6 elementi da 8 è lo stesso di creare una lista di 8 meno 2 elementi, ma quali due elementi?

Bene se rimuoviamo 1,2 che ci lascia con 3,4,5,6,7,8. Consideriamo tutti i gruppi di 2 ... A partire da 1,2 il successivo sarebbe 1,3 ... quindi il seguente è letto colonna per colonna.

12 
13 23 
14 24 34 
15 25 35 45 
16 26 36 46 56 
17 27 37 47 57 67 
18 28 38 48 58 68 78 

Riassumendo ciascuna delle colonne sopra ci dà 28. (quindi questo coperti solo la prima cifra della lista (6,1,1) ripetere la procedura per la seconda cifra (uno) che è "2 Scegli 1 "Così di sinistra su due cifre dalla lista sopra ne scegliamo una delle due e poi per l'ultima ne prendiamo la rimanente

So che questo non è un algoritmo dettagliato ma spero che sarai in grado per iniziare

Answer 2

Generare tutte le combinazioni di sottoinsiemi ricorsivamente nel modo classico Quando si raggiunge il punto in cui il numero di elementi rimanenti è uguale al numero di sottoinsiemi vuoti, quindi limitati solo ai sottoinsiemi vuoti.

Ecco un'implementazione di Python:

def combinations(source, n): 
    def combinations_helper(source, subsets, p=0, nonempty=0): 
    if p == len(source): 
     yield subsets[:] 
    elif len(source) - p == len(subsets) - nonempty: 
     empty = [subset for subset in subsets if not subset] 
     for subset in empty: 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+1): 
      yield combination 
     subset.pop() 
    else: 
     for subset in subsets: 
     newfilled = not subset 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled): 
      yield combination 
     subset.pop() 

    assert len(source) >= n, "Not enough items" 
    subsets = [[] for _ in xrange(n)] 
    for combination in combinations_helper(source, subsets): 
    yield combination 

E un test:

>>> for combination in combinations(range(1, 5), 2): 
... print ', '.join(map(str, combination)) 
... 
[1, 2, 3], [4] 
[1, 2, 4], [3] 
[1, 2], [3, 4] 
[1, 3, 4], [2] 
[1, 3], [2, 4] 
[1, 4], [2, 3] 
[1], [2, 3, 4] 
[2, 3, 4], [1] 
[2, 3], [1, 4] 
[2, 4], [1, 3] 
[2], [1, 3, 4] 
[3, 4], [1, 2] 
[3], [1, 2, 4] 
[4], [1, 2, 3] 
>>> len(list(combinations(range(1, 9), 3))) 
5796 

Answer 3

ho di fronte a me Knuth Volume 4, Fascicle 3, Generazione di tutte le combinazioni e le partizioni, sezione 7.2 .1.5 Generazione di tutte le partizioni impostate (pagina 61 in fascicolo).

Prima ha dettagli algoritmo H, stringhe di crescita limitato in modo lessicografico a causa di George Hutchinson. Sembra semplice, ma non ho intenzione di immergermi in esso solo ora.

Nella pagina successiva in un'elaborazione codici Gray per le partizioni set medita:

Supponiamo, tuttavia, che non ci interessa tutte delle partizioni; potremmo volere solo quelli che hanno blocchi m. Possiamo farlo attraverso la collezione più piccola di stringhe di crescita limitata, cambiando ancora una cifra alla volta?

Quindi descrive una soluzione a causa di Frank Ruskey.

La soluzione semplice (e certo di essere corretto) è codificare filtraggio Algoritmo H su partizioni dove m==3 e nessuna delle partizioni sono l'insieme vuoto (secondo i vincoli dichiarati). Sospetto che Algorithm H sia estremamente veloce, quindi il costo del filtro non sarà grande.

Se si sta implementando questo su un 8051, è possibile iniziare con l'algoritmo Ruskey e quindi filtrare solo sulle partizioni contenenti il ​​set vuoto.

Se si sta implementando questo su qualcosa di più piccolo di un argomento 8051 e millisecondi, è possibile seminare ciascuna delle tre partizioni con un elemento univoco (un semplice ciclo annidato di tre livelli) e quindi aumentare mediante il partizionamento sul resto cinque elementi per m==3 utilizzando l'algoritmo di Ruskey. Non dovrai filtrare nulla, ma devi tenere traccia di quali cinque elementi rimangono alla partizione.

La cosa bella del filtraggio giù dall'algoritmo generale è che non è necessario verificare alcuna intelligenza propria e si cambia idea in seguito sui propri vincoli senza dover rivedere la propria intelligenza.

Potrei persino lavorare a una soluzione più tardi, ma per ora è tutto.

P.S. per i guppies Java: ho scoperto la ricerca su "George Hutchison stringhe di crescita limitata" un certo pacchetto ca.ubc.cs.kisynski.bell con documentazione per il metodo growthStrings() che implementa l'algoritmo di Hutchison.

sembra essere disponibile presso http://www.cs.ubc.ca/~kisynski/code/bell/

Answer 4

Accendere il problema su di essa la testa e troverete una soluzione straight-forward. Hai 8 numeri che ciascuno deve essere assegnato esattamente a un gruppo; La "soluzione" è solo una soluzione se almeno un numero è stato assegnato a ciascun gruppo.

L'attuazione banale comporterebbe 8 per i loop ea pochi IF (pseudocodice):

for num1 in [1,2,3] 
    for num2 in [1,2,3] 
    for num3 in [1,2,3] 
     ... 
     if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3)) 
      Print Solution! 

Esso può anche essere implementato in modo ricorsivo, utilizzando due array e un paio di funzioni. Molto più bello e più facile da eseguire il debug/follow (pseudocodice):

numbers = [1, 2, 3, 4, 5, 6, 7, 8] 
positions = [0, 0, 0, 0, 0, 0, 0, 0] 

function HandleNumber(i) { 
    for position in [1,2,3] { 
    positions[i] = position; 
    if (i == LastPosition) { 
     // Check if valid solution (it's valid if we got numbers in all groups) 
     // and print solution! 
     } 
    else HandleNumber(i+1) 
    }  
} 

La terza realizzazione userebbe senza ricorsione e un po 'di backtracking. Pseudocodice, ancora:

numbers = [1,2,3,4,5,6,7,8] 
groups = [0,0,0,0,0,0,0,0] 

c_pos = 0 // Current position in Numbers array; We're done when we reach -1 
while (cpos != -1) { 
    if (groups[c_pos] == 3) { 
     // Back-track 
     groups[c_pos]=0; 
     c_pos=c_pos-1 
    } 
    else { 
    // Try the next group 
    groups[c_pos] = groups[c_pos] + 1 
    // Advance to next position OR print solution 
    if (c_pos == LastPostion) { 
     // Check for valid solution (all groups are used) and print solution! 
     } 
    else 
     c_pos = c_pos + 1 
    } 
}