układanie słówek z zadanych liter

Nie wiem jak to się nazywa fachowo, ale chodzi o układanie słówek z zadanych liter, w postaci innego słowa albo zdania.

Np. mając słowo: transplantacja

mamy za zadanie sprawdzić, czy inne słowo można z tego ułożyć.

kot - nie można, bo w transplantacja nie ma k ani o.
spacja, taran, tata - a te można

lala - tego też nie można, bo potrzeba dwóch l, a w transplantacja mamy tylko jedno.

funkcja typu:
superior(a, b)
if b ma litery z a then wynik = 1
else wynik = 0;

i jak to zrobić, sprawdzić szybko, optymalnie?

Na początek musisz mieć słownik wszystkich wyrazów, wrzucić je do tablicy a później wyszukiwać wszystkie kombinacje. Na potrzeby tego dla każdego słowa zrobiłbym tablicę ze statystykami informującego po ile i jakich liter w nim występuje. Do tablic ze statystykami porobiłbym jeszcze indeksy na poszczególne litery - to tak żeby to wyszukiwanie nie trwało wieki.

Tu masz link do słownika: http://www.math.uni.wroc.pl/~hebisch/prog/pol.lst

Mozesz zapisac strukture do trie a potem przeszukiwac je deep first searchem.

1. Musisz oczywiście mieć słownik :) Możesz np. pobrać polską wikipedię i zrobić set ze wszystkich słów które tam są.
2. Testowanie wszystkich możliwych wariacji bez powtórzeń liter z danego słowa może być czasochłonne. Ja osobiście zalecałbym najpierw policzyć sobie jakieś n-gramy (bigramy, trigramy przynajmniej, albo nawet więcej) żeby wiedzieć jakie zbitki słów mają w ogóle sens. W sumie nie trzeba nawet zliczać prawdopodobieństwa, można by zrobić set który zawiera "istniejące" zbitki n-literowe. Tzn. np. dla słowa spacja wrzucasz do seta sp, pa, ac, cj, ja i do 3-seta spa, pac, acj, cja itd. W ten sposób możesz łatwo sprawdzić czy dana zbitka może być częścia jakiegoś słowa czy też nie. Np. pewnie nie będzie nigdy zbitki zz, więc jak masz wyjściowe słowo zaraza to nie ma sensu szukać w słowniku słów zaczynających się od zz...

Najpierw słownik: https://sjp.pl/slownik/odmiany/

Słowa pakujesz do (hash)mapy, gdzie kluczem jest histogram wystąpień liter słowie, a wartością list możliwych słów dla danego histogramu.

Bierzesz słowo wejściowe, budujesz z niego histogram.
Iterujesz po kolejnych histogramach pomniejszonych o jedną litrę i sprawdzasz czy występuje w mapie.

To jest wersja uproszczona.
Bo można wziąć słowa i od razu zbudować mapę wszystkich odpowiedzi, budując odpowiednio sprytne drzewo histogramów.
Takie drzewo zapisać sobie i wczytywać przy starcie programu. Wtedy odpowiedzi będziesz dostawał w zasadzie od razu.

Mi nie chodzi o wyszukanie wszystkich możliwych słów ze słownika, które można tu ułożyć,
lecz tylko dla jednego - zadanego.

przykładowo:

z = 'kilkudziesięciokondygnacyjny'
s = 'koczkodan'

da się zbudować: słowo s z liter w z ?

sprawdzam:

jest_s_w_z = superior(z, s); // s in z

xD
Zrób letter-count tych dwóch słow tak jak pisał wyżej @MarekR22 i sprawdź czy każda litera z 1 występuje w 2 i czy jej licznik jest >=

from collections import Counter


def letter_count(word):
    return Counter(word)


def superior(z, s):
    x = letter_count(z)
    print(x)
    y = letter_count(s)
    print(y)
    for letter, counter in y.items():
        if letter not in x or x[letter] < counter:
            return False
    return True


def main():
    z = 'kilkudziesieciokondygnacyjny'
    s = 'koczkodan'
    print(superior(z, s))


main()

a co to za język?

Poza tym sam myślałem że można tak to robić, ale to jest za słabe.

Myślałem że istnieje lepszy sposób...

Tu nawet lekka modyfikacja pozwoliłaby to sporo przyspieszyć - 10 razy pewnie!

