Rekursive Kombinationen

Jochen W.

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?

Schlangenmensch

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

Ansonsten bist du für C im falschen Unterforum

wob

@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?

SeppJ

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.

Jochen W.

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

Th69

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])