Ridurre la permutazione

Question

Ho bisogno di un algoritmo in grado di mappare le esecuzioni in una permutazione su un singolo numero, ma anche di ridurre i numeri successivi.

Quindi una corsa è un insieme sequenziale di numeri in una permutazione che è ordinata e in ordine. Nell'elenco, 1; 2; 3; 5; 6; 4 ci sono due piste, 1; 2; 3 e 5; 6. Voglio sostituirli con un singolo numero, un minimo, quindi se, dopo aver rimosso le esecuzioni, abbiamo una permutazione di 4 elementi, la permutazione usa i numeri 1 ... 4. In quanto sopra, dobbiamo ridurre le due esecuzioni . la prima corsa sarebbe 1, 4 trasforma in 2 e [5; 6] trasforma in 3, per mantenere il secondo criterio. Se ordino la permutazione ridotta, quindi espando gli elementi all'interno della mappatura e ordina la permutazione originale otterrò lo stesso risultato. La permutazione risultante non dovrebbe avere esecuzioni al suo interno.

Ad esempio (ho evidenziato le piste):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

per ora, sto passando sopra l'elenco e sto creando un elenco di elenchi, raggruppando le corse. In realtà la seconda parte è la parte difficile per fare una soluzione pulita. Ho pensato all'approccio ingenuo, curioso se qualcuno ha qualche trucco intelligente che può farlo meglio del mio, sono come O (2n + n log n),

• sostituzione delle corse con l'elemento head della corsa e inserimento di tali dati in una tabella hash (per recuperabilità)
• ordinamento per creare una mappa con le cifre mancanti con l'indice ordinato. [1; 6; 5; 4] produrrebbe [(1,1); (4,2); (5,3); (6,4)]
• sostituendo l'elenco nel passaggio 1 con la mappa creata nel passaggio 2 e aggiornando l'hashtable per la traduzione.

scorrendo un esempio, di nuovo:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Se ordino questa permutazione e ricostruisco: [1; 2; 3; 4], 3 - > 3; 4 e 4 - > 5; 6 ottengo, 1; 2; 3 ; 4; 5; 6. Ordinati anche.

Sto usando le liste, quindi sarebbe preferibile un approccio funzionale. Nessun codice necessario Tutte le idee, ovviamente, sono benvenute.

EDIT:

  

mweerden:

     

    

Non mi è chiaro quali siano le condizioni precise sulla mappatura. Perché esattamente non è permesso produrre solo la permutazione [1,2, ..., N] per una permutazione con N esecuzioni? Sembra che tu preferisca mappare una corsa su un numero da quella corsa, ma (dato che ciò non è sempre possibile) sembra permetterti un po 'di libertà. & # 8211;

  

Non preferisco mappare una corsa su un numero all'interno di quella corsa (guarda sopra!), ma devo conservare un ordinamento . La permutazione [1; 2; 3 ... N] è una corsa e quindi può essere ulteriormente ridotta. Ecco perché non è valido. L'ordine avrà importanza in ulteriori operazioni in un altro algoritmo, ma i singoli elementi possono essere espansi alla fine per salvare la permutazione originale.

Answer 1

Notazione:

• il conteggio inizia da 1
• l.i è l'elemento i dell'elenco l
• l+m è la concatenazione degli elenchi m e [n,n+1,n+2,...,m]
• una corsa è un elenco secondario massimo che è un elenco n per alcuni n <= m e p con [1,2,...,N]

Quindi ci viene data una permutazione r_1,r_2,...,r_M dell'elenco p = r_1+r_2+...+r_M. Dividiamo q in serie [1,2,...,M] in modo che r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N]. Stiamo quindi cercando una permutazione p = [1,3,4,2,5,6] di N=6 tale che M=4.

Ad esempio, se r_1 = [1], abbiamo r_2 = [3,4], r_3 = [2], r_4 = [5,6], [1,3,2,4], r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6] e i < M. In questo caso è necessario q.i + 1 = q.(i+1) essere r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) come r_(q.i)+r_(q.i + 1).

Si noti che r_(q.i) non può contenere esecuzioni di lunghezza superiore a una per definizione; se lo fosse, allora c'è un r_(q.i + 1) con O(1) e quindi un sotto-elenco runheads = [r_1.1,r_2.1,...,r_M.1] di N, ma heads è anche un sotto-elenco di runheads che contraddice che O(n) e r_i sono viene eseguito.

