[C++] Algorytm - wszystkie możliwe kombinacje zbioru

Question

Witam, mam problem jak w C++ rozwiązać ten problem:

Dany jest zbiór/tablica możliwych ruchów P np. {'a', 'b', 'c', 'd', 'e'}, użytkownik podaje wartość d np 7. Tablica P może być różnej długości i różnymi od elementami. Następnie chce wygenerować pewną ilość zbiorów o długości 7 (niech będzie postaci string) taką, że każdy z nich był inny, ale by każdy ich element był z tablicy P.

Czyli np:

• "aaaaaaa"
• "aaaaaab"
• "aaaaaac"
• ...
• "dedcdea"
• ...
• "eeeeeee"

Pomocy! Nie mam pomysłu :( Mogę prosić o jakieś sugestie? 

EDIT1: Dodatkowy inny zestaw danych:
Zbiór P {1, 2, 3} , d=2

• {1 1}
• {1 2}
• {1 3}
• {2 1}
• {2 2}
• {2 3}
• {3 1}
• {3 2}
• {3 3}

EDIT2: Można korzystać z różnych bibliotek (np <algorithm>).

Answer 1

Tutaj masz ładnie napisany kod z wyjaśnieniem: http://sebastianpawlak.com/pl/Informatyka/Algorytmy/Permutacje/index.html . W twoim przypadku zamiast tablicy int będzie tablica char. Dodatkowo jeżeli będziesz potrzebował wyświetlić więcej niż n! zbiorów to po wypisaniu tych n! zmień wartość drugiego elementu na pierwszy itd. Kod, który masz tam podany musisz lekko zmodyfikować(masz tam na stałe podaną silnie), ale masz tam także algorytm podany, więc sobie raczej poradzisz.

Comments

To jeszcze nie to (albo nie potrafię przetworzyć tego w myślach na moje). W tym kodzie permutuje się tablice t. Ja u siebie mam na podstawie jednej tablicy utworzyć wiele innych. Elementy mogą się powtarzać w dodatku czyli dla zbioru {1,2,3} i długości wyjściowych zbiorów 2 (np podanych przez użytkownika) mam wypisać:

• 1 1
• 1 2
• 1 3
• 2 1
• 2 2
• 2 3
• 3 1
• 3 2
• 3 3

---

Tak jak napisałem, aby elementy się powtarzały musisz zmieniać elementy kolejno. Tam też używasz tylko jednej tablicy.

---

Czy mógłbyś mi powiedzieć co to znaczy "zmieniać elementy kolejno"? Jedyne co udało mi się ustalić co do Twojej odpowiedzi to to, że silnia w mainie nie jest mi potrzebna. Tzn ilość odpowiedzi jest jak:
(ilosc elementów pierwszego zbioru) ^ (ilosc elementów  drugiego zbioru)
Czyli na jego podstawie mam zrobić warunek trwania pętli?

---

Ten algorytm wykonuje kombinacje bez powtórzeń. Jeśli chcesz mieć kombinacje z powtórzeniami to go modyfikujesz w następujący sposób: na początek program się wykona w całości dla jakiegoś zbioru. Następnie zamiast się zakończyć zmieniasz wartość drugiego elementu na wartość pierwszego elementu np. zbiór A={A,B,C} przekształcasz w zbiór A={A,A,C} i analogicznie aż do zbioru samych A. Następnie robisz to samo z B i C.

---

I oczywiście dla każdego zbioru się ten program wykona.

---

Co prawda zrobiłem to chwilowo jakoś inaczej, ale daję najlepszą za jakieś podejście do tematu i męczenie się ze mną :D

Zrobiłem tak, bo jakoś bardziej mi pasowało:

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;

int power(int podst, int wyk){

    int k=1;
    for(int i=1; i<=wyk; i++)
    {
        k*=podst;
    }
    return k;
}

void wypisz(vector<string> C, vector<string> A){

    cout<<"[------> Kombinacje 1-elementowe\n"
    <<"[------> Ilosc kombinacji: "<<C.size()<<endl;

    for(int i=0, j=1, k=0; i<C.size(); i++, k++)
    {
        if(i!=0) if(C[i].size()>C[i-1].size())
        {
            j++;
            k=0;
            cout<<endl;
            cout<<"[------> Kombinacje "<<j<<"-elementowe\n"
            <<"[------> Ilosc kombinacji: "<<power(A.size(), C[i].size())<<endl;

        }

        if(i<99) cout<<"0";
        if(i<9) cout<<"0";
        cout<<i+1<<" : ";
        if(k<99) cout<<"0";
        if(k<9) cout<<"0";
        cout<<k+1<<" )--> "<<C[i]<<endl;
    }
}

int main()
{
    vector<string> A;
    vector<string> B;
    //vector<string> C;
    vector<string> D;

    int outsize = 5;

    A.push_back("a");
    A.push_back("b");




    B=A;

    //for(int i=0; i<B.size(); i++) B.push_back(A[i]);

    int start = clock();

    for(int k=0; k<outsize-1; k++)
    {
        for(int i=0; i<B.size(); i++)
        {
            for(int j=0; j<A.size(); j++)
            {
                //C.push_back(B[i]+A[j]);
                D.push_back(B[i]+A[j]);
            }
        }
        B=D;
        if(k<outsize-2) D.clear();
    }

    wypisz(D,A);
    int stop = clock();
    cout<<double(stop - start)/CLOCKS_PER_SEC<<endl;

    return 0;
}

Chociaż i tak będę to musiał zmienić, bo to jest zbyt pamięciożerne 

Answer 2

ASCII. Dodajesz 1 do ostatniego znaku (jeżeli masz a - zmienia się na b) tylko jeżeli dojdziesz do z, to musisz ifem dodać 1 do następnej, a ostatnią literę zmienić na a. I tak do samego końca.

Comments

Tablica P może wyglądać np tak { 'R', 'E', 'z', 'd' }. Twoja odpowiedz mi nic nie mówi co do reszty treści;/

---

To możesz użyć funkcji tolower(), która zmienia litery na mniejsze i zmiennej pomocniczej, jeśli nie chcesz utracić rzeczywistej wartości xD

---

Mi chodzi jak ułożyć pętle by wygenerować te wszystkie możliwe ciągi znaków.