È sempre possibile ordinare un array multidimensionale in tutte le dimensioni? Come?

Supponiamo, Ho un array di numeri interi n (per n=2 è un vettore, per n=2 è una matrice rettangolare, per n=3 è un parallelepipedo, ecc.). Ho bisogno di riordinare gli elementi dell'array in modo che gli elementi in ogni riga, colonna, ecc. Siano in ordine decrescente.È sempre possibile ordinare un array multidimensionale in tutte le dimensioni? Come?

È possibile per qualsiasi array di input?
~~L'ordine richiesto è univoco per qualsiasi array di input?~~ Mi sono appena reso conto che la risposta a questa domanda in generale è no, ad es. per matrici quadrate.
L'ordine richiesto è univoco per qualsiasi array di input con lunghezze diverse in tutte le dimensioni?
Qual è l'algoritmo più veloce per produrre l'ordine richiesto?

fonte

2013-08-05 Լ.Ƭ.

È possibile definire "riordinare" in modo più preciso? –

Quindi, per un array 2D di numeri interi, vorresti il numero intero più grande nell'angolo in basso a destra? Mi sembra che ordinando ogni colonna, e poi ogni riga ti darà un tale riordino. Sono sicuro che c'è un modo più veloce per farlo però. –

@ZiyaoWei "riordinare" significa "riorganizzare", "mettere gli stessi elementi è un (possibilmente) ordine diverso". In altre parole, la matrice risultante deve contenere gli stessi numeri interi, con la stessa molteplicità (nel caso in cui un intero appaia più volte in posizioni diverse nell'array di input), ma possibilmente in posizioni diverse (nessuna, una, alcune o tutte le gli indici possono cambiare). –

È possibile per qualsiasi array di input?

Sì, se vedremo sulla matrice come un array monodimensionale, con lo stesso numero di elementi, e quindi ordinare che, attraversando nuovamente alla matrice originale n-dimensioni, rimane ordinato, poiché per ogni i1,....,i_k,...,i_m: per tutti i_k < i_k':

i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ... 
Thus (the array is ordered): 
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...] 
Thus (back to original array): 
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...

quanto riguarda la 2a domanda:

'la necessaria ordinare unico per qualsiasi matrice di input con differenti lunghezze in tutte le dimensioni?

No:

1 1   1 3 
3 4   1 4 
5 6   5 6

Qual è l'algoritmo più veloce per produrre l'ordinamento richiesto?

Una soluzione è già suggerita: si tratta di un grande array lungo e di ordinarlo. Complessità è O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
Il mio istinto dice che se potessi farlo più velocemente, potresti sory più veloce di O(nlogn), ma non ho prove per questo reclamo, quindi potrebbe essere sbagliato.

fonte

2013-08-05 18:03:45 amit

Penso che non sia necessario un ordinamento completo. – lcn

@lcn Potrebbe essere ridondante, il mio istinto dice che non lo è, ma non ne sono affatto sicuro. Ad ogni modo, il punto della risposta è mostrare che può essere fatto algoritmicamente per tutti i casi di input, mi piacerebbe vedere anche algoritmi più ottimizzati, se esistono. – amit

Lasciatemi approfondire l'idea di Alptigin Jalayr.

Supponiamo di disporre di righe ordinate, quindi per i dati seguenti abbiamo a <= b e c <= d.

 .  . 
..., a, ..., b, ... 
    .  . 
..., c, ..., d, ... 
    .  .

Quando a è maggiore di c, cioè c <a, poi scambio di loro ci dà c < b dal a <= b e a <=d poiché b <= d (se b > d, scambiamo b e d pure). In una parola, ordinando prima le righe e poi le colonne successive è possibile ottenere la matrice desiderata.

fonte

2013-08-05 18:06:54 lcn

È sempre possibile ordinare un array multidimensionale in tutte le dimensioni? Come?

risposta

Problemi correlati