Anagramy i rekurencja

Gdyby ktoś mógłby mi pomóc, byłbym bardzo wdzięczny. Przez ten głupi program nie mogę spać po nocach.

Mam napisać program, wczytujący od użytkownika wyraz, i wypisujący na ekranie wszystkie anagramy tego wyrazu.

Wskazówka(mnie ona niewiele pomaga, bo nie wiem jak ją przełożyć na kod programowy): załóżmy (chwilowo), że dysponujemy funkcją, która potrafi podać wszystkie anagramy wyrazów krótszych niż 4 literowe. W takiej sytuacji, dla wyrazu np. "noga", lista permutacji będzie zawierać: n + permutacje("oga"), o + permutacje("nga") itd.Z kolei, permutacje np. "oga" będzie zawierać "o" + permutacje "ga", "g" + permutacje "oa" itd.Na tej zasadzie można skonstruować funkcję rekurencyjną, która będzie stanowiła rozwiązanie zadania.

Musi to być to napisane z użyciem funkcji rekurencyjnej, gdyby nie to nie było by problemu, bo bez kłopotu napisałem taki program ale bez rekurencji( z użyciem funkcji sort() i next_permutation()).

proszę ... listing2 ... przerób sobie jak ci wygodnie.

Nie wiem dlaczego ale nie chce mi tego programu przepuścić kompilator, proszę o pomoc.

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

void permute( string prefix, string s )
{
    if ( s.size() <= 1  )
        cout <<prefix <<s <<"\n";
    else
        for ( char *p = s.begin(); p <s.end(); p++ )
        {
            char c = *p;
            s.erase(p);
            permute( prefix + c, s );
            s.insert( p, c );
        }
}

main()
{
    permute( "", "123456" );
    return 0;
}

dostajesz niemalże gotowy kod i nie potrafisz go jeszcze wykorzystać? Nie przekopiuje ci całego ale zacznę za ciebie, możesz to zrobić np tak:

 string::iterator it = s.begin(); 
for (; it != s.end(); ++it)

tylko teraz odpowiednio pozamieniaj. Swoją drogą właśnie dlatego nie daje gotowców, nie próbowałeś nawet zrozumieć tego kodu tylko ślepo go kompilować. Na jego podstawie powinieneś zbudować swój wszak pytałeś o algorytm.

Napisałem taki program, niestety w linii z funkcją s.insert kompilator wykrywa błąd złej kompilacji z char na const char, nie wiem jak to naprawić, proszę o pomoc.

"main.cpp|18|error: invalid conversion from 'char' to 'const char*'|"

 #include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

void permute( string prefix, string s )
{
    if ( s.size() <= 1  )
        cout <<prefix <<s <<"\n";
    else

        for ( int i=0 ; i< s.size() ; i++)
        {

            char c = s[i];
            s.erase(s[i]);
            permute( prefix + c, s );
            s.insert(s[i],c);
        }

}

main(int argc, char * argv[])
{
    permute( "", "ttgftyg" );
    return 0;
}

Wybacz moje haterstwo ale szlag mnie trafia na widok takiego lenistwa ... nie potrafisz nawet sprawdzić jakie parametry przyjmują odpowiednie metody. Ślepo edytujesz kod na chybł/trafił. Tak to nigdy nie trafisz. Możesz to zrobić iteratorami albo iterując (czyli tak jak ty zacząłeś). Czego byś nie wybrał metody te posiadają odpowiednie wersje do obu tych rozwiązań. Zacznijmy od erase, nie wiem czy rozumiesz po co ona tam jest ale wytłumaczę ci ... jest ona po to tam wywołana aby usunąć znak z łańcucha, który obecnie przeglądasz czyli na tej pozycji, na której się znajdujesz i tylko jeden znak. Czyli musisz ją wywołać w twoim wypadku tak:

s.erase(i, 1);

to co ty piszesz to są brednie.
Wywołanie rekurencyjne masz dobrze (bo nic tam zmieniać nie musiałeś :] ) pozostaje insert. To zostawiam tobie do roboty. klik i czytaj jakie argumenty może przyjąć ta metoda. Podpowiem s.begin() jest typu string::iterator. Wykaż się troszkę inwencją i pokaż, że nie próbujesz napisać programu za trudnego jak na twoje umiejętności.
Poza tym zakup jakąś porządną książkę i wspieraj się nią podczas prób pisania takich programów. Przypominam, że ten temat był o anagramach, a nie wykorzystaniu klasy string. Jak jej używać masz chyba we wszystkich pozycjach traktujących o podstawach c++ i standardowej bibliotece!

Wykaż się troszkę inwencją i pokaż, że nie próbujesz napisać programu za trudnego jak na twoje umiejętności.

Chyba masz racje nie jestem w stanie napisać tego programu, nadal nie wiem gdzie popełniam błąd w funkcji insert, mimo twoich wskazówek, przepraszam za kłopot, no trudno. Dziękuje ze pomoc i poświęcony czas.

Możesz tak:

void permute( string prefix, string s )
{
    if (s.size() <= 1)
        cout <<prefix <<s <<"\n";
    else
    {
        string::iterator it = s.begin();
        for (; it != s.end(); ++it)
        {
            char c = *it;
            s.erase(it);
            permute( prefix + c, s);
            s.insert(it, c);
        }
    }
}

Możesz i tak:

void permute( string prefix, string s )
{
    if (s.size() <= 1)
        cout <<prefix <<s <<"\n";
    else
    {
        for (int i = 0 ; i < s.size() ; i++)
        {
            char c = s[i];
            s.erase(i, 1);
            permute(prefix + c, s);
            s.insert(s.begin() + i, c);
        }
    }
}

Dobra pomęczyłeś się, nic z tego to masz :) Przejrzyj tą stronę co podlinkowałem wyżej i zobacz jak stosować standardową bibliotekę.

Wielkie dzięki! Uratowałeś mi życie.