Obliczanie ilości możliwych permutacji na łańcuchach znaków.

0

Witam serdecznie wszystkich!
Jestem wciąż początkującą osobą w C++, aczkolwiek znam już podstawy (zmienne, stale, pętle, wyrażenia warunkowe, tablice,wskaźniki w miarę ogarniam (tylko musiałbym je sobie powtórzyć ;) ), funkcje, zmienne tekstowe, zasięgi zmiennych itp.). Przygotowuję się do konkursu i próbuję powoli ogarniać różne algorytmy. Rozwiązywałem zadanie, które polegało na tym, by wypisać ilość możliwych kombinacji łańcucha znaków. Od razu skojarzyłem to z permutacjami i zacząłem pisać program, który korzysta ze wzoru zaprezentowanego na tym filmiku: ( ).
Wyszło mi coś takiego (zaopatrzyłem wszystko w komentarze, by wyjaśnić moje pokrętne rozumowanie ;) ):

#include <iostream>
#include <string>
using namespace std;
int silnia(int dlu);
int main()
{
int i,j,dl,licznik=0,wynik=1,wynik2;
string wyraz;
cin>>wyraz;   //wpisanie wyrazy, którego mamy obliczyć ilość różnych kombinacji
dl=wyraz.length();   //zapisanie dlugosci w zmiennej dl


for( i= 0; i < dl; i++)  //rozpoczecie petli, która analizuje po kolei kazda litere wyrazu
{
    if(wyraz[i] != '.') //sprawdzenie, czy dana literka nie byl juz zliczana
    {
        licznik++; //nadanie biezacej literce statusu, ze wystapila w wyrazie jeden raz
        for( j=i+1; j<dl; j++) //rozpoczecie petli, ktora ma zadanie sprawdzic, czy w dalszej czesci wyrazu nie wystepuje ponownie biezaca literka
        {
            if(wyraz[j]==wyraz[i]) //w przypadku powtorzenia
            {
                licznik++; //dajemy o tym znac licznikowi
                wyraz[j]='.';//oraz w miejsce literki wstawiamy '.', by nie musieć drugi raz analizować tej samej literki i uniknąć błędów
            }
        }
        wynik=wynik*silnia(licznik); //nastepnie  korzystujac ze wzoru !n / (!n1 * !n2 ...) obliczamy dzielnik mnozac po kolei !n1*!n2 przy poszczególnych obrotach petli
    }
    licznik=0; //zerujemy licznik powtorzen
}
wynik= silnia(dl)/wynik; //ocliczamy wynik ze wzoru !n / (!n1 * !n2 ...)
cout<<wynik<<endl; //podaejmy wynik
    return 0;
}
/*************Funkcja obliczajaca Silnia****************************/

int silnia(int dlu)
{
int silnia=1;
 for(int i = 2; i <= dlu; i++)
{
    silnia*=i;
}
return silnia;
}

Wszystko w nim działa jak należy, ale niestety nie działa on w każdym przypadku (możliwe, że przy dłuższych łańcuchach znaków). Czy moje rozumowanie jest odpowiednie, czy może istnieje jakieś prostsze rozwiązanie? (mam na myśli przede wszystkim rozwiązanie oparte o możliwości początkującego programisty)
PS. Zastanawiam się, czy by nie zmienić funkcji obliczającą Silnię na wersje rekurencyjną, czy to by mogło coś przyspieszyć, czy wręcz przeciwnie.
PS2. Jeśli zauważycie, że mój kod przedstawia jakieś złe nawyki (dot. przejrzystości kodu lub dot. wydajności kodu), proszę mi je wytykać, bo im szybciej się o takowych złych praktykach dowiem, tym lepiej.

0

Proponuję zacząć od podania treści zadania. Zdanie "ilość możliwych kombinacji łańcucha znaków" niekompletnie określa problem.

0

Hmm, chodzi o to, by po wpisaniu np. "MAMA" wyskoczyło, że można z tych liter stworzyć 6 różnych kombinacji, czy też słów. (mama, mmaa, maam, amam, aamm, amma). Program ma tylko za zadanie wypisać na wyjście ilość tych możliwości w formie liczby, nie musi ich wszystkich wypisywać.

3

Na konkurs pewnie się nie nada ze względu na sposób użycia STL, ale gdy będziesz go poznawał to możesz wrócić do mojego kodu.

Każde wystąpienie znaku wrzucam do mapy. Dzięki temu, że klucze są w niej unikalne - w przypadku gdy znak już w niej istnieje, zwiększam jej licznik. Następnie liczę dzielnik ze wzoru na ilość permutacji z powtórzeniami. std::accumulate pozwala na dowolną operację na każdym z podanych elementów oraz przechowuje licznik, który będzie naszym wynikiem i w końcu by uzyskać wynik dzielę ilość elementów przez otrzymaną liczbę.

Nagłówki string, map, algorithm, numeric.

std::string word = "mama";

std::map<char, int> letters;
std::for_each(word.begin(), word.end(), [&letters](char letter) { letters[letter]++; });
	
auto factorial = [](int number) { unsigned int result = number; while(--number) result *= number; return result; };

int denominator = std::accumulate(letters.begin(), letters.end(), 1,
	[&factorial](int product, std::pair<char, int> letter) { return product * factorial(letter.second); });
	
int permutations = factorial(word.length()) / denominator;
1

Przy długich słowach szybciej będzie zliczane powtórzenia zapisywać w tablicy (gdzie indeks komórki odpowiada danemu znakowi) zamiast w mapie. Dalej pozostaje już liczenie silni.

Tak jak @Rev radzi, najpierw zlicz wystąpienia liter, a dopiero następnie licz silnie. Zastanów się jak zrobić aby obliczanie wszystkich silni było bardziej wydajne. Wykonywanie nk mnożeń za każdym razem nie jest dobrym wyjściem. Znając N! możesz policzyć (N+M)! robiąc tylko M dodatkowych mnożeń. Jak sobie posortujesz zliczenia rosnąco i będziesz obliczać kolejne silnie od najmniejszej do największej to wystarczy w sumie N mnożeń. Istnieją też sposoby na szybkie obliczanie przybliżonej wartości silni. Możesz się nimi zainteresować.

1 użytkowników online, w tym zalogowanych: 0, gości: 1