Is there a way to iterate over order?

Question

How can one iterate through order of execution?

I am developing a piece of software that have several steps to compute over some data, and i was thinking in may changing the order of those steps pragmatically so i can check what would be the best order for some data.

Let me exemplify: I have let's say 3 steps (it's actually more):

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

And I want a contraption that allow me to walk thought every permutation of those steps and then check results. Something like that:

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

then someMagic execute A,B then C on i==0. A, C then B on i==1. B, A then C on i==2 and so on.

Answer 1

You can use function pointers, maybe something like the following:

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

The key is to find a way to iterate over the set of permutations of the [0, n[ integer interval.

A permutation (in the mathematical meaning) can be seen as a bijection of [0, n[ into itself and can be represented by the image of this permutation, applied to [0, n[.

for example, consider the permutation of [0, 3[:

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

it can be seen as the tuple (1, 2, 0), which in C, translate naturally to the array of integers permutation = (int []){1, 2, 0};.

Suppose you have an array of function pointers steps, then for each permutation, you'll then want to call steps[permutation[i]], for each value of i in [0, n[.

The following code implements this algorithm:

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

The outer loop in main, indexed by j, iterates over all the n! permutations, while the inner one, indexed by i, iterates overs the n steps.

The get_next_permutation modifies the permutation array in place, to obtain the next permutation in the lexicographical order.

Note that it doesn't work when the permutation in input is the last one (n - 1, ..., 1, 0), hence the if (j != f - 1) test. One could enhance it to detect this case (i isn't set) and to put the first permutation (0, 1, ..., n - 1) into the permutation array.

The code can be compiled with:

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

And I strongly suggest using valgrind as a way to detect off-by-one errors.

EDIT: I just realized I didn't answer the OP's question precisely. The someMagic() function would allow a direct access to the i-th permutation, while my algorithm only allows to compute the successor in the lexicographic order. But if the aim is to iterate on all the permutations, it will work fine. Otherwise, maybe an answer like this one should match the requirement.

Answer 3

I've come to a solution that is simple enough:

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