Macierz czwórkowa

[pelas_91]

Mam następujący problem:

Chcę uzyskać macierz wypełnioną czterema liczbami spełniającą następującą własność: żaden minor główny \(\displaystyle{ 2 \times 2}\) się nie powtarza.

Zależy mi na "ogólnym" rozwiązaniu problemu, bo \(\displaystyle{ 2 \times 2}\) jest tylko wstępem do \(\displaystyle{ 3 \times 3}\) i w końcu np. \(\displaystyle{ 10 \times 10}\).

Czy ktoś jest w stanie podpowiedzieć, co doczytać z kombinatoryki, żeby rozwiązać ten problem?

[jsf]

Jestem trochę zmęczony, więc może coś mi umyka, ale wydaje mi się, że każda macierz diagonalna, która na przekątnej ma kolejne liczby pierwsze, spełnia żądany warunek. Dla niej każdy minor główny jest inną liczbą - każdy jest iloczynem różnych liczb pierwszych, więc występuje tylko raz. Jeżeli macierz wyjściowa nie jest kwadratowa, to odcinamy odpowiednio dużo kolumn od prawej strony tak, żeby kwadratowa była, w tej kwadratowej wpisujemy liczby tak jak to opisałem wyżej, a w odciętej części cokolwiek.

Może źle rozumiem zadanie albo zapomniałeś dopisać jakiegoś założenia, bo to za proste, żeby kazać rozpatrywać najpierw w przypadkach \(\displaystyle{ 2 \times 2}\), potem \(\displaystyle{ 3 \times 3}\) i dopiero wtedy \(\displaystyle{ 10 \times 10}\). Może korzystasz z innej definicji minoru głównego - ja się sugerowałem , czyli nawet dla macierzy niekwadratowej działa, bo pojęcie minoru będzie się odnosiło tylko do jej części kwadratowej.

Przepraszam, jeżeli coś zepsułem.

[pelas_91]

Echh... przepraszam za baznadziejnie niepoprawne uproszczenie...
Oczywiście nie chodzi mi o minory-wyznaczniki lecz o same macierze \(\displaystyle{ 2 \times 2}\), a potem \(\displaystyle{ 3 \times 3, ..., 10 \times 10}\).

Innymi słowy fragment takiej macierzy mógłby wyglądać tak:

\(\displaystyle{ \left[\begin{array}{ccccccccc}1&2&3&4&1&2&3&4& \\2&3&1&2&1&2&3&4&\dots \\4&3&2&1&4&3&2&1&\\ &&&&\vdots&&&&\end{array}\right]}\)

jak utworze wszystkie macierze \(\displaystyle{ 2 \times 2}\) z tego kawałka, takie "zbite" a nie "rozwalone" ale mogące na siebie zachodzić np.

\(\displaystyle{ \left[\begin{array}{cc}1&2\\2&3\end{array}\right]\ \left[\begin{array}{cc}2&3\\3&1\end{array}\right]\ \left[\begin{array}{cc}2&3\\4&3\end{array}\right]\ \left[\begin{array}{cc}3&1\\3&2\end{array}\right]}\)

itd.

to żadne dwie nie są równe.

Zastanawiam się na sposobem generowania takich prostokątów.

[jsf]

Bardzo łatwo wymyślić nieskończoną klasę takich macierzy - są to macierze o każdym wyrazie innym.

Co do generowania, to wydaje mi się, że każdą taką macierz można wygenerować w następujący sposób. Dla przykładu chcemy stworzyć macierz \(\displaystyle{ 10 \times 12}\), taką, żeby żadne dwie "podmacierze" \(\displaystyle{ 2\times 2}\) nie były takie same. Na pozycjach \(\displaystyle{ a_{11},a_{12},a_{21},a_{22}}\) wpisujemy cokolwiek. Wycinamy z papieru o dużym stopniu przezroczystości kwadrat \(\displaystyle{ 2\times 2}\), ustawiamy na macierzy tak, żeby siedziały w nim wypisane już wyrazy. Potem przesuwając kwadrat o jedną kolumnę/wiersz w prawo, lewo, górę lub dół uzupełniamy puste miejsca takimi liczbami lub liczbą, żeby uzupełniana macierz nie pokrywała się z żadną dotąd wypisaną. Zawsze będzie można taką liczbę dopisać (chociażby dowolną dotąd nie wypisaną liczbę), więc algorytm się zawsze kończy, do tego wygenerować nim można dowolną macierz o żądanej własności.

Niestety nie rozumiem, do czego zmierzamy? Może chciałbyś policzyć prawdopodobieństwo wylosowania takiej macierzy? To by dopiero było hardcorowe zadanie. Chociaż w sumie wyjdzie \(\displaystyle{ 1}\), więc rozpatrzymy jakiś zawierający atomy rozkład losowania liczb do komórek macierzy i będziemy się z tym bawić może i tydzień.

