Łączenie komórek za pomocą permutacji liniowych i kolumnowych w skończonej siatce

Chciałbym wiedzieć, czy wcześniej zbadano następujący prosty problem i czy znane jest jakieś rozwiązanie.

Niech G będzie siatką skończoną (MxN), S podzbiorem komórek G („okruchy”). Mówi się, że dwie okruchy są (lokalnie) połączone, jeśli ich współrzędne różnią się co najwyżej o jeden (tj. Jeśli narysowane jako kwadraty, dzielą co najmniej jeden punkt narożny).

Teraz można spróbować połączyć okruchy (ich zestaw jako całość), permutując linie i kolumny siatki. Innymi słowy, celem jest opracowanie permutacji linii i permutacji kolumn, tak aby dowolne dwie okruchy w wynikowej siatce były połączone łańcuchem (lokalnie) okruchów.

Pytanie: czy zawsze istnieje rozwiązanie?

Nie bardzo wiem, jak go zaatakować. Z braku lepszego pomysłu napisałem surowy program, który szuka rozwiązań brutalną siłą (generuje losowo permutacje i sprawdza, czy wynikowa siatka ma połączone okruchy). Program do tej pory zawsze znajdował rozwiązania na małych (10 x 10 lub 7 x 14) siatkach, a większe siatki wyraźnie nie są w zasięgu jego uproszczonej strategii (zbyt długo losowe natknięcie się na rozwiązanie) byłoby zbyt długie.

Oto przykład siatki rozwiązanej przez program:

Początkowa siatka (okruchy są oznaczone X, puste komórki kropkami):

   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Rozwiązanie:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Oczywiście problem można z łatwością uogólnić na dowolny wymiar d> 2. Podejrzewam, że można by rozważyć inne uogólnienia.

Z góry dziękuję,

Yann David

Spróbujmy bardziej dokładnie argumentu zliczającego jak we wcześniejszej wersji mojej odpowiedzi.

Biorąc pod uwagę wejściową macierz 0-1 z q nonzerami, zdefiniuj „rozwiązanie”, które będzie permutacją wierszy, permutacją kolumn i podłączoną macierzą 0-1, którą otrzymuje się jako wynik po wykonaniu permutacji. Ważną obserwacją jest tutaj to, że możliwe są co najwyżej różne macierze wyjściowe: po dokonaniu jednej z wyborów dla pozycji jednego z nonzerów, możemy zakodować resztę macierzy wyjściowej w bitach , wykonując przedpremierowe przejście drzewa opinającego nonzeros i rejestrując dla każdej krawędzi drzewa, czy idzie do liścia, czy jest ostatnią krawędzią od jego rodzica i jaki jest kierunek. Tak więc liczba rozwiązań wynosi łącznie maksymalnie . n 2 5 q n 2 2 5 q ( n ! ) $n^2 2^{5q}$$n^2$$5q$$n^2 2^{5q} (n!)^2$

Teraz każde rozwiązanie działa tylko dla pojedynczego wejścia, ponieważ możemy odwrócić permutacje, aby odzyskać dane wejściowe z macierzy wyjściowej. Liczba wejść, które mają dokładnie niezerowych wierszy w wierszu wynosi , a dla stałej można to przepisać . Ale dla liczba rozwiązań wynosi . Dla dane wejściowe przewyższają liczbę rozwiązań, więc jest dane wejściowe nierozwiązywalne.$c$cexp(cnlogn-O(n))q=cnexp(2nlogn+O(cn))c>$\binom{n}{c}^n$$c$$\exp(cn\log n-O(n))$$q=cn$$\exp(2n\log n+O(cn))$$c>2$