Kombination/Permutation

firefly_85

Hallo allerseits,

Ich hab da ein kleines Problem.

Ich brauch ein Programm das mir für eine 39stellige Zahl alle Kombinationen angibt.
Ich habs nur mit 39 for-Schleifen geschafft, das ist natürlich Wahnsinn.
Da muss es doch eine einfacher Lösung geben. Jemand eine Idee.

Besipiel für eine stellige Zahl wäre so:

for(int z1=0;z1<=9;z1++)
  {
    for(int z2=0;z2<=9;z2++)
	{
	  for(int z3=0;z3<=9;z3++)
	  {
	    for(int z4=0;z4<=9;z4++)
		{
		  for(int z5=0;z5<=9;z5++)
		  {
		    cout << z1 << z2 << z3 << z4 << z5 << endl;
		  }
		}
	  }
    }
  }

Man kann sich leicht denken, dass das für 39 Stellen gigantisch und unübersichtlich wird.

Bin für jede Hilfe dankbar!

Lg

Jockelx

~~Überleg mal, ob es dafür nicht bessere Schleifengrenzen als von 0 bis 9 gibt.~~
Mmh, war so die erste Idee, ist aber auch nur semi-gut.

volkard

Weißt Du, wie ein mechanischer Kilometerzähler funktioniert? Wenn eine Ziffer von 9 auf 0 umschlägt, wird der linke Nachbar um eins erhöht. So kann man's machen.

Oder rekursiv.

Bashar

Machs mit Rekursion. Alle Kombinationen auf n Stellen (für n>=1) bekommst du, indem du alle Kombinationen von n-1 Stellen berechnest und jeweils 0 bis 9 davorschreibst.
Soviel zur Theorie, ich würd mir aber auch mal Gedanken um den Zeitbedarf machen. Wenn wir mal großzügig davon ausgehen, dass du in einer Sekunde 10^9 Kombinationen schaffst, dann brauchst du 10^30 Sekunden, also irgendwas bei 10^22 Jahre.

pumuckl

Womit wir wieder bei einer der Standardfragen wären: was willst du damit erreichen? Gibt bestimmt ne einfachere Methode, dein eigentliches Problem zu lösen.

knivil

39stellige Zahl alle Kombinationen

Schon mal ueberlegt, wieviele Kombinationen es gibt und wie lange es dauert, sie anzugeben?

firefly_85

hallo,

Danke schon mal für die zahlreichen Antworten.

Also im speziellen gehts um ein multivariates quadratisches Gleichungssystem.
Stichwort: NP-hard

Im Detail schaut das dann so aus:

fi=fi(x1,...,xn)=ci
mit i=1..17, xn=39, ci: vorgegeben konstanten
fi: Funktionen

Alle fi müssen mit einem Vektor aus x=[x1,..,xn] erfüllt werden.
Analytisch leider nicht möglich.
Alle x können Werte von 1..17 auf dem vorgegebenen Körper annehmen, wobei ich eine Lösung schon zwischen 0 und 2 erwarte.
D.h. im Endeffekt sind es dann nicht 10^39 Möglichkeiten sondern "nur" 3^39.

Ich hab mir das dann so vorgestellt, dass die Kombinationen in jede Funktion eingehen und überprüft werden und wenn eine Kombination stimmt -> Ausgabe

Ich weiß leider nicht wie ich es sonst am besten angehen soll.

SeppJ

Toll, dann sind's nur noch 200 CPU-Jahre. Während das für verteiltes Rechnen durchaus eine realistisch schaffbare Zahl ist, solltest du dir vielleicht besser mal überlegen, ob du
a) Nicht vielleicht ein paar mehr Zusatzinformationen hast, die das Problem vereinfachen könnten
b) Überhaupt die volle Lösung brauchst.

Was soll's denn werden wenn es fertig ist?

pumuckl

Für sowas gibts numerische Lösungsansätze. Mit brute force kommst du da nicht weit.
Wenn ich mich richtig erinnere wäre ein Ansatz z.B., di(X) = ||fi(X)-ci|| zu definieren und die Minima zu suchen.

Für solche Probleme gibts ein nettes Buch: "Numerical Recipes in C/C++", wie du das Problem an sich erstmal in einen fassbaren Rahmen reduzieren kannst findet sich sicher im Numerik-Buch deiner Wahl.

firefly_85

pumuckl schrieb:

Für solche Probleme gibts ein nettes Buch: "Numerical Recipes in C/C++", wie du das Problem an sich erstmal in einen fassbaren Rahmen reduzieren kannst findet sich sicher im Numerik-Buch deiner Wahl.

Ja das hab ich auch schon durchforstet. In dem steht leider nix drin.
Es gibt sicher noch Algorithmen sind aber leider extrem schwer zu finden.
Irgendwas mit Gröbnerbasis oder so.

Danke für eure Hilfe..Zumindest weiß ich mal dass es so nicht geht.