[pelas_91]

Na pozycjach \(\displaystyle{ a_{11},a_{12},a_{21},a_{22}}\) wpisujemy cokolwiek. Wycinamy z papieru o dużym stopniu przezroczystości kwadrat 2x2, ustawiamy na macierzy tak, żeby siedziały w nim wypisane już wyrazy. Potem przesuwając kwadrat o jedną kolumnę/wiersz w prawo, lewo, górę lub dół uzupełniamy puste miejsca takimi liczbami lub liczbą, żeby uzupełniana macierz nie pokrywała się z żadną dotąd wypisaną.

A skąd będziemy wiedzieć że wśród dopisanych liczb nie znajdę dwóch identycznych macierzy? To że każda podmacierz jest różna od jednej, z góry ustalonej macierzy jeszcze nie gwarantuje nam że wszystkie podmacierze są parami różne.

Zawsze będzie można taką liczbę dopisać (chociażby dowolną dotąd nie wypisaną liczbę), więc algorytm się zawsze kończy, do tego wygenerować nim można dowolną macierz o żądanej własności.

Dowolną nie wypisaną liczbę? Ale ja przecież mam do dyspozycji cały czas tylko cztery liczby.

[jsf]

Źle zrozumiałem pojęcie "macierz czwórkowa". Myślałem, że chodzi o macierz \(\displaystyle{ 2\times 2}\). Ty za to trochę źle zrozumiałeś zaproponowany przeze mnie algorytm: ja chciałem macierz, którą tworzę, porównywać z każdą już uzupełnioną, nie tylko z pierwszą. Więc on dalej będzie generował wszystkie możliwe takie macierze, ale trzeba dołączyć moment stopu - jeżeli nie da się już dopisać takiej liczby.

W każdym razie zadanie zrobiło się ciekawe i rozumiem, że mamy policzyć ilość macierzy, np. \(\displaystyle{ 10\times 12}\), które spełniają te kryterium? Bo jeżeli tylko o generowanie chodzi, to algorytm się broni, chociaż do zliczania możliwych kombinacji się nie nadaje.

[pelas_91]

ja chciałem macierz, którą tworzę, porównywać z każdą już uzupełnioną, nie tylko z pierwszą.

Jest to zawsze wyjście z sytuacji ale niesamowicie czasochlonne i skomplikowane nawet przy użyciu komputera. Nie wyobrażam sobie jak długo musiałby trwać te wszystkie porównania dla podmacierzy \(\displaystyle{ 10 \times 10}\)

[jsf]

Zgadzam się jak najbardziej. W każdym razie żaden algorytm nie będzie zbyt szybki. Bo jeżeli masz macierz \(\displaystyle{ n\times m}\), to porównując tylko jedną podmacierz \(\displaystyle{ 2 \times 2}\) musisz wykonać \(\displaystyle{ (n-1)(m-1)-1}\) porównań. W sumie dla macierzy \(\displaystyle{ n \times m}\) będzie do wykonania (tzn. orientacyjnie, być może gdzieś zapomniałem dopisać czegoś drobnego)
\(\displaystyle{ \sum_{i=1}^{(n-1)(m-1)}((n-1)(m-1)-i)}\)
porównań, więc liczba astronomiczna, ale zmniejszyć jej nie możesz, bo przecież każde dwie macierze trzeba porównać. Tak na pierwszy rzut oka zaproponowany przeze mnie algorytm, jeżeli tylko nie zatrzyma się przed wypełnieniem macierzy, ma właśnie taką złożoność obliczeniową - wykonujesz minimalną liczbę możliwych porównań. Nie mam na razie zielonego pojęcia, jaki algorytm zaproponować, żeby miał właśnie tę złożoność obliczeniową (czyli za każdym razem generował dobrą macierz minimalną liczbą porównań). Pytałeś na początku, z czego powinieneś się douczyć. Ja bym na Twoim miejscu w tym momencie bardzo się zainteresował algorytmiką - może ktoś już taki algorytm wymyślił albo są rozwiązania podobnych problemów, które używają lepszego podejścia. Pewnie opłacalne byłoby nie trzymanie się minimalnej liczby porównań, bo dużo bardziej opłacalne będzie dostawanie spełniającej nasz warunek macierzy za każdym razem.

Swoją drogą, rozpatrywane przez nas macierze wcale tak duże być nie mogą, bo liczba różnych macierzy czwórkowych danej wielkości jest ograniczona, np. \(\displaystyle{ 2\times 2}\) można wypełnić tylko na \(\displaystyle{ 4^{4}}\) różnych sposobów.

Jeżeli do czegoś dojdziesz, to pisz. Sam jestem bardzo zainteresowany rozwiązaniem tego problemu. Za cztery dni będę miał więcej czasu i wtedy też nad tym usiądę.