nie potrzeba liczyć od razu liter w s, bo to można w biegu zrobić - wraz ze sprawdzaniem tego warunku:

cnts = 0 // licznik liter w s

for i ...
{
c = s[i];
if ++cnts[c] > cntz[c] then return 0; // i to jest koniec sprawdzania
}

return 1; // ok

@bonifacy przy normalnych słowach nic ci to nie przyspieszy, bo liter w słowie jest raptem kilka i moim zdaniem to niepotrzebna komplikacja. Zresztą i jedno i drugie rozwiazanie to O(n) gdzie n to długość słowa które testujesz. Szybciej się nie da, więc mówienie że to za słabe jest śmieszne. Pesymistyczny musisz przelecieć całe słowo, średnio przynajmniej jego połowę, więc mimo wszystko O(n)

10 razy szybciej jest śmieszne?

A dodatkowo wyobraź sobie taki wariant (użycia tej funkcji):
mamy tylko jedno zdanie: z, ale tych s - 'podzbiorów' do sprawdzenia może być nawet 100000!

wtedy wystarczy tylko raz przeliczyć litery z, a potem sprawdzamy kolejne słowa -
i jaki będzie teraz czas szukania dla długości zdania, np.: 500 literek, a 'słówek' średnio po 50?

Nie bardzo cie rozumiem. To oczywiste że cały słownik liczymy wcześniej, a potem sprawdzamy juz tylko kolejne słowa. I znów: średnio asymptotycznie będziesz nadal miał liniowy czas, nie przeskoczysz tego. A ten twój kod moze być nawet i wolniejszy. Raz ze wszystkie te lookupy cntz[c] i cnts[c] kosztują, a jak użyjesz dicta opartego na drzewie a nie na hashmapie to już w ogóle kosztują O(logn) i nagle twój pomysł robi się O(nlogn) ;)
Śmieszne jest myślenie ze to co napisałeś będzie 10 razy szybsze. Sprawdź ;)

Ty chyba w ogólne nie kumasz tego zadania.

Wyobraź sobie taki problem, który dotyczy krzyżówek gazetowych z hasłami:

1. w całej krzyżówce jest od 200 do 1000 liter (diagram: 20 x 15 = 300);
   i teraz chcemy z tych liter ułożyć hasło - zwykle popularną sentencję lub przysłowie,
   którego długość jest zwykle około 30, ale może być i 200.

2. mamy bazę sentencji, przysłów, np. 100000 sztuk

wyszukaj teraz wszystkie sentencje, które pasują do tej krzyżówki (np. 500 literek):
raz tym swoim sposobem, a potem z moim usprawnieniem, i porównaj czasy.

raz tym swoim sposobem, a potem z moim usprawnieniem, i porównaj czasy.

Spróbuj, polecam sprawdzić. Dla takich małych liczb nie zobaczysz żadnej różnicy bo te wszystkie dane wejdą do L1 cache procesora. Jakbyśmy mówili o gigabajtach danych, miliardach słów długości setek tysięcy znaków, to kto wie?
Dla danych o których piszesz więcej czasu zajmie włączenie programu czy wczytanie danych niz te całe "obliczenia".

Baza o rozmiarach rzędu sto tys zdań - sentencji na pewno zajmuje sporo miejsca.

Wyjdzie potężna różnica, pewnie nawet więcej niż 10 razy.

BTW. na tych setach, b-drzewach, itp. zabawkach, to już w ogóle byłoby strasznie - obliczenia trwałyby całe godziny, a to ma być robione momentalnie = sekundy!

xD
Nie wierzę że to nie jest troll.
Google mówi ze średnio jedno zdanie ma 15-20 liter słów a słowo ma średnio niecałe 5 liter. Założmy że jedno zdanie ma 20 słów, a jedno słowo 5 liter, w sumie więc jedno zdanie ma 100 znaków. Sto tysięcy takich zdań daje nam 10 milionów znaków, czyli całe 10 MB pamięci. Aktualnie procesory maja już po 12MB w L3 cache.
Napisz jeszcze ze dwa posty i przeniosę do Perełki bo jest potencjał.

Podstawowa zasada pracy dla moderatorów:
moderator nie powinien się wypowiadać na dany temat - jak zwyczajny użytkownik,
bo wtedy od razu widać jak on głupi jest.

the end.

W sensie ze widać od razu jak głupi jest użytkownik? Niestety to jest w dużej mierze prawda :(