有沒有辦法迭代訂單？

Question

如何迭代執行順序？

我正在開發一個軟件，它有幾個步驟來計算一些數據，我在想可能會改變這些步驟的順序，所以我可以檢查一下數據的最佳順序。

讓我舉例說明：我讓我們說3個步驟（它實際上更多）：

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

而且我希望有一個玩意兒，讓我走想過這些步驟每一個排列，然後檢查結果。類似的東西：

data = originalData; i=0; 
while (someMagic(&data,[stepA,stepB,stepC],i++)){ 
    checkResults(data); 
    data = originalData; 
} 

然後someMagic執行A，B然後C在i == 0。 A，C然後B在i == 1。 B，A然後C在i == 2等等。

Answer 1

您可以使用函數指針，可能像下面：

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

，關鍵是要找到一種方法來遍歷集合的[0, n[整數區間permutations。

置換（在數學上的含義）可以看作是[0, n[本身的雙射，可以用這個置換的圖像表示，應用於[0, n[。

例如，考慮的[0, 3[置換：

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

它可以被看作是該元組(1, 2, 0)，其在C，自然轉化爲整數permutation = (int []){1, 2, 0};的陣列。

假設你有函數指針steps的數組，然後爲每個排列，你會再想要調用steps[permutation[i]]，在[0, n[的i每個值。

下面的代碼實現該算法：

#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; 
} 

外環在main，通過j索引，遍歷所有n!置換，而內部之一，通過i索引，迭代接管的n步驟。

get_next_permutation修改了permutation數組，以便按字典順序獲得下一個排列。

注意，它不起作用當輸入置換是最後一個(n - 1, ..., 1, 0)，因此if (j != f - 1)測試。 人們可以加強它來檢測這種情況下（我沒有設置），並把第一個排列(0, 1, ..., n - 1)到permutation陣列。

的代碼可以編譯：

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

，我強烈建議使用valgrind，以此來檢測的off-by-一個錯誤。

編輯：我剛剛意識到我沒有準確回答OP的問題。 someMagic()函數將允許直接訪問第i個排列，而我的算法只允許按字典順序計算後繼。但是如果目標是迭代所有的排列，它將工作得很好。否則，可能像this one這樣的答案應該符合要求。

Answer 3

我來的解決方案很簡單：

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