Ora, per trovare un r_i.1 dato un 1, assumiamo la disponibilità di una struttura di dati di mappatura con k inserimenti e ricerche di numeri ed elenchi con i -> k accodamenti e attraversamento in avanti. Quindi facciamo quanto segue.

• Per prima cosa costruiamo la lista f. Questo può essere fatto in modo banale attraversando rev mantenendo la corsa corrente. Durante questo passaggio ricordiamo anche il numero massimo riscontrato per ottenere k -> i alla fine e costruire una mappatura k -> runheads(i) con gli elementi di runheads = [1,3,2,5] come chiavi. Questo passaggio è chiaramente heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }. Nota che non è rilevante quali siano i valori di 2, quindi possiamo semplicemente usare run 3 come valore per la chiave 5.

• Ora passiamo da 4 a (e incluso) { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 } mantenendo un valore { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } con valore iniziale { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }. Per ogni valore map(f,runheads) controlliamo se [f(1),f(3),f(2),f(5)] è in O(n*log(n)). In questo caso aggiungiamo <=> a una mappatura <=> e aumentiamo <=>. Anche questo passaggio è chiaramente <=>. Per poter tornare da <=> a <=> possiamo anche archiviare un'ulteriore mappatura <=> con <=> o anche <=> senza costi aggiuntivi di big-O.

• Infine applichiamo la mappatura <=> agli elementi di <=> per ottenere <=>. Ancora una volta <=>.

Per illustrare con un esempio, esaminiamo il caso <=>.

• Nel primo passaggio otteniamo <=>, <=> e <=>.

• Per i secondi passi abbiamo quattro casi per i quali dobbiamo fare qualcosa: <=>, <=>, <=> e <=>. Per questi casi abbiamo valori per <=> che sono <=>, <=>, <=> e <=>, rispettivamente. Ciò significa che <=> sarà <=>. (E <=> sarebbe <=> o <=>, a seconda di ciò che hai scelto di archiviare.)

• Per ottenere <=> calcoliamo <=> che è <=> o, equivalentemente, <=>.

Quindi, se non ho commesso un errore e se le strutture dati soddisfano i requisiti di cui sopra, questa soluzione dovrebbe essere <=>. In pratica, potrebbe essere più utile utilizzare la propria soluzione (<=>). Se hai un grande <=> ma con solo un paio di esecuzioni, l'ordinamento <=> e l'utilizzo per costruire le mappature potrebbe essere più efficiente. Penso che <=> dovrebbe essere abbastanza grande perché ciò avvenga.

Answer 2

Modificato per chiarimento

passaggio 1: esegui l'algoritmo ma invece di produrre solo una tabella hash produce una tabella hash (D1) indicizzata dall'intestazione del set su cui sta mappando (ad esempio, per [3,4] che sarà 3) e un elenco (L1) con il set stesso

[3, 4, 6, 8; 1; 2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Passaggio 2: guardo le raccolte che abbiamo ora vedrai che, per un determinato set abbiamo l'indice in cui l'abbiamo trovato (in L1) e il valore Head. Il valore corretto della mappa sarà il numero intero minimo tra loro che non è già stato preso. Ad esempio, per [3,4] avremo che il valore deve essere compreso tra 1 e 3 e, poiché 1 è già preso, il valore corrispondente è 2. Tieni presente che, poiché D1 è indicizzato dall'Head valore, i valori più bassi assumeranno sempre se esiste l'insieme corrispondente. Nell'esempio, [1,2] è mappato su 1, in modo che questa chiave sia già & Quot; presa & Quot ;. Quindi, in pseudocodice:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Ad esempio

• prendiamo il primo valore in L1 - > [3,4] ...
• ottieni la testa = 3
• A partire da 1 cerchiamo D1 [1] che è già preso, quindi incrementiamo a 2.
• Cerchiamo D1 [2] che è vuoto, quindi assegniamo D1 [2] = [3,4] ed eliminiamo D [3]

Questo non fornisce O (n) ma qualcosa come O (n + log (n)) (n per il primo passo, log (n) per il secondo)

Per l'esempio sopra che ti porta:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Ora, se hai [3; 4; 8; 6; 1; 2], ciò comporterà

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

poiché sta usando l'ordinamento assoluto nell'array originale, non so se va bene o vuoi che 6 sia nell'indice 3 e 8 nell'indice 4, in quel caso probabilmente avrai preordinare L1 in base alla testa che aumenterà la tua complessità di Log (n)

Se devi preordinare avrai 0 (n + log ^ 2 (n)) che non è poi così male (forse meno supponendo che un QuickSort abbia O (Log n) che ordina L1 sarà O (log (log (log n))