Ich bräuchte von euch mal eine Skizzierung des Algos und die zu verwendende Datenstruktur und die Parameter der (rekursiven) Methode:
Ich habe ein String[] mit 5 Elementen (variabel). Daraus sollen alle Permutationen mit 3 Elementen (variabel) ohne Wiederholung gebildet werden (und auf der Konsole ausgegeben werden).
Zuerst: a, b, c oder zuerst: c, d, e?
Mag mir jemand Helfen? Wenn ich jetzt angebe, ich würde einen € überweisen, wäre das sicher sinnlos.
erstmals im neuen Forum einen Thread nach Hausaufgaben verschoben…
du musst eigentlich schon selber programmieren, hier gibt es keine APIs oder Methoden zu verweisen,
elementarste Arrays, Schleifen, und wenn du je ‚3 Elemente‘ in einem Ergebnis-Objekt ablegen willst ist eine neue Klasse/ Datenstruktur dafür hoffentlich klar,
fange mit einfachen Schritten an, allein schon die 5 Elemente ausgeben, poste Code, jeder über ‚nix‘ ist schon besser,
danach Frage um Frage bzw. hoffentlich auch eigene Beiträge
allerdings gab es kürzlich ein mehr oder weniger ähnliches Thema
http://forum.byte-welt.net/threads/10894-Kombination-von-Array-Elementen
versuche erstmal nur 2 Elemente zu kombinieren,
zwei Schleifen ineinander ist der entscheidende Tipp, das sei ruhig verraten
edit: Rekursion statt Schleife ist natürlich wieder bisschen was anderes, aber auch nützlich die Schleifenvariante zu kennen/ können,
im Link von Aru nicht nur die erste Lösung anschauen 
Woran hängts denn?
So lange wie du im JFO unterwegs warst, müsstest du mindestens über 3-4 solcher Themen gestolpert sein,
da kann es doch nicht so schwer sein mit etwas Nachdenken (und bei Bedarf Googeln) einen Ansatz zu produzieren.
@Marco13 hatte für solche Probleme mal einen sehr schönen Codeschnipsel (Combinatorics), ich glaube der wurde hier allerdings noch nicht gepostet.
Gruß
Ja, das war im alten Forum dann schon ein Thread, wo gelegentlich neuere Versionen angehängt wurden, und irgendwann wurden die Posts so groß, dass sie nicht mehr in einen Beitrag (~20k Zeichen) gepasst haben, deswegen habe ich es dann mal zu einer JAR zusammengefasst, die ich irgendwo hochgeladen hatte. Tatsächlich steht auf meiner TODO-Liste recht weit oben, das ganze mal etwas “glattzuziehen” und auf GitHub zu klatschen. Hiermit ist das in meiner Queue nochmal ein Stück weiter hoch gewandert, aber … konkret zur Frage: Das war nicht mit einer rekursiven Methode gelöst. Im Gegenteil, das waren explizit alles Iterables/Iteratoren.
Das Prob dabei ist, dass ich das in einer anderen Programmiersprache schreiben müsste, welche nicht Java ist!:
C-Coder
[spoiler]```/*
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define trenner ‘_’
typedef struct Menge {
char * menge;
int n;
int k;
} Menge;
Menge *menge = NULL;
int calcN(char *m) {
int n;
if (m[0] == ‘\0’)
return 0;
if (m[0] == trenner)
return 0;
n = 1;
while(*m) {
if (m == trenner)
n++;
m++;
}
if (–m == trenner)
return 0;
return n;
}
void printA(int i,…) {
// ??? Zeile 36 ???
}
void printB(void) {
}
void printC(void) {
}
void printD(void) {
}
void printABkmn(int a, int b) {
int i = ((a-1)<<1)|(b-1);
printf("Mode: “, i);
while (i) {
if (i & 1)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
printf(”
");
if (a == 1)
if (b == 1)
printA();
else
printB();
else if (b == 1)
printC();
else
printD();
}
int main(void) {
int a, b, k = 1;
char *m = (char *) malloc(sizeof(char) * 1000);
menge = (Menge *) malloc(sizeof (Menge));
while (1) {
printf(“k-Permutation: 1
k-Kombination: 2
“);
scanf(”%i”, &a);
printf(“ohne Zuruecklegen: 1
mit Zuruecklegen : 2
“);
scanf(”%i”, &b);
if (a < 1 || a > 2 || b < 1 || b > 2) {
break;
}
printf(“Menge M getrennt durch %c:
“, trenner);
scanf(”%999s”, m);
printf(“k (Anzahl Ziehungen): “);
scanf(”%i”, &k);
if (k < 1 || k > 999 / 2 + 1) {
break;
}
menge->menge = m;
menge->n = calcN(m);
menge->k = k;
printf("a=%-5ib=%-5ik=%-5in=%-5iM=%s
", a, b, k, menge->n, m);
printABkmn(a, b);
}
return EXIT_SUCCESS;
}```[/spoiler]
Zeile 36 ist das Prob. Danke für’s drüber schauen oder für das in der Prioritätenliste nach oben schieben.
Zeile 36 sieht wirklich nach einem Problem aus: Da steht ein Kommentar mit Fragezeichen. Was soll denn in Zeile 36 passieren?
Auch wenn es jetzt um C geht, noch der Vollständigkeit halber: http://forum.byte-welt.net/threads/10920-Combinatorics?p=77243#post77243
Die Frage von Aru ist aber berechtigt, bzw. die eigentliche Frage des Threaderstellers IMHO nicht klar genug…
Danke Marco. Ich hab’s hin bekommen. Jetzt schaffe ich die anderen auch noch,:
Ausgabe
[spoiler]
k-Permutation: 1
k-Kombination: 2
1
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
1
Menge M getrennt durch _:
a_b_c_d_e
k (Anzahl Ziehungen): 3
a=1 b=1 k=3 n=5 M=a_b_c_d_e
Mode: 2686660:
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
k-Permutation: 1
k-Kombination: 2
o^C
[/spoiler]
Funktionen
[spoiler]```void printArray(int a[]) {
int i;
for (i = 0; i < menge->k; i++) {
printf("%2i", a**);
}
printf("
");
}
void printA(int idx, int val, int a[]) {
if (idx == menge->k) {
printArray(a);
return;
}
int idx2 = idx + 1; /* generell sollte man Deklarationen/Definitionen(/Initialisierungen) u. Code nicht mischen */
for (; val < menge->n;) {
a[idx] = val++;
printA(idx2, val, a);
}
}```[/spoiler]
Wie mache ich daraus jetzt eine Iterative version, damit daraus ein Hochgeschwindigkeitsprogramm wird und ich die volle Power von C ausnutzen kann? Zwei Arrays für Indexe und Values?
(Die Frage mit dem “Was kommt zuerst?” hat sich jetzt auch geklärt!)
Für irgendwelche Grenzfälle habe ich das aber bislang nicht getestet.
*** Edit ***
Edit: Hat sich erledigt, ist falsch, das wäre eine k-Kombination ohne Wiederholungen, denn bei einer Permutation muss auch 4 3 2 vorkommen.
“Hochgeschwindigkeitsprogramm” und “print” ist ein Widerspruch. Ein einzelnes printf dauert so lange, dass er in der gleichen Zeit hunderte oder tausende von Kombinationen berechnen könnte. BTW: Mir ist die Frage immernoch nicht klar. Obwohl ich zugeben muss, dass ich das für die Permutationen auch (“unverstanden”) auf Basis dessen geschrieben habe, was auf Wikipedia dazu steht :o
Ich kann die Aufgabenstellung im Moment nicht nennen… Aber es geht ja um’s Prinzip, möglichst wenige Funktionen/Prozeduren zu haben, die nicht schnell sind, also sollen langsame Funktionen möglichst isoliert werden. printf- dazu noch mit Formatierungsanweisungen- ist ein Graus… i know.
Aber wenn man sich die Ausgabe so ansieht, müsste doch nur für jede Zeile (jedes int []) doch nur noch mal die Rekursion aufgerufen werden, oder?
“menge” enthält Elemente mit Index. Eine 3-Permutation einer 5-elementigen Menge ist einfach eine Anordnung 3er Elementen aus M, wobei die Position innerhalb der Anordnung entscheidend/wichtig ist. Und es soll kein Element mehrfach vorkommen (außer die menge würde gleiche Elemente enthalten, was aber die Definition ausschließt).
Die Anzahl ist ein bisschen fri*ckelig: (n “über” k)*k! = n! / (n - k)! oder k+n-1 “über” k = “Doppelklammer” n “über” k, bei k nicht unterscheidbare Bälle, n unterscheidbare Fächer (s. bitte Abzählende Kombinatorik - Wikip.).
Gut’ Nacht
Komplettes Programm noch mal
[spoiler]```/*
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define TRENNER ‘_’
typedef struct Menge {
char * menge;
int n;
int k;
} Menge;
Menge *menge = NULL;
int calcN(char *m) {
int n;
if (m[0] == ‘\0’)
return 0;
if (m[0] == TRENNER)
return 0;
n = 1;
while(*m) {
if (m == TRENNER)
n++;
m++;
}
if (–m == TRENNER)
return 0;
return n;
}
void printArray(int arr[]) {
int i;
for (i = 0; i < menge->k; i++) {
printf("%2i", arr**);
}
printf("
");
}
void printA(int idx, int val, int arr[]) {
int idx2;
if (idx == menge->k) {
printArray(arr);
return;
}
idx2 = idx + 1; /* Deklarationen/Definitionen(/Initialisierungen) u. Code nicht mischen */
for (; val < menge->n;) {
arr[idx] = val++;
printA(idx2, val, arr);
}
}
void printB(void) {
}
void printC(void) {
}
void printD(void) {
}
void printABkmn(int a, int b) {
int i = ((a - 1) << 1) | (b - 1); /* 00-11 */
printf("Mode: %i: “, i);
while (i) {
if (i & 1)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
printf(”
");
if (a == 1)
if (b == 1)
printA(0, 0, (int *) malloc(sizeof(int) * menge->k));
else
printB();
else if (b == 1)
printC();
else
printD();
}
int main(void) {
int a, b, k = 1;
char *m = (char *) malloc(sizeof(char) * 1000);
menge = (Menge *) malloc(sizeof (Menge));
while (1) {
printf(“k-Permutation: 1
k-Kombination: 2
“);
scanf(”%i”, &a);
printf(“ohne Zuruecklegen: 1
mit Zuruecklegen : 2
“);
scanf(”%i”, &b);
if (a < 1 || a > 2 || b < 1 || b > 2) {
break;
}
printf(“Menge M getrennt durch %c:
“, TRENNER);
scanf(”%999s”, m);
printf(“k (Anzahl Ziehungen): “);
scanf(”%i”, &k);
if (k < 1 || k > 999 / 2 + 1) {
break;
}
menge->menge = m;
menge->n = calcN(m);
menge->k = k;
printf("a=%-5ib=%-5ik=%-5in=%-5iM=%s
", a, b, k, menge->n, m);
printABkmn(a, b);
}
return EXIT_SUCCESS;
}```[/spoiler]
Wenn ich jetzt b, c, d habe, wie mache ich daraus: b, d, c und c, b, d und c, d, b und d, b, c und d, c, b?
{a, b} bzw. (a, b) != {b, a} bzw. (b, a) bei Permutationen.
Ich hätte niemals gedacht, dass das so kompliziert werden würde.
Edit: Lesbarere “calcN”-Funktion:
[spoiler]int calcN(char *m) { int n; if (*m == '\0') return 0; if (*m++ == TRENNER) return 0; n = 1; while(*m) { if (*m == TRENNER) n++; m++; } if (*--m == TRENNER) return 0; return n; }[/spoiler]
Zwei _=TRENNER hintereinander ist legal (außer zu Beginn und zu Schluss).
Was ist das denn für ein mess? printA, printB, printXYZ, Berechnung und Ausgabe gemischt, auf char-Arrays mit irgendwelchen TRENNER-Zeichen, und was “Menge” genau sein soll, ist auch nicht klar…
WAS soll berechnet werden? Ich gehe davon aus, dass es eine Funktion geben soll, die etwa (!) eine Signatur hat wie
char** computeAllPermutations(char *input, int inputLength) { ... }
Stimmt das so weit?
Ja, bis auf, dass kein char ** zurückgegeben werden braucht, sondern jede Zeile sofort ausgegeben oder in eine Datei geschrieben werden kann.
OK. Meine “aktive” C-Zeit ist eine Weile her, deswegen bin ich mir nicht 100% sicher darüber, wie man diese Anforderung am geeignetsten umsetzt (AFAIK ist es nicht so leicht, das “gut” zu machen). Muss es nur C sein, oder tut’s auch C++? Wenn’s C sein muss: Dürfen da function pointers drin vorkommen?
Wenn die Frage, ob auf die Konsole oder in eine Datei geschrieben wird, zur Compilezeit beantwortet werden kann (d.h. indem man einfach eine andere Funktion aufruft), dann ist das nicht so ein großes Problem. Dann kann man ja einfach erstmal ein vorgefertigtes Codestück zum Generieren von Permutationen verwenden (siehe z.B. diese alte Version der Wiki-Seite: http://en.wikipedia.org/w/index.php?title=Permutation&oldid=299065358 ), und Ende läuft es dann darauf raus, dass während dieser Generierung eine Funktion doSomethingWith(char *currentPermutation, int length) aufgerufen wird, die entweder in eine Datei schreibt, oder auf einer Konsole ausgibt. Aber unabhängig davon würde ich das mit dem “Trenner” zu vermeiden versuchen…
c ist gut. Aber das sieht nach einem Set/einer HashMap aus, oder? Das wäre nicht verfügbar. C++ darf es auch nicht sein.
Durch ein Feld iterieren und auf Vorkommnis testen?
Da kommt kein Set und keine HashMap drin vor.
So geht’s:
Ausgabe
[spoiler]
k-Permutation: 1
k-Kombination: 2
1
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
1
Menge M getrennt durch _:
a_b_c_d
k (Anzahl Ziehungen): 3
a=1 b=1 k=3 n=4 M=a_b_c_d
Mode: 0:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
0 1 3
0 3 1
1 0 3
1 3 0
3 0 1
3 1 0
0 2 3
0 3 2
2 0 3
2 3 0
3 0 2
3 2 0
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
k-Permutation: 1
k-Kombination: 2
o^C
[/spoiler]
Code(teil)
[spoiler]```#define TRENNER ‘_’
typedef struct Menge {
char * menge;
int n;
int k;
} Menge;
Menge *menge = NULL;
int calcN(char m[]) {
int n;
if (*m == ‘\0’)
return 0;
if (*m++ == TRENNER)
return 0;
n = 1;
while(*m) {
if (m == TRENNER)
n++;
m++;
}
if (–m == TRENNER)
return 0;
return n;
}
void printArray(int arr[]) {
int i;
for (i = 0; i < menge->k; i++) {
printf("%2i", arr**);
}
printf("
");
}
void printA1(int idx, int arr[], int arr2[], int arr3[]) {
int i, idx2;
if (idx == menge->k) {
printArray(arr2);
return;
}
idx2 = idx + 1;
for (i = 0; i < menge->k; i++)
if (arr3**) {
arr3** = 0;
arr2[idx] = arr**;
printA1(idx2, arr, arr2, arr3);
arr3** = 1;
}
}
int *iniArr3(void) {
int *arr3 = (int *) malloc(sizeof(int) * menge->k);
int *iptr = arr3;
int i = 0;
while (i++ < menge->k)
*arr3++ = 1;
return iptr;
}
void printA(int idx, int val, int arr[]) {
int idx2;
if (idx == menge->k) {
printA1(0, arr, (int ) malloc(sizeof(int) * menge->k), iniArr3());
return;
}
idx2 = idx + 1; / Deklarationen/Definitionen(/Initialisierungen) u. Code nicht mischen */
for (; val < menge->n;) {
arr[idx] = val++;
printA(idx2, val, arr);
}
}```[/spoiler]
Sieht nur irgendwie etwas steinig aus.
arr[] enthält z. B. b,c,d
arr2[] soll als nächstes b,d,c usw. enthalten
arr3**: Ist Element arr** noch nicht in arr2[] enthalten? (arr3[] enthält 1 oder 0)
Marco, jetzt bist du dran und sagst, was man besser machen sollte.^^
Zugegebenermaßen etwas irritiert mußte ich eben feststellen, dass ich auf diesem Rechner hier nichtmal einen C-Compiler habe. Aber auf dem anderen. Morgen abend schau’ ich da nochmal. Mal schauen, ob in meinem Code dann auch ein ‚free‘ vorkommen wird 
Jawoll, darauf aufbauend hat es jetzt geklappt:
c-Datei
[spoiler]```/*
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define TRENNER ‘_’
typedef struct Menge {
char *menge;
int n;
int k;
} Menge;
Menge *menge = NULL;
int calcN(char m[]) {
int n;
if(*m == ‘\0’)
return 0;
if(*m++ == TRENNER)
return 0;
n = 1;
while(*m) {
if(m == TRENNER)
n++;
m++;
}
if(–m == TRENNER)
return 0;
return n;
}
void printArray(int arr[]) {
int i;
for(i = 0; i < menge->k; i++) {
printf("%2i", arr**);
}
printf("
");
}
void printA1(int idx, int arr[], int arr2[], int arr3[]) {
int i, idx2;
if(idx == menge->k) {
printArray(arr2);
return;
}
idx2 = idx + 1;
for(i = 0; i < menge->k; i++)
if(arr3**) {
arr3** = 0;
arr2[idx] = arr**;
printA1(idx2, arr, arr2, arr3);
arr3** = 1;
}
}
int *iniArr3(void) {
int *arr3 = (int *) malloc(sizeof(int) * menge->k);
int i = 0;
while(i++ < menge->k)
*arr3++ = 1;
return arr3 - i;
}
void printA(int idx, int val, int arr[]) {
int idx2;
if(idx == menge->k) {
printA1(0, arr, (int ) malloc(sizeof(int) * menge->k), iniArr3());
return;
}
idx2 = idx + 1; / Deklarationen/Definitionen(/Initialisierungen) u. Code nicht mischen */
for(; val < menge->n;) {
arr[idx] = val++;
printA(idx2, val, arr);
}
}
void printB(int idx, int arr[]) {
int idx2, val;
if(idx == menge->k) {
printArray(arr);
return;
}
idx2 = idx + 1;
for(val = 0; val < menge->n; val++) {
arr[idx] = val;
printB(idx2, arr);
}
}
void printC(int idx, int val, int arr[]) {
int idx2;
if(idx == menge->k) {
printArray(arr);
return;
}
idx2 = idx + 1;
for(; val < menge->n;) {
arr[idx] = val++;
printC(idx2, val, arr);
}
}
void printD(int idx, int val, int arr[]) {
int idx2;
if(idx == menge->k) {
printArray(arr);
return;
}
idx2 = idx + 1;
for(; val < menge->n; val++) {
arr[idx] = val;
printD(idx2, val, arr);
}
}
void printAB(int a, int b) {
int i = ((a - 1) << 1) | (b - 1); /* 00-11 */
printf("Mode: %i: “, i);
while(i) {
if(i & 1)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
printf(”
");
if(a == 1)
if(b == 1)
printA(0, 0, (int *) malloc(sizeof(int) * menge->k));
else
printB(0, (int *) malloc(sizeof(int) * menge->k));
else if(b == 1)
printC(0, 0, (int *) malloc(sizeof(int) * menge->k));
else
printD(0, 0, (int *) malloc(sizeof(int) * menge->k));
}
int main(void) {
int a, b, k = 1;
char *m = (char *) malloc(sizeof(char) * 1000);
menge = (Menge *) malloc(sizeof(Menge));
while(1) {
printf(“k-Permutation: 1
k-Kombination: 2
“);
scanf(”%i”, &a);
printf(“ohne Zuruecklegen: 1
mit Zuruecklegen : 2
“);
scanf(”%i”, &b);
if(a < 1 || a > 2 || b < 1 || b > 2) {
break;
}
printf(“Menge M getrennt durch %c:
“, TRENNER);
scanf(”%999s”, m);
printf(“k (Anzahl Ziehungen): “);
scanf(”%i”, &k);
if(k < 1 || k > 999 / 2 + 1) {
break;
}
menge->menge = m;
menge->n = calcN(m);
menge->k = k;
printf("a=%-5ib=%-5ik=%-5in=%-5iM=%s
", a, b, k, menge->n, m);
printAB(a, b);
}
return EXIT_SUCCESS;
}```[/spoiler]
Ausgabe
[spoiler]
C:\Users\MeinNam\Desktop>Mengen.exe
k-Permutation: 1
k-Kombination: 2
1
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
1
Menge M getrennt durch _:
a_b_c
k (Anzahl Ziehungen): 2
a=1 b=1 k=2 n=3 M=a_b_c
Mode: 0:
0 1
1 0
0 2
2 0
1 2
2 1
k-Permutation: 1
k-Kombination: 2
1
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
2
Menge M getrennt durch _:
a_b_c
k (Anzahl Ziehungen): 2
a=1 b=2 k=2 n=3 M=a_b_c
Mode: 1: 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
k-Permutation: 1
k-Kombination: 2
2
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
1
Menge M getrennt durch _:
a_b_c
k (Anzahl Ziehungen): 2
a=2 b=1 k=2 n=3 M=a_b_c
Mode: 2: 01
0 1
0 2
1 2
k-Permutation: 1
k-Kombination: 2
2
ohne Zuruecklegen: 1
mit Zuruecklegen : 2
2
Menge M getrennt durch _:
a_b_c
k (Anzahl Ziehungen): 2
a=2 b=2 k=2 n=3 M=a_b_c
Mode: 3: 11
0 0
0 1
0 2
1 1
1 2
2 2
k-Permutation: 1
k-Kombination: 2
oh^C
C:\Users\MeinNam\Desktop>
[/spoiler]
printA erhöht val immer um 1 und beginnt ab da, außerdem wird wegen Permutation printA1 aufgerufen
printB beginnt immer ab val=0
printC erhöht val auch immer um 1, ruft aber nicht printA1 auf
printD beginnt immer ab val, aber erhöht val erst nach dem rekursiven Aufruf
Beachte: Anzahl kaPermutation ohne Zuruecklegen ist nicht immer gleich Anzahl kaKombination mit Zuruecklegen
Wäre in diesen Fällen Rekursionen oder Iterationen besser? In deiner aktiven c-Zeit von dir, wie hättest du die Funktionen angeordnet/sortiert und welche Bezeichnungen den Funktionen gegeben?