[C++] Permutationen (kombinationen)

[hemorieder]

Hi,

ich muss für die Schule in c++ ein Programm schreiben das mir alle Möglichkeiten anzeigt Zahlen zu sortieren, also z.B:

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Ich will garkeinen Code oder so haben, ich kann mir nur garnicht erklären wie ich das anstellen soll, also vom algorithmus her. Also ich will nich die Zahl ausgeben lassen wieviele Möglichkeiten es gibt, sondern wirklich alle Möglichkeiten ausgeben. Ich muss mit Rekursion arbeiten denke ich mal.

Aber wie gesagt, irgendwie fällt mir dazu nix ein. Also wäre es echt cool wenn ihr ne idee hättet.

Ich bedanke mit im vorraus.

mfg

hemorieder

 

[Quidoff]

Handelt es sich jetzt um Permutationen oder Kombinationen? Permutationen sind ja einfach alle möglichen Anordnungen einer n-elementigen Menge (also Fakultät).
Bei Kombinationen musst du ja eine bestimmte Anzahl an Elementen aus einer Menge auswählen.

Wenn du aber schon die Funktion für die Fakultät geschrieben hast, dann musst du ja nur die Formel für die Kombination nehmen.

Wenn du allerdings alle Permutationen ausgeben musst und nicht nur deren Anzahl berechnen musst, dann würde ich einfach ein paar Schleifen schreiben.

Wenn du z.B. 4 Zahlen von 0-9 hast, dann würde ich 4 Schleifen ineinander verschachteln und in der innersten: cout << a << b << c << d << endl;
schreiben.

//edit
Die Fakultät kann man am "einfachsten" mit Rekursion lösen.
Die Funktion hat nur 2 Zeilen. Aber Code wolltest du ja keinen haben.

 

[hemorieder]

also das Programm für die Fakultät habe ich bereits. Und es geht dann eher um das anzeigen der Kombinationen.

Das mit den Forschleifen ist denke ich mal ist ein Problem, weil dann ja auch die Möglichkeiten 111,222,333 auftauchen. Ein weiteres Problem ist, dass dieses Programm für "n" zahlen funktionieren muss. Somit kann ich nicht im vorraus von 3 oder 4 Schleifen ausgehen.

mfg

hemorieder

 

[riod]

int zahl[0]= 1, zahl[1]=5, zahl[2]=3, zahl[3]=4;
int i;

(code stimmt hinten und vorne nicht also nur gucken wie gemacht...)

ausgabe:
while(zahl==true)
{

cout << zahl: << zahl;
i++;
};

----
zum sortieren , versuch mal nen dreiertausch....
a lâ ...

bool check = true;
int temp;

while(check==true)
{
i ++
if(zahl<zahl[y])
{
temp= zahl;
zahl=zahl[y];
zahl[y]=temp;
// so das der die niedrigste zahl an de anfang tauscht
}

// solange bis er nichtmehr tauscht (musst halt gucken wie du das üerprüfst)
}





}

 

[hemorieder]

also irgendwie werde ich dadraus überhaupt nicht schlau, wäre cool wenn du mich in icq mal ansprechen könntest. 147055180

 

[Raechaer]

Du kannst's dir natürlich auch einfach machen und next_permutation aus der STL verwenden:

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;

int main()
{
	vector<int> v;
	vector<int>::iterator iter;
	int n = 3;

	for (int i=1; i <= n; ++i)
		v.push_back(i);

	do 
	{
		for (iter = v.begin(); iter != v.end(); ++iter)
		{
			cout << *iter << " ";
		}
		cout << endl;
	}
	while (next_permutation(v.begin(), v.end()));
}

 

[hemorieder]

ok das ist ja schonmal hammer, danke dafür. Aber wenn man das "per hand" machen wollte, also quasi selber die funktion schreiben, hättest du dafür auch eine idee ?

 

[Raechaer]

Mittels Rekursion solltest du eigentlich recht ellegant alle Permutationen berechnen können, eine Lösungsidee gibt's z.B. auf http://schulinformatik.at/fachdidaktik/programmierung/iteration-rekursion.htm

 

[hemorieder]

ja das ausrechnen der permutationen ist ja auch kein thema, habe ich auch schon. Nur das darstellen der Möglichkeiten das ist mein problem.

 

[Boron]

Darstellen?
Na ja, immer wenn du eine Permutation gefunden hast, dann raus damit auf den Bildschirm.

Das ist der linke Teil in dem Bild "Algorithmus Permutiere()" auf der von Raechaer verlinkten Seite.
Halte dich sklavisch an den Algo, dann kann fast nichts schief gehen.