Rekursive Kombinationen



  • Folgendes Problem: Es gibt 'n' Teilmengen mit unterschiedlicher Größe bzw. Länge.
    Aus jeder Teilmenge soll genau ein Element ausgewählt werden. Gesucht werden alle
    möglichen Kombinationen. Für die Teilmengen {1, 2, 3} und {2, 5} ist das Ergebnis
    z. B. 12, 15, 22, 25, 32, 35. Wer kennt den Link zu einer Lösung möglichst für
    ein rekursives C-Programm oder kann das Programm hier einstellen?



  • @Jochen-W Wie wäre es, wenn du es selbst mal versuchst?

    Ansonsten bist du für C im falschen Unterforum 😉



  • @Jochen-W sagte in Rekursive Kombinationen:

    Für die Teilmengen {1, 2, 3} und {2, 5} ist das Ergebnis
    z. B. 12, 15, 22, 25, 32, 35.

    Und warum kommt da 12 raus, wenn ich eine 1 und eine 2 wähle? Sind die Teilmengen in einer bestimmten Ordnung vorgegeben, sodass man die letzte mit 1, die vorletzte mit 10 usw. multiplizieren muss? Und was soll passieren, wenn in einer Teilmenge eine Zahl größergleich 10 ist?


  • Mod

    Das ist (hoffentlich) doch nicht numerisch gemeint. Ich würde das sowieso mit Zeichenketten machen, weil man dann schick immer bis zu einem Nullterminator laufen kann, ohne dass man mehr Code für das Setup braucht als für die eigentliche Aufgabe.

    PS: Aus der langen Reihe "Studenten sind jetzt dümmer als KI", habe ich den Eingangsbeitrag 1:1 in ChatGPT kopiert:

    #include <stdio.h>
    #include <stdlib.h>
    
    void combinations(int **sets, int *sizes, int *indices, int n, int depth, int *output, int *count) {
        if (depth == n) {
            // base case: we have selected one element from each set
            // print the combination
            for (int i = 0; i < n; i++) {
                printf("%d", sets[i][indices[i]]);
            }
            printf("\n");
            // add the combination to the output array
            for (int i = 0; i < n; i++) {
                output[*count * n + i] = sets[i][indices[i]];
            }
            (*count)++;
            return;
        }
        // recursive case: select one element from the current set and move on to the next set
        for (int i = 0; i < sizes[depth]; i++) {
            indices[depth] = i;
            combinations(sets, sizes, indices, n, depth + 1, output, count);
        }
    }
    
    int main() {
        int n = 2;
        int *sizes = malloc(n * sizeof(int));
        sizes[0] = 3;
        sizes[1] = 2;
        int **sets = malloc(n * sizeof(int *));
        sets[0] = malloc(3 * sizeof(int));
        sets[0][0] = 1;
        sets[0][1] = 2;
        sets[0][2] = 3;
        sets[1] = malloc(2 * sizeof(int));
        sets[1][0] = 2;
        sets[1][1] = 5;
        int *indices = calloc(n, sizeof(int));
        int count = 0;
        int *output = malloc(n * sizes[0] * sizes[1] * sizeof(int));
        combinations(sets, sizes, indices, n, 0, output, &count);
        printf("Total combinations: %d\n", count);
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d", output[i * n + j]);
            }
            printf("\n");
        }
        free(sizes);
        free(sets[0]);
        free(sets[1]);
        free(sets);
        free(indices);
        free(output);
        return 0;
    }
    

    Meiner Meinung nach ein bisschen overengineered, das hätte man mit zielgerichteterer Programmierung auch in weniger als halb so vielen Zeilen machen können. Aber natürlich auch sehr gut, dass man hier eine so universelle Lösung hat, anstatt nur das ganz spezielle Problem zu lösen. Man sieht auch fein, wie das Setup hier tatsächlich die Hälfte vom Code ausmacht, und das obwohl das nur ein ganz simples Beispiel ist.



  • @SeppJ Das Programm funktioniert zwar nicht, aber das Unterprogramm dient mir als Grundlage, an dem ich mich weiterhangeln kann. Vielen Dank!



  • Doch, es funktioniert: Ideone-Code (außer, daß es doppelt die Werte ausgibt - und das ist ja einfach zu beheben [eine Berechnungsfunktion sollte ja, außer zu Debugzwecken, keine Ausgaben tätigen])