tablice dwu-wymiarowe

Piszę pewien program w którym wykorzystuje tablice dwu-wymiarowe. W pewnym momencie
mam na dwóch zmiennych N i M odpowiednio: N: liczbę wierszy i M: liczbę kolumn tablicy dwu-wymiarowej. Potrzebuję sprawdzić jakimś algorytmem ile tablic rozmiaru N*M da się zrobić spełniających następujące warunki:

1. Tablica musi być wypełniona liczbami z zakresu 0..N*M..-1.
2. Tablica jest posortowana wierszami i kolumnami. (oddzielnie wierszami, oddzielnie kolumnami)
3. Liczby sie nie powtarzają.
   Np, dla N=2 i M=2 wynik powinien być = 2.

Wdzięczna byłabym za pomoc w napisaniu jakiegoś sprytnego algorytmu.

Czyżby za napisania tematu w wersji żeńskiej są większe profity niż za wersję męską?:>

misqa napisał(a)

1. Tablica musi być wypełniona liczbami z zakresu 0..N*M..-1.

Srednio jasny dla mnie jest ten przedzial. To ma byc iloczyn zbiorow? Swoja droga to 0..N*-1..M chyba?

Force napisał(a)

Czyżby za napisania tematu w wersji żeńskiej są większe profity niż za wersję męską?:>

Hehe, dopiero wlasnie zauwazylem niezdecydowanie plciowe usera ;P
Ciekawe, ciekawe. ;)

Zrozumiałem to tak: tablica musi być wypełniona liczbami z zakresu 0..NM..-1. Co dla N=2 i dla M=2 daje: 0, 1, 2, 3. Inaczej można ten przedział zapisać 0...(NM)-1??? Czy dobrze to rozumiem? Jak tak to trochę trudne to będzie. Ja nie mam pomysłu na to.

Elementów jest tyle, co komórek macierzy, tak więc każde ułożenie będzie jedną z permutacji zbionu N*M elementowego.

Najprostszy ale najgorszy byłby zwykły bruteforce, tj wygenerować każdą możliwą permutacje (jest ich (M*N)! a więc dużo) i sprawdzić, które z nich tworzą macierz posortowaną.

Znacznie lepszy byłby ulepszony bruteforce, a konkretniej rekurencyjny algorytm backtrackingu. W twoim przypadku polegałby mniej więcej na zasadzie "Wstawiaj niewykorzystane elementy do macierzy dopóki macierz jest posortowana. Jeśli porządek zostanie zaburzony wróć do momentu, kiedy można było wstawić inny, kolejny element i kontynuuj wstawianie." Dokładniejszy opis idei backtrackingu znajdziesz w internecie np. http://en.wikipedia.org/wiki/Backtracking

Z backtrackingiem dalej można kombinować ustalając jakie wartości mogą być w jakich komórkach. Można zauważyć, że:

0 musi być w pierwszej komórce macierzy (0, 0)
1 musi być za 0, czyli w komórce (1,0) (1,1) lub (0,1).
2 musi być za 0 lub 1, czyli możliwe miejsca to (1,0) (1,1) (0,1) (2,0) (2,1) (2,2) (1,2) (0, 2)
3 musi ... i dochodzimy do wniosku, że 'k' musi być w komórce (0..k, 0..k)
Od drugiej strony to samo:
mn-1 musi być w komórce (n-1, m-1)
mn-2 może być w komórkach (n-2, m-1) (n-2, m-2) (n-1, m-2)
mn-3 może być w komórkach (n-2, m-1) (n-2, m-2) (n-1, m-2) (n-3, m-1) (n-3, m-2) (n-3, m-3) (n-2, m-3) (n-1, m-3)
itd. więc 'mn-k' musi być w komórkach (n-k..n-1, m-k..m-1)

Można się więc zastanowić, z jakiego zakresu liczby mogą być w komórce (i, j). Jeśli by oznaczyć 'a=min(i,j), b=min(n-i,m-j)', to w komórce (i,j) odpadają liczby mniejsze od 'a' (bo nie wykraczają poza (0..a-1, 0..a-1)) oraz liczby większe od mn-b (bo nie wykraczają poza (n-b+1..n-1, m-b+1..m-1).
Tak więc podczas wstawiania elementów do komórki (i,j) warto wybierać tylko te z zakresu a..mn-b.