Gibt es eine Möglichkeit, über die Reihenfolge zu iterieren?

Question

Wie kann man die Reihenfolge der Ausführung durchlaufen?

Ich entwickle ein Stück Software, die mehrere Schritte haben, um über einige Daten zu berechnen, und ich dachte im Mai die Reihenfolge dieser Schritte pragmatisch ändern, damit ich überprüfen kann, was die beste Reihenfolge für einige Daten wäre.

Lassen Sie mich erläutern: Ich habe die 3 Schritte sagen lassen (es ist eigentlich mehr):

stepA(data); 
stepB(data); 
stepC(data); 

Und ich will einen Apparat, die mir erlauben jede Permutation dieser Schritte gedacht zu gehen und dann Ergebnisse überprüfen. Etwas wie das:

dann führen einigeMagic A, B dann C auf i == 0. A, C dann B auf i == 1. B, A dann C auf i == 2 und so weiter.

Answer 1

können Sie Funktionszeiger verwenden, vielleicht so etwas wie die folgenden:

typedef void (*func)(void *data); 

int someMagic(void *data, func *func_list, int i) { 
    switch (i) { 
    case 0: 
     func_list[0](data); 
     func_list[1](data); 
     func_list[2](data); 
     break; 
    case 1: 
     func_list[0](data); 
     func_list[2](data); 
     func_list[1](data); 
     break; 
    case 2: 
     func_list[1](data); 
     func_list[0](data); 
     func_list[2](data); 
     break; 
    default: return 0; 
    } 
    return 1; 
} 

func steps[3] = { 
    stepA, 
    stepB, 
    stepC 
} 

while (someMagic(&data, steps, i++)) { 
    .... 
} 

Answer 2

Der Schlüssel ist, einen Weg finden über den Satz von permutations des [0, n[ ganzzahligen Intervall zu wiederholen.

Eine Permutation (in der mathematischen Bedeutung) kann als eine Bijektion von [0, n[ in sich selbst gesehen werden und kann durch das Bild dieser Permutation dargestellt werden, angewendet auf [0, n[.

Betrachten wir zum Beispiel die Permutation von [0, 3[:

0 -> 1 
    1 -> 2 
    2 -> 0 

kann als das (1, 2, 0) Tupel zu sehen, die in C, permutation = (int []){1, 2, 0}; auf das Array von ganzen Zahlen natürlich übersetzen.

Angenommen, Sie ein Array von Funktionszeigern steps haben, dann für jede Permutation werden, Sie wollen dann steps[permutation[i]] nennen, für jeden Wert von i in [0, n[.

Der folgende Code implementiert diesen Algorithmus:

#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 

static void stepA(int data) { printf("%d: %s\n", data, __func__); } 
static void stepB(int data) { printf("%d: %s\n", data, __func__); } 
static void stepC(int data) { printf("%d: %s\n", data, __func__); } 
static void (* const steps[])(int) = {stepA, stepB, stepC,}; 
static int fact(int n) { return n == 0 ? 1 : fact(n - 1) * n; } 

static int compare_int(const void *pa, const void *pb) 
{ 
    return *(const int *)pa - *(const int *)pb; 
} 

static void get_next_permutation(int tab[], size_t n) 
{ 
    int tmp; 
    unsigned i; 
    unsigned j; 
    unsigned k; 

    /* to find the next permutation in the lexicographic order 
    * source: question 4 (in french, sorry ^^) of 
    * https://liris.cnrs.fr/~aparreau/Teaching/INF233/TP2-permutation.pdf 
. */ 
    /* 1. find the biggest index i for which tab[i] < tab[i+1] */ 
    for (k = 0; k < n - 1; k++) 
     if (tab[k] < tab[k + 1]) 
      i = k; 

    /* 2. Find the index j of the smallest element, bigger than tab[i], 
    * located after i */ 
    j = i + 1; 
    for (k = i + 1; k < n; k++) 
     if (tab[k] > tab[i] && tab[k] < tab[j]) 
      j = k; 

    /* 3. Swap the elements of index i and j */ 
    tmp = tab[i]; 
    tab[i] = tab[j]; 
    tab[j] = tmp; 

    /* 4. Sort the array in ascending order, after index i */ 
    qsort(tab + i + 1, n - (i + 1), sizeof(*tab), compare_int); 
} 

int main(void) 
{ 
    int n = sizeof(steps)/sizeof(*steps); 
    int j; 
    int i; 
    int permutation[n]; 
    int f = fact(n); 

    /* first permutation is identity */ 
    for (i = 0; i < n; i++) 
     permutation[i] = i; 

    for (j = 0; j < f; j++) { 
     for (i = 0; i < n; i++) 
      steps[permutation[i]](i); 
     if (j != f - 1) 
      get_next_permutation(permutation, n); 
    } 

    return EXIT_SUCCESS; 
} 

Die äußere Schleife in main durch j indexiert, iteriert über die alle n! Permutationen, während die innere, durch i indexiert, iteriert overs die n Schritte.

Die get_next_permutation ändert das permutation Array an Ort und Stelle, um die nächste Permutation in der lexikographischen Reihenfolge zu erhalten.

Beachten Sie, dass es nicht funktioniert, wenn die Permutation in Eingang ist der letzte (n - 1, ..., 1, 0), daher der if (j != f - 1) Test. Man könnte es verbessern, um diesen Fall zu erkennen (i ist nicht gesetzt) ​​und die erste Permutation (0, 1, ..., n - 1) in das permutation Array zu setzen.

Der Code kann mit kompiliert werden:

gcc main.c -o main -Wall -Wextra -Werror -O0 -g3 

Und ich empfehle valgrind als eine Möglichkeit, mit Off-by-one Fehler zu erkennen.

EDIT: Ich erkannte gerade, dass ich die Frage des OP nicht genau beantwortete. Die someMagic() Funktion würde einen direkten Zugriff auf die i-te Permutation ermöglichen, während mein Algorithmus nur die Berechnung des Nachfolgers in der lexikographischen Reihenfolge erlaubt. Aber wenn das Ziel darin besteht, alle Permutationen zu durchlaufen, wird es gut funktionieren. Andernfalls sollte eine Antwort wie this one die Anforderung erfüllen.

Answer 3

Ich habe zu einer Lösung kommen, die einfach genug ist:

void stepA(STRUCT_NAME *data); 
void stepB(STRUCT_NAME *data); 
void stepC(STRUCT_NAME *data); 

typedef void (*check)(STRUCT_NAME *data); 

void swap(check *x, check *y) {  
    check temp; 

    temp = *x; 
    *x = *y; 
    *y = temp;  
} 

void permute(check *a, int l, int r,STRUCT_NAME *data) {  
    int i, j = 0, score; 
    HAND_T *copy, *copy2, *best_order = NULL; 

    if (l == r) { 
     j = 0; 
     while (j <= r) a[j++](data); 
    } else { 
     for (i = l; i <= r; i++) { 
      swap((a + l), (a + i)); 
      permute(a, l + 1, r, data); 
      swap((a + l), (a + i)); 
     } 
    }  
} 

check checks[3] = { 
    stepA, 
    stepB, 
    stepC, 
}; 

int main(void){ 
    ... 
    permute(checks,0,2,data) 
}