alle 4er Kombinationen *grrrr*



  • Ich kaempf mit einen Algorithmus, der mir Kombinationen aus 4er Gruppen zusammenstellen muss.
    Genau gesagt ist die Eingabe eine durch 4 Teilbare Zahl >= 8. Dann muss ich alle
    Kombinationen berechnen, wobei gilt, dass {1, 2, 3, 4} gleich {1, 3, 4, 2} ist, und deshalb der Fall nicht doppelt betrachtet werden soll. Also folgende Kombinationen sind gleich:
    {1, 2, 3, 4} mit {5, 6, 7, 8}
    und
    {1, 3, 4, 2} mit {5, 6, 7, 8}
    mein bisheriges Bemuehen ergab bis noch nicht viel:

    #include <stdio.h>
    #include <stdlib.h>
    
    void print(int a[], int n) {
    	int i;
    
    	for (i = 0; i < n; i++)
    		printf("%d ", a[i]);
    	printf("\n");
    }
    
    void swap(int i, int j, int a[], int l) {
    	int iter;
    
    	int *tmp = (int*)malloc(sizeof(int)*l);
    	if (tmp == 0)
    		exit(-1);
    
    	for (iter = 0; iter < l; iter++) {
    		tmp[iter] = a[i+iter];
    		a[i+iter] = a[j-iter];
    		a[j-iter] = tmp[iter];
    	}
    
    	free(tmp);
    }
    
    void comb(int n) {
    	int *a;
    	int i, j, l, tmp = 0;
    
    	a = malloc(sizeof(int)*n);
    
    	for (i = 0; i < n; i++)
    		a[i] = (i+1);
    
    	for (l = 1; l < 4; l++) { 
    		for (j = 0; j < 4; j++) {
    			for (i = 0; i < 4; i++) {
    
    				swap(i+4, j, a, 1);
    				print(a, n);
    				swap(i+4, j, a, 1);
    			}
    		}
    	}
    
    	free(a);
    }
    
    int main(int argc, char *argv[]) {
    	comb(8);
    
    	return 0;
    }
    

    Das Beispiel arbeitet mit einer fix Kodierten Zahl von 8 (ergibt also 2 Vierergruppen). Aber wie gesagt, der Erfolg bleibt aus ...

    Hat vielleicht jemand ne Idee, wo mein Denkfehler liegt?



  • ich geb mir echt mühe, aber deine beschreibung kapier ich nicht!



  • nullcheckung schrieb:

    ich geb mir echt mühe, aber deine beschreibung kapier ich nicht!

    Sorry, probier's nochmal:

    Ein brauche einen Algorithmus, der von einer gegebenen Menge an Elementen (zur einfachheit halber sagen wir es sind halt Zahlen) alle Kombinationen aus jeweils 4 Elementen erstellt.
    Die Menge an Elementen ist durch 4 teilbar und die entstehenden Submengen bestehen eben aus 4 Elementen.

    Ein etwas naiver Ansatz in diesem Zusammenhang waere einfach alle Permutationen aus dieser Menge zu erstellen. Dabei kann es aber vorkommen, dass bestimmte Kombinationen oeffter auftreten.
    z.B. Kommen die Zahlen 1, 2, 3, 4 (also ein 4er Block) in unterschiedlicher Reihenfolge halt oefter im selben Block vor, daher gilt folgendes:
    {1, 2, 3, 4} = {2, 3, 4, 1} = {3, 4, 1, 2} usw.

    Da gibt es doch sicher was besseres hab ich mir gedacht, aber selbst bin ich noch auf nichts besseres drauf gekommen und google hat auch nichts ausgespuckt bzw. vielleicht suche ich halt mit den falschen Begriffen.

    ----
    ich hoff das war jetzt etwas verstaendlicher ...



  • probier mal dies:

    #include <stdio.h>
    
    #define LENGTH 8
    int S[LENGTH] = {0};
    
    void print (void)
    {
        int j, count = 0;
    
        for(j=0; j<LENGTH; j++)
            if(S[j] == 1)
                count++;
    
        if (count != 4)
            return;
    
        for(j = 0; j < LENGTH; j++)
           if(S[j] == 1)
               printf ("%d", j+1);
        puts ("");
    }
    
    void make_subset (int n)
    {
        if(n == 0)
            print();
        else
        {
            S[n-1] = 1;
            make_subset (n-1);
            S[n-1] = 0;
            make_subset (n-1);
        }
    }
    
    void main()
    {
        make_subset (LENGTH);
    }
    

    🙂



  • Wow,

    super, danke.
    Ist zwar nicht genau was ich brauche, aber damit laesst sich super arbeiten.

    Danke!!!



  • moe szyslak schrieb:

    Ist zwar nicht genau was ich brauche...

    alle teilmengen mit 4 elementen aus 8, so wie ich dich verstanden habe. stimmt das denn nicht?
    🙂



  • for(j=0; j < len; j++)
             if(groups[j] == 1)
                 count++; 
    
         if (count != 4)
             return;
    
         for(j = 0; j < len; j++)
             if(groups[j] == 1)
                 printf ("%d ", j+1);
         printf("\t");
    
         for(j = 0; j < len; j++)
             if(groups[j] == 0)
                 printf ("%d ", j+1);
         printf("\n");
    

    Nicht viel, es sollen nur die uebrigen auch ausgegeben werden (siehe oben). Aber wie gesagt, das ist nicht schwierig und funktioniert super.
    Danke nochmal!!!



  • ^^damit gibst du die liste einmal vorwärts und einmal rückwärts aus. aber gut, wenn's so sein soll...
    🙂


Log in to reply