4. Alle Permutationen von z.b. A-B-C ausgeben - Heap's Algorithmus

Alle Permutationen von z.b. A-B-C ausgeben - Heap's Algorithmus

  • K

    hallo,
    wir sollen den heap's algorithmus programmieren, siehe hier https://en.wikipedia.org/wiki/Heap's_algorithm (ein pseudocode).

    Wenn man z.b. das programm mit heap 2 startet in der konsole, soll es A-B und B-A ausgeben, bei heap 3 alle permutationen von A-B-C, etc.

    Ich hab es jetzt soweit:

    #include<stdio.h>

char A[26]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};

void swap(char *x, char *y){
	int tmp=*x;

	*x=*y;
	*y=tmp;
}

void generate(int n){
	if (n==1){
		int a;
		for(a=0;a<n-1;a++){
			int permutation=0;
			++permutation;
			printf("%d.: %c", permutation ,A[a]);
		} 
		printf("\n");
	}
	else{
		int i;
		for(i=0;i<n-1;++i){
			generate(n-1);
			if(n%2==0) swap(&A[i],&A[(n-1)]);
			else swap(&A[0],&A[(n-1)]);
		}
		generate(n-1);
	}
}

int main(int argc,char *argv[]){
	int n;
	if(argc<2 || (n=atoi(argv[1]))<0){
		printf("Usage: %s <number-of-elements>\n",argv[0]);
		return -1;
	}					
	generate(n);
	return 0;
}

    allerdings bekomm ich eine warnung:
    heap.c:35:2: warning: implicit declaration of function 'atoi' [-Wimplicit-function-declaration]
    (diesen code am anfang mit dem argc haben wir nicht näher erklärt bekommen, der ist wohl nur dafür da damit man das programm entsprechend mit heap *anzahl der elemente* in der konsole starten kann)

    und es gibt mir nichts aus außer neue zeilen. Also wenn ich heap 2 eingebe bekomm ich nur ein paar neue zeilen und sonst nichts. Weiß wer was da falsch ist?
    mfg

    0
  • Mod

    Der &-Operand soll wohl vor dem A stehen, nicht dem i.

    edit: Ähhh, ja. Das sieht jetzt etwas komisch aus als Antwort, wenn du die Frage einfach wegeditierst 😕

    0
  • K

    Ja ich habs grad bemerkt (bevor ich deine antwort gelesen hab), deswegen hab ichs schnell weg editiert xD

    Ich hab jetzt den & operant richtig hingeschrieben.

    (Davor hab ich in zeile 26 swap A[&i] stehen gehabt, aber richtig ist natürlich swap &A[i])

    Ja jetzt sieht das programm so aus:

    #include<stdio.h>

char A[26]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};

void swap(char *x, char *y){
	int tmp=*x;

	*x=*y;
	*y=tmp;
}

void generate(int n){
	if (n==1){
		int a;
		for(a=0;a<n-1;a++){
			int permutation=0;
			++permutation;
			printf("%d.: %c", permutation ,A[a]);
		} 
		printf("\n");
	}
	else{
		int i;
		for(i=0;i<n-1;++i){
			generate(n-1);
			if(n%2==0) swap(&A[i],&A[(n-1)]);
			else swap(&A[0],&A[(n-1)]);
		}
		generate(n-1);
	}
}

int main(int argc,char *argv[]){
	int n;
	if(argc<2 || (n=atoi(argv[1]))<0){
		printf("Usage: %s <number-of-elements>\n",argv[0]);
		return -1;
	}					
	generate(n);
	return 0;
}

    Aber jetzt bekomm ich zwar keine fehlermeldungen mehr, allerdings bekomm ich keine ausgabe außer neue zeilen.

    0
  • K

    So läuft es nun:

    #include<stdio.h>

char A[26]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};

void swap(char *x, char *y){
	int tmp=*x;

	*x=*y;
	*y=tmp;
}

void generate(int n){
	if (n==1){
		int b;
		for(b=0;A[b]!='\0';b++){
			printf("%c",A[b]);
		} 
		printf("\n");
	}
	else{
		int i;
		for(i=0;i<n-1;++i){
			generate(n-1);
			if(n%2==0) swap(&A[i],&A[n-1]);
			else swap(&A[0],&A[n-1]);
		}
		generate(n-1);
	}
}

int main(int argc,char *argv[]){
	int n;
	if(argc<2 || (n=atoi(argv[1]))<0){
		printf("Usage: %s <number-of-elements>\n",argv[0]);
		return -1;
	}
	int i;
	for(i=n; i<=26; ++i) A[i]='\0';
	generate(n);
	return 0;
}

    Ich hatte ein paar denkfehler bei zeile 14-20.

    0
  • B

    A ist zu klein für 27 Zeichen.

    0
Anmelden zum Antworten