największy możliwy prostokąt liter

Napisz program, aby znaleźć największy możliwy prostokąt liter, tak aby każdy wiersz tworzy słowo (od lewej do prawej), a każda kolumna tworzy słowo (od góry do dołu).

Znalazłem to interesujące pytanie. To nie jest praca domowa, choć może się tak wydawać. (Nie jestem w szkole). Robię to dla Zabawy.

Przykład

Od kot, samochód, małpa, api, rep, wskazówka otrzymujemy następujący prostokąt (który jest kwadratem): 

c a r
a p e
t i p

Moim początkowym pomysłem jest zbudowanie pewnego rodzaju drzewa prefiksów, aby móc pobrać wszystkie słowa zaczynające się od określonego ciągu. Byłoby to przydatne, gdy mamy już 2 lub więcej słów (albo czytając od góry do dołu lub od lewej do prawej) i musimy znaleźć następne słowo do dodania.

Jakieś inne pomysły?

Edit

Czy można to zrobić za pomocą prostopadłościanu (prostokąta 3D)?

Co jeśli musi mieć poprawne słowa na przekątnych (idea credit: user645466); jak by algo dla niego było zoptymalizowane?

Author: Johannes Pille, 2011-12-15
Source

3 answers

Niech d będzie słownikiem. Fix m i N. możemy sformułować problem znalezienia prostokąta m × n jako problem ograniczenia satysfakcji (CSP).

X i,1 ...x i,N ∈ D ∀i ∈ {1,..., m}
x 1, j ...x M,j ∈ D ∀j ∈ {1,..., n}
xi, j ∈ {A,..., Z} ∀i ∈ {1,..., m}, ∀j ∈ {1,..., n}

[[9]} bardzo powszechnym podejściem do rozwiązywania CSP jest łączenie backtrackingu z propagacją ograniczeń. Luźno mówiąc, backtracking oznacza, że wybieramy zmienną, odgadujemy jej wartość i rekurencyjnie rozwiązujemy podproblem o jedną zmienną mniej, a propagacja ograniczeń oznacza próbę zmniejszenia liczby możliwości dla każdej zmiennej (ewentualnie do zera, co oznacza, że nie ma rozwiązania).

Jako przykład możemy uruchomić siatkę 3 × 3 wybierając x1,1 = Q.

Q??
???
???

Ze słownikiem języka angielskiego, jedyna możliwość x1,2 i x2,1 jest U (w przed Scrabble "słowa").

Sztuka rozwiązywania CSP polega na balansowaniu między backtrackingiem a propagacją ograniczeń. Jeśli w ogóle nie propagujemy ograniczeń, to używamy tylko brutalnej siły. Jeśli propagujemy ograniczenia doskonale, to nie musimy się cofać, ale algorytm propagacji, który sam rozwiązuje problem np-hard, jest prawdopodobnie dość drogi w obsłudze.

W tym problemie praca z dużym słownikiem na każdym węźle backtrackingu będzie kosztowna, chyba że mieć dobrą obsługę struktury danych. Opiszę podejście, które używa trie lub DAWG szybko obliczyć zbiór liter, za pomocą których prefiks rozciąga się do pełnego słowa.

W każdym węźle backtrackingu, zbiór zmiennych, które przypisaliśmy, jest młodym tableau. Innymi słowy, Żadna zmienna nie jest przypisana, dopóki zmienne nad nią i po lewej stronie nie zostaną przypisane. Na poniższym diagramie . oznacza przypisaną zmienną, a * i ? oznacza przypisaną zmienną zmienne.

.....*
...*??
...*??
..*???
*?????

Zmienne oznaczone {[5] } są kandydatami do następnej, której zostanie przypisana wartość. Zaletą posiadania wielu wyborów zamiast wyboru stałej zmiennej za każdym razem jest to, że niektóre zmienne mogą być znacznie lepsze niż inne.

