Variationen mit Wiederholung



  • Guten Tag liebe Programmierer / innen,
    ich benötige ganz dringen eure Hilfe, ich brauche ein Programm wo ich alle Variationen mit Wiederholung ausgegeben bekomme (n^n). Ich habe schon das ganze Internet durchgesucht, habe Leute gefragt die etwas Ahnung davon haben und mir sogar ein Buch gekauft wo man Programmieren lernt, doch nichts hat mir weiter geholfen. Das Buch verstehe ich nicht so ganz und bis ich das Studieren kann werden noch ein paar Jahre vergehen, denn ich bin zur Zeit in einer Ausbildung. Beispielsweise alle Variationen von 1-5 : 11111 bis 55555 Doch was am besten wäre, ist aus 5 Objekten, 20er Reihen zu bekommen : 11111111111111111111 - 55555555555555555555.
    Wäre echt klasse wenn mir jemand helfen könnte, ich bin nämlich voll am verzweifeln und kurz vor´m aufgeben.



  • Ich will mal nicht so sein, auch wenn du zumindest einen Ansatz präsentieren könntest.

    #include <iostream>
    #include <iomanip>
    #include <string>
    
    template<class val, class iter >
    bool next_variation(const iter& first, const iter& last, const val& upper, const val& start, int step)
    {
    	iter next = first;
    	while(next!=last)
    	{
    		*next+=step;
    		if(*next<=upper)
    			return true;
    		*next++=start;
    	}
    	return false;
    }
    
    int main(int argc, char** argv)
    {
    	std::string s="11111";
    	int i=0;
    	do
    	{
    		std::cout << std::setw(4) << ++i << " " << s;
    		// 6 Spalten anzeigen
    		if(!(i%6))
    			std::cout << "\n";
    		else
    			std::cout << "  ";
    
    	} while (next_variation(s.rbegin(), s.rend(), '5', '1', 1));
    }
    

    Versuch das nachzuvollziehen:
    next_variation setzt den Startwert des momentanen Index rauf, bis der Maximalwert erreicht ist, anschließend wird der Index erhöht und das Spiel beginnt von vorne.
    Nach jeder Änderung - sofern sie innerhalb der Grenzen geblieben ist - wird true zurück- und der String ausgegeben. Reverse-Iteratoren sorgen dafür, dass die Änderung von hinten nach vorne geschieht.
    Mit 20er Reihen weiß ich nicht genau, was du meinst, gib den String einfach mehrfach hintereinander aus.



  • Noch ein Beispiel:

    #include <stdio.h>
    
    void countUp (char *s, int idx)
    {
        if (++s[idx] == '6')
        {
            s[idx] = '1';
            countUp (s, idx+1);
        }
    }
    
    int main()
    {
        char s[] = "11111111111111111111";
        for(;;)
        {
            puts (s);
            countUp (s, 0);
        }
    }
    

    Das Programm wird bei der 5^20. Ausgabe wohl abstürzen. Aber so lange lässt du es vermutlich nicht laufen. 😉



  • Super,
    in erster Linie vielen Dank das ihr mir hilft. Tut mir Leid dref falls ich mich Blöd ausgedrückt habe. Beides geht in die richtige Richtung. ( Kein Wunder wenn man die Richtigen fragt 😉 ). Als ich versucht habe die zahlen einzugeben die ich tatsächlich brauche ( 13^13 ) hat es nicht funktioniert 😞 könnt ihr mir bitte sagen wodran das liegt und wie ich das richtig mache ?



  • Fatlum schrieb:

    Super,
    in erster Linie vielen Dank das ihr mir hilft. Tut mir Leid dref falls ich mich Blöd ausgedrückt habe. Beides geht in die richtige Richtung. ( Kein Wunder wenn man die Richtigen fragt 😉 ). Als ich versucht habe die zahlen einzugeben die ich tatsächlich brauche ( 13^13 ) hat es nicht funktioniert 😞 könnt ihr mir bitte sagen wodran das liegt und wie ich das richtig mache ?

    Was meinst du mit 13^13? Eine Sequenz von 13 Zeichen, aus einem Zeichensatz von 13 möglichen Zeichen?



  • wenn ich 13 verschiedene Farben haben, bräuchte ich dann alle Möglichkeiten mit zurücklegen. Das wären dann : 302.875.106.592.253 Möglichkeiten. Meinst du das ist möglich ?



  • Fatlum schrieb:

    wenn ich 13 verschiedene Farben haben, bräuchte ich dann alle Möglichkeiten mit zurücklegen. Das wären dann : 302.875.106.592.253 Möglichkeiten. Meinst du das ist möglich ?

    Eine recht kleine Zahl. 😉
    Müsste aber noch in long long passen.



  • Und wie sieht dann der Code aus ? 🙄 ( Ich weis ich bin total Ahnungslos dadrin 😃 )



  • Wieviel Zeit hast du denn alle Kombinationen zu erzeugen und zu speichern? 🙄
    Selbst bei 1 Milliarde Zahlen pro Sekunde bräuchte das Programm immer noch 302875 Sekunden (~ 3,5 Tage)...

    Und der Speicherplatz dafür beträgt dann sizeof(long long) * (13^13) Bytes = 8 * 302875106592253 Bytes = 2256595 GB = 2203 TB = 2,15 PB (petabyte).



  • Darüber habe ich mir noch keine Gedanken gemacht 😮



  • Th69 schrieb:

    Und der Speicherplatz dafür beträgt dann sizeof(long long) * (13^13) Bytes = 8 * 302875106592253 Bytes = 2256595 GB = 2203 TB = 2,15 PB (petabyte).

    Jetzt mach ihm keine Angst. Er muss ja nicht alles speichern. 😃



  • Erklär mal, welches Problem Du lösen willst.



  • Fatlum schrieb:

    Als ich versucht habe die zahlen einzugeben die ich tatsächlich brauche ( 13^13 ) hat es nicht funktioniert 😞 könnt ihr mir bitte sagen wodran das liegt und wie ich das richtig mache ?

    int main()
    {
    	const unsigned num = 13;
    	unsigned s[num];
    	unsigned startValue = 1;
    	unsigned endValue = startValue+num-1;
    
    	for(size_t i=0;i<num;++i)
    		s[i]=startValue;
    
    	int i=0;
    	do
    	{
    		std::cout << std::setw(4) << ++i << " ";
    		for(size_t k=0;k<num;++k)
    			std::cout << std::setw(2) << s[k] << " ";
    		std::cout << "\n";
    	} while (next_variation(&s[0], &s[num], endValue, startValue, 1));
    

    Bei 1000 Ausgaben pro Sekunde kannst du th69s Wert mit 1.000.000 multiplizieren. Ich will ehrlich sein, die Zeit habe ich wohl nicht mehr hier auf Erden...
    Es ist aber auch generell der falsche Ansatz, denn:

    Furble Wurble schrieb:

    Erklär mal, welches Problem Du lösen willst.



  • erwähnen könnte man auch noch
    http://en.cppreference.com/w/cpp/algorithm/next_permutation

    das zeit-problem besteht aber natürlich weiterhin 😉


Anmelden zum Antworten