Permutationen / Variationen

[LinkinMaster]

Hallo zusammen,
ich hoffe ihr könnt mir helfen, ich verzweifle langsam an der Aufgebe!
Also ich soll für 4 oder 5 Knotenpunkte alle möglichen Variationen ausgeben ohne eine Wiederholung der Punkte (sprich 1-1-1-1) .

Beispiel Kombination aus 3 Knotenpunkten:

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

Ich habe kein Problem alle Variationen von Hand aufzuschreiben aber ich komm zum verrecken nicht aus den Algorithmus um es zu programmieren.

Code: Alles auswählen

#include <stdio.h>

#define DIMENSION 4

int main(void){

	int i,j,k,l;		// Zähler Schleifendurchläufe

	// Dimensionierung der Durchläufe
	int Kombinationen2Konten, Kombinationen3Konten, Kombinationen4Konten, Kombinationen5Konten;

	if(DIMENSION==4){
		Kombinationen2Konten=12;		// Anzahl möglicher Kominationen bei 2 Knoten
		Kombinationen3Konten=24;
		Kombinationen4Konten=24;
		Kombinationen5Konten=0;
	}
	else if(DIMENSION==5){
		Kombinationen2Konten=20;
		Kombinationen3Konten=60;
		Kombinationen4Konten=120;
		Kombinationen5Konten=120;
	}

	int Feld[Kombinationen2Konten+Kombinationen3Konten+Kombinationen4Konten+Kombinationen5Konten][DIMENSION];

	// Generrierung der Streckenkombinationen

	for(i=1; i<=Kombinationen2Konten; i++){

		for(j=0; j<=DIMENSION; j++){
			Feld[j][0]=j+1;

			for(k=1; k<=DIMENSION; k++){
				if(Feld[j][k]==Feld[j][0]){
				Feld[j][k]=k;
				printf("%i-%i-%i-%i\n",Feld[i][1],Feld[i][2],Feld[i][3],Feld[i][4]);
				}
				else{
					continue;
				}
			}
		}
	}
	return 0;
}

[LinkinMaster]

Hallo zusammen,
ich habe jetzt eine Variante gefunden die für mich funktioniert aber alles andere als elegant ist. Falls einer eine effizienteren Algorithmus hat immer her damit

Code: Alles auswählen

#include <stdio.h>

#define DIMENSION 4		// Hier kann man für 4 oder 5 Knotenpunkte berechnen lassen


