zrób zbiór zawierający podane litery ("alfabet") bez powtórzeń.
przejedź w pętli po słowniku, kopiując do innego słownika tylko słowa zawierające litery ze zbioru (in) i jednocześnie nie zawierające liter spoza niego (not in) i nie dłuższe niż liczba wszystkich liter (z powtórzeniami).
w ten sposób zawęzisz ilość wyrazów. a jeśli wyrazy mają się składać ze wszystkich liter (bez pominięcia żadnej), to odrzucaj nie tylko słowa dłuższe, ale też słowa krótsze, wtedy słownik wyjściowy jest jednocześnie rozwiązaniem problemu.
powyższa operacja ma złożoność O(m*n2), czyli dla typowego słownika jezyka polskiego ~16MB * np. cały alfabet (32 litery) jest to mniej niż 512MB danych do przetworzenia (przerywasz wewnętrzną pętlę, tj. odrzucasz niepasujące słowo po znalezieniu pierwszej, a nie ostatniej, niepasującej litery). znośnie. przy dobrze napisanej i zoptymalizowanej pętli jest to kilkanaście-kilkadziesiąt sekund. n2 <= n, bo określa liczbę liter bez powtórzeń, poza tym to pesymistyczny przypadek (wszystkie 32 litery).
w przeciwnym wypadku - pętla po nowym słowniku, dla każdego słowa: 1. tworzysz kopię tablicy zawierającą wymagane litery (z powtórzeniami); 2. usuwasz (albo szybciej - zamieniasz na np. #255) ze słowa litery znajdujące się w kopii tablicy, i jednocześnie usuwasz te litery z tej kopii tablicy; 3. jeśli słowo jest puste ('') lub składa się z samych znaków #255, to wrzucasz je do kolejnego słownika z wynikami.
na koniec pętli po kopii słownika ten "kolejny słownik" zawiera szukane wyrazy.
powyższa operacja ma również złożoność kwadratową O(m2*n), przy czym m2 <= m to liczba słów pozostałych po pierwszym odsianiu.
dla najbardziej pesymistycznego przypadku rozwiązanie powinno być wygenerowane najdalej po kilkudziesięciu sekundach (zakładając sensowny procesor).
obie operacje da się przyspieszyć, bo założyłem porównywanie każdej litery każdego wyrazu z każdą literą naszego "alfabetu", tymczasem można to zrobić wyszukiwaniem binarnym po "alfabecie", wtedy obie operacje można spróbować zdusić do O(m * log(n2)) i O(m * log(n)), jednak zysk nie będzie duży, bo samo "opakowanie" kodu wyszukiwania połówkowego zeżre trochę mocy procesora, do tego n2 i n są małymi liczbami, więc log(n) ~ n.
widzę też inne podejście warte zastanowienia: stworzyć tyle słowników, ile ma najdłuższe słowo, powiedzmy 30, w każdym posortować wyrazy po kolejnej literze. to umożliwiłoby wyszukiwanie binarne w zbiorze kilkudziesięciu tysięcy słów, więc by naprawdę znacznie przyspieszyło cały proces, poza tym takie posortowane tabele można wygenerować raz i korzystać z nich wielokrotnie. tylko jeszcze trzeba wymyślić, jak efektywnie korzystać z tych tabel - na razie nie mam konkretnego pomysłu, a nie mam czasu myśleć nad tym. niemniej problem bardzo ciekawy, jeśli chodzi o efektywne rozwiązanie. może by jakiś konkurs znowu? :>
a tak z innej bajki:
void dekodoj(char tablica1[100],int *tab2,char *tab3,int max)
- jak można robić błędy ortograficzne w nazwach procedur? ku*wa, człowieku, ogarnij się, wstyd. i liczenie permutacji bez powtórzeń dla n liter to wiesz, O(n!*m)... przy 10 literach pójdziesz na kawę, przy 12 literach klękniesz, a przy 16 literach dzieci twoich dzieci będą nadal czekać na wynik. 15 liter to ponad bilion potencjalnych słów, a to jeszcze razy ~2M słów w słowniku, coś koło tryliona bajtów danych. nie tędy droga.