C-Code-Permutation
Hier ist ein Permutationscode, der jedoch nicht alle möglichen Permutationen druckt. Nur gedruckt ist die Eingabe. Was ist los mit diesem Code?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int bitmask;
char* characters;
int characters_count;
char* running;
int running_count;
void permutations() {
int i;
if (running_count == characters_count) {
printf("%s\n", running);
} else {
for (i=0; i<characters_count; i++) {
if ( ((bitmask>>i)&1) == 0 ) {
running[running_count] = characters[i];
bitmask |= (1<<i);
running_count = running_count + 1;
permutations();
running_count = running_count - 1;
}
}
}
}
main() {
int i;
int cases;
characters = (char*)malloc(sizeof(char)*30);
scanf("%s", characters);
characters_count = strlen(characters);
running = (char*)malloc(sizeof(char)*30);
memset(running, 0, 30);
running_count = 0;
permutations();
free(characters);
free(running);
}
Probeneingabe
ab
Beispielausgabe
ab
Anstatt von
ab
ba
Mein Freund hält hier nur eine Zeile für einen Fehler. Aber ich kann nicht herausfinden, welche Zeile die falsche ist oder welche mir fehlt
Sie können Ihren Code folgendermaßen korrigieren:
bitmask |= (1<<i);
running_count = running_count + 1;
permutations();
running_count = running_count - 1;
bitmask &= ~(1<<i);
Es wäre jedoch viel besser, sich nicht auf globale Variablen zu verlassen.
Aufgrund mainder festen Puffergröße ist auch keine Speicherzuweisung erforderlich .
Hier ist eine Version ohne Speicherzuordnung, keine globalen Variablen:
#include <stdio.h>
#include <string.h>
void permutations(int bitmask,
const char *characters, int characters_count,
char *running, int running_count) {
if (running_count == characters_count) {
printf("%.*s\n", running_count, running);
} else {
for (int i = 0; i < characters_count; i++) {
if (((bitmask >> i) & 1) == 0) {
running[running_count] = characters[i];
permutations(bitmask | (1 << i),
characters, characters_count,
running, running_count + 1);
}
}
}
}
int main(void) {
char characters[30];
char running[30];
if (scanf("%29s", characters) == 1) {
permutations(0, characters, strlen(characters), running, 0);
}
return 0;
}
Beachten Sie auch, dass der %.*s printfKonvertierungsspezifizierer nur die ersten running_countZeichen druckt runningund der %29s scanfSpezifizierer, um einen Pufferüberlauf zu verhindern.