int main(void){
	int Knoten[5]={1,2,3,4,5};
	int Variation[5]={0};
	int i,j,k,l,m;

	// Streckenkombinationen bei 2 Knoten
	for(i=0; i<DIMENSION; i++){
		Variation[0]=Knoten[i];
		for(j=0; j<DIMENSION; j++){
			if(Variation[0]==Knoten[j]){
				continue;
			}
			else{
				Variation[1]=Knoten[j];
				printf("%i-%i\n",Variation[0],Variation[1]);
			}
		}
	}

	// Streckenkombinationen bei 3 Knoten
	for(i=0; i<DIMENSION; i++){
		Variation[0]=Knoten[i];
		for(j=0; j<DIMENSION; j++){
			if(Variation[0]==Knoten[j]){
				continue;
			}
			else{
				Variation[1]=Knoten[j];
				for(k=0; k<DIMENSION; k++){
					if(Variation[0]==Knoten[k] || Variation[1]==Knoten[k]){
					continue;
					}
					else{
						Variation[2]=Knoten[k];
						printf("%i-%i-%i\n",Variation[0],Variation[1],Variation[2]);
					}
				}
			}
		}
	}

	// Streckenkombinationen bei 4 Knoten
	for(i=0; i<DIMENSION; i++){
		Variation[0]=Knoten[i];
		for(j=0; j<DIMENSION; j++){
			if(Variation[0]==Knoten[j]){
				continue;
			}
			else{
				Variation[1]=Knoten[j];
				for(k=0; k<DIMENSION; k++){
					if(Variation[0]==Knoten[k] || Variation[1]==Knoten[k]){
					continue;
					}
					else{
						Variation[2]=Knoten[k];
						for(l=0; l<DIMENSION; l++){
							if(Variation[0]==Knoten[l] || Variation[1]==Knoten[l] || Variation[2]==Knoten[l]){
								continue;
							}
							else{
								Variation[3]=Knoten[l];
								printf("%i-%i-%i-%i\n",Variation[0],Variation[1],Variation[2],Variation[3]);
							}
						}
					}
				}
			}
		}
	}

	// Streckenkombinationen bei 5 Knoten
	if(DIMENSION==5){
		for(i=0; i<DIMENSION; i++){
			Variation[0]=Knoten[i];
			for(j=0; j<DIMENSION; j++){
				if(Variation[0]==Knoten[j]){
					continue;
				}
				else{
					Variation[1]=Knoten[j];
					for(k=0; k<DIMENSION; k++){
						if(Variation[0]==Knoten[k] || Variation[1]==Knoten[k]){
						continue;
						}
						else{
							Variation[2]=Knoten[k];
							for(l=0; l<DIMENSION; l++){
								if(Variation[0]==Knoten[l] || Variation[1]==Knoten[l] || Variation[2]==Knoten[l]){
									continue;
								}
								else{
									Variation[3]=Knoten[l];
									for(m=0; m<DIMENSION; m++){
										if(Variation[0]==Knoten[m] || Variation[1]==Knoten[m] || Variation[2]==Knoten[m] || Variation[3]==Knoten[m]){
										continue;
										}
										else{
											Variation[4]=Knoten[m];
											printf("%i-%i-%i-%i-%i\n",Variation[0],Variation[1],Variation[2],Variation[3],Variation[4]);
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}

	return 0;
}

[nufan]

Hallo LinkinMaster!

Ich komme leider etwas spät zum Antworten, aber ich hätte einen allgemeineren Lösungsvorschlag.

Dein Ziel ist es, DIMENSION Zahlen zwischen 1 und einer Obergrenze (nennen wir sie mal ANZAHL_KNOTEN) zu finden.

Nehmen wir das von dir gezeigte Beispiel an:
DIMENSION = 2
ANZAHL_KNOTEN = 3

Spielen wir das ganze durch.

Auswahl 1, 1. Zahl:
Wir versuchen zuerst die kleinste Zahl zu verwenden, also 1. Du willst keine Duplikate innerhalb einer Auswahl, deshalb muss zuerst überprüft werden, ob die Zahl schon verwendet wurde. Nachdem wir zu diesem Zeitpunkt noch keine Auswahl getroffen haben, können wir im ersten Schritt 1 auswählen.

Auswahl 1, 2. Zahl:
Auch bei der zweiten Auswahl beginnen wir wieder bei 1 zu zählen. Allerdings haben wir diese schon verwendet, deswegen erhöhen wir den Wert und fügen die Zahl 2 zur Auswahl hinzu.

An diesem Punkt haben wir DIMENSION Zahlen ausgewählt und wir können sie ausgeben: 1-2

Auswahl 2, 2. Zahl:
2. Zahl? Ja. Anstatt komplett von vorne zu beginnen, gehen wir an dieser Stelle nur einen Schritt zurück. Wir gehen zur 3 weiter: 1-3

DIMENSION Zahlen wurden ausgewählt: 1-3

ANZAHL_KNOTEN wurde erreicht, die letzte Zahl kann nicht mehr erhöhen. Wir gehen nun noch einen Schritt zurück.

Auswahl 3, 1. Zahl:
An Position 1 steht der Wert 1. Für diese Ausgangssituation haben wir allerdings bereits alle möglichen Permutationen erstellt. Wir erhöhen also an der ersten Stelle auf den Wert 2.

Auswahl 3, 2. Zahl:
Beginnen wir wieder bei 1 zu zählen. Aktuell ist diese auch noch frei, also wählen wir sie aus.

DIMENSION Zahlen wurden ausgewählt: 2-1

Auswahl 4, 2. Zahl:
Erhöhen wir die zweite Stelle, bekommen wir 2. Allerdings wurde dieser Wert bereits an der ersten Stelle verwendet und wir springen direkt zu 3 weiter.

DIMENSION Zahlen wurden ausgewählt: 2-3

ANZAHL_KNOTEN wurde erreicht, die letzte Zahl kann nicht mehr erhöhen. Wir gehen nun noch einen Schritt zurück.

Auswahl 5, 1. Zahl:
An Position 1 steht der Wert 2. Für diese Ausgangssituation haben wir allerdings bereits alle möglichen Permutationen erstellt. Wir erhöhen also an der ersten Stelle auf den Wert 3.

Auswahl 5, 2. Zahl:
Beginnen wir wieder bei 1 zu zählen. Aktuell ist diese auch noch frei, also wählen wir sie aus.

DIMENSION Zahlen wurden ausgewählt: 3-1

Auswahl 6, 2. Zahl:
An Position 2 wird auf 2 erhöht. Diese Zahl ist noch unbenutzt und wird ausgewählt.

DIMENSION Zahlen wurden ausgewählt: 3-2

Wird die zweite Position erhöht, kommen wir auf die bereits verwendete 3 und haben ANZAHL_KNOTEN erreicht. Wir gehen noch einen Schritt zurück, allerdings wurde auch hier ANZAHL_KNOTEN bereits erreicht. Es gibt keine weiteren Möglichkeiten mehr, fertig.

Dieses Schema lässt sich unabhängig von der Anzahl der Dimensionen realisieren. Du merkst allerdings, dass du für jeden Schritt einen Zustand brauchst, zu dem du zurückkehren kannst, wenn du mit allen Permutationen fertig bist. Das ist ein Anzeichen für ein rekursives Problem: https://www.proggen.org/doku.php?id=c:t ... #rekursion

Was ist der Vorteil einer rekursiven Lösung gegenüber der von dir? Du hast aktuell für jede Dimension eine Schleifen-Ebene und fixe hardcodierte Array-Indizes. Du hast vielleicht schon gemerkt, dass das bei 5 Dimensionen etwas unübersichtlich und chaotisch wurde. Bei einer rekursiven Lösung ist das nicht der Fall. Sie benötigt für 100 Dimensionen gleich viel Code wie für 2 und kommt komplett ohne fixe Indizes aus.

[LinkinMaster]

Ok, vielen Dank für die ausführliche Lösungsvorschlag!
Werde mich auf jeden Fall mal um eine rekusive Umsetzung meines Problems kümmern.