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



  • 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


  • 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 😕



  • 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.



  • 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.



  • A ist zu klein für 27 Zeichen.


Log in to reply