Dla każdego *, wykonaj dwa spojrzenia na Trie / DAWG, jedno dla poziomego i jedno dla pionowego, i Oblicz przecięcie zbiorów liter, które mogą nadejść dalej. Jedną z klasycznych strategii jest wybór zmiennej z najmniej możliwości w nadziei, że szybciej osiągniemy sprzeczność. Podoba mi się ta strategia, ponieważ przycina się naturalnie, gdy jest zmienna o zerowych możliwościach i rozmnaża się naturalnie, gdy jest zmienna o Jedynce. Poprzez buforowanie wyników możemy sprawić, że ocena każdego węzła będzie bardzo szybka.

 12
Author: Per,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-15 04:22:12

Biorąc pod uwagę Słownik wyrazów o danej długości, utwórz dwa nowe słowniki: pierwszy zawiera wszystkie prefiksy pojedynczych liter wyrazów (wszystkie litery, które mogą być pierwszą literą słowa o danej długości), a drugi zawiera wszystkie prefiksy dwuliterowe wyrazów (wszystkie sekwencje dwóch liter, które mogą być dwiema pierwszymi literami słowa o danej długości). Możesz również robić potrójne prefiksy, ale prawdopodobnie nie będziesz musiał wykraczać poza to.

  1. Wybierz słowo z słownik, nazwij to X. Będzie to pierwszy rząd macierzy.

  2. Sprawdź, czy X[1], X[2], ..., X[N] są poprawnymi przedrostkami pojedynczej litery, korzystając z tej poręcznej listy, którą stworzyłeś. Jeśli tak, przejdź do kroku 3; w przeciwnym razie wróć do kroku 1.

  3. Wybierz słowo ze słownika, nazwij je Y. Będzie to drugi rząd macierzy.

  4. Sprawdź to X[1] Y[1], X[2] Y[2], ..., X[N] Y[N] są poprawnymi przedrostkami dwuliterowymi używającymi tej poręcznej listy, którą stworzyłeś. Jeśli oni są, przejdź do kroku 5; w przeciwnym razie wróć do kroku 3. Jeśli było to ostatnie słowo w słowniku, wróć do kroku 1.

    ...

    2(N-1). Wybierz słowo ze słownika, nazwij je Z. Będzie to n-ty rząd macierzy.

    2N. sprawdź, czy X[1] Y[1] ... Z[1], X[2] Y[2] ... Z[2], ..., X[N] Y[N] ... Z[N] są wszystkie słowa w słowniku. Jeśli tak, gratulacje, udało Ci się! W przeciwnym razie wróć do kroku 2 (N-1). Jeśli było to ostatnie słowo w słowniku, wróć do kroku 2 (n-3).

Logika polega na zbudowaniu prostokąt słów jeden wiersz na raz, wybierając słowa dla wierszy, a następnie sprawdzając, czy kolumna może być uzupełniona do słów. Będzie to przebiegało znacznie szybciej niż dodawanie jednej litery na raz.

 1
Author: PengOne,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-17 00:23:05

Utworzyć worek [] dla słowa o tej samej długości = indeks następnie utworzyć wordlist można używać tylko w języku angielskim.]} 

   Rectangle makeRectangle(length, height, rectangle)
    {
        if ( length == rectangle.length()) check if complete and return;
        checkIfPartialComplete - check columns for valid prefixes
        for ( i from 1 to grouplist[i-1])
        {
            newRectangle = append word[i] to rectangle 
            return makeRectangle(l,h, rectangle with appended word) if not equal to null
        }
    }


boolean checkPartial(int l, Trie trie)
{
    for ( int i =0 ; i < l; i++)
    {
        String col = getColumn(i);
        if (!trie.contains(col))
        {
            return false;
        }
    }
    return true;
}
boolean checkComplete(int l, Bag<String> lengthGroup)
{
    for ( int i=0; i < l ; i++)
    {
        String col = getColumn(i);
        if (!lengthGroup.contains(col))
        {
            return false;
        }
    }
    return true;
}
 1
Author: Nataraj,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-06-11 01:09:43