Czy zawsze można zamówić wielowymiarową tablicę we wszystkich wymiarach? W jaki sposób?

Załóżmy, że mam n-wymiarową tablicę liczb całkowitych (dla n=1 jest to wektor, dla n=2 jest to prostokątna matryca, dla n=3 jest to równoległościan itp.). Muszę zmienić kolejność elementów tablicy tak, aby elementy w każdym wierszu, kolumnie itp. Były w porządku malejącym.Czy zawsze można zamówić wielowymiarową tablicę we wszystkich wymiarach? W jaki sposób?

Czy jest to możliwe dla dowolnej tablicy wejściowej?
~~Czy wymagana kolejność jest unikalna dla dowolnej tablicy wejściowej?~~ Właśnie uświadomiłem sobie, że odpowiedź na to pytanie ogólnie jest no, np. dla kwadratowych matryc.
Czy wymagana kolejność jest unikalna dla dowolnej tablicy wejściowej o różnych długościach we wszystkich wymiarach?
Jaki jest najszybszy algorytm do wykonania wymaganego zamówienia?

Źródło

2013-08-05 Լ.Ƭ.

Czy możesz precyzyjniej zdefiniować "uporządkowanie"? –

Tak więc, dla tablicy 2D liczb całkowitych, chcesz największą liczbę całkowitą w prawym dolnym rogu? Wydaje mi się, że sortowanie każdej kolumny, a następnie każdy rząd da takie uporządkowanie. Jestem pewien, że jest na to szybszy sposób. –

"Zamiana" ZiyaoWei oznacza "przestawienie", "wstawienie tych samych elementów to (być może) inna kolejność". Innymi słowy, wynikowa tablica musi zawierać te same liczby całkowite, z tą samą wielokrotnością (w przypadku gdy liczba całkowita pojawia się wiele razy w różnych pozycjach w tablicy wejściowej), ale możliwe, że w różnych położeniach (brak, jeden, niektóre lub wszystkie elementy elementu). wskaźniki mogą się zmienić). –

Czy jest to możliwe dla dowolnej tablicy wejściowej?

Tak, jeśli spojrzymy na tablicę jako tablicę pojedynczych wymiarów, z tą samą liczbą elementów, a następnie posortujemy ją, przechodząc z powrotem do oryginalnej tablicy o wymiarach n, pozostaje ona sortowana, ponieważ dla każdego i1,....,i_k,...,i_m: dla wszystkich 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']...

Co do 2 pytania:

Czy wymagane zamawiania unikalny dla każdej tablicy wejściowej, która ma różne długości we wszystkich wymiarach?

nr:

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

Jaki jest najszybszy algorytm w celu uzyskania wymaganego kolejność?

Jedno rozwiązanie jest już zasugerowane: zważywszy, że jest to duża długa tablica i posortuj ją. Złożoność to O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m)) Mój gut mówi, że gdybyś mógł to zrobić szybciej, mógłbyś szybciej niż O(nlogn), ale nie mam dowodu na to roszczenie, więc może to być złe.

Źródło

2013-08-05 18:03:45 amit

Myślę, że pełne sortowanie nie jest konieczne. – lcn

@lcn Może to być niepotrzebne, moje jelito mówi, że tak nie jest - ale nie jestem tego pewien. W każdym razie, punktem odpowiedzi jest pokazanie, że można to zrobić algorytmicznie dla wszystkich przypadków wejściowych, chciałbym zobaczyć bardziej zoptymalizowane algorytmy, jeśli takie istnieją. – amit

Pozwolę sobie omówić więcej o idei Alptigina Jalayra.

Załóżmy, że mamy posortowane wiersze, więc dla poniższych danych mamy a <= b i c <= d.

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

Kiedy a jest większa niż c, tj c <a, potem zamiana z nich daje nam c < b ponieważ a <= b i a <=d ponieważ b <= d (jeśli b > d, możemy zamienić b i d również). Jednym słowem najpierw sortowanie wierszy, a następnie kolumn może dać pożądaną macierz.

Źródło

2013-08-05 18:06:54 lcn

Czy zawsze można zamówić wielowymiarową tablicę we wszystkich wymiarach? W jaki sposób?

Odpowiedz

Powiązane problemy