Układanie wyrazów

asdasd666 · Post autor: **asdasd666** » 1 gru 2014, o 15:52

Witam. Mam za zadanie wymyślić algorytm który ciąg z literami P,I,E,S uporządkuje w ten sposób aby utworzyć wyrazy PIES. Np mam PPIIEESS i musimy ułożyć PIESPIES. Do dyspozycji mam tylko jeden typ przełożenia - czwórka(dokładnie i tylko czwórka) znaków z dowolnego miejsca obok siebie na koniec ciągu. Więc ciąg wyjściowy to jak najwięcej słów PIES oraz ewentualne śmieci na prawym końcu ciągu. Jedyne co przychodzi mi na razie do głowy to brute force czyli takie przekładanie aż otrzymamy wszystkie układy. Ale nawet przy tej metodzie nie wiem jaki mógłby być warunek końca, tzn ile np jest wszystkich możliwości mając tylko tą jedną operacje przełożenia? Jakby był ktoś tak miły i spróbował nakierować mnie na jakieś rozwiązanie to byłbym bardzo wdzięczny. Proszę o pomoc. Pozdrawiam.

Everard · Post autor: **Everard** » 1 gru 2014, o 18:46

Jesteś pewien że rozwiązanie w ogóle zawsze istnieje? Jeżeli nasz startujący ciąg to PEISP, iterując Twoją operację w jedyny możliwy sposób dostajemy
PPEIS
SPPEI
ISPPE
EISPP
PEISP

więc nigdy nie dostajemy nigdzie PIES...

asdasd666 · Post autor: **asdasd666** » 1 gru 2014, o 20:03

Masz racje rozwiązanie nie zawsze istnieje ( algorytm ma to uwzględniać ). Masz może jakiś pomysł? Jedyne co mi przychodzi to głowy to sprawdzanie kolejnych liter, jesli jest zle to przekładamy. Ale też nie za bardzo wiem kiedy się zatrzymać. Co więcej czy jeśli tak postępując i już na drugiej pozycji nie uda mi się ustawić wymaganej litery tzn ze w ogóle się nie da ? Ciężko mi z tym idzie...

asdasd666 · Post autor: **asdasd666** » 26 gru 2014, o 16:37

Hmm.. Jako że dalej borykam się z tym problemem to mam takie pytanie bardziej ogólne. Ile jest wszystkich możliwych ciągów ( niekoniecznie różnych - tzn ten sam ciąg otrzymany w inny sposób jest rozróżnialny ) jakie możemy otrzymać przy pomocy tej operacji dla ciągu rozmiaru n ?
dla n = 4 mamy 1
dla n = 5 mamy 5
dla n = 6 ... ?