Re: Recursion, Yo

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:
>

It's significant (or at least note worthy) that the code in the
original post was not ISO C ...

>
Interesting that GCC?s C compiler allows nested routine definitions,
but the C++ compiler does not.
>

and re-writing it in ISO C would show up some of the issues involved
...

>
Ask and you shall receive ...
>
/*
    Generate permutations of a list of items.
    Pass a list of arbitary words as command arguments, and this
    program will print out all possible orderings of them.
*/
>
#include <iso646.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
>
typedef void (*permute_action)
  (
    unsigned int nrwords,
    const char * const * words,
    void * arg
  );
>
struct permute_ctx
  {
    unsigned int nrwords;
    const char * const * words;
    permute_action action;
    void * action_arg;
    const char ** permbuf;
    bool * used;
  } /*permute_ctx*/;
>
static void permute1
  (
    struct permute_ctx * ctx,
    unsigned int depth
  )
  {
    if (depth < ctx->nrwords)
      {
        for (unsigned int i = 0; i < ctx->nrwords; ++i)
          {
            if (not ctx->used[i])
              {
                ctx->permbuf[depth] = ctx->words[i];
                ctx->used[i] = true;
                permute1(ctx, depth + 1);
                ctx->used[i] = false;
              } /*if*/
          } /*for*/
      }
    else
      {
        ctx->action(ctx->nrwords, ctx->permbuf, ctx->action_arg);
      } /*if*/
  } /*permute1*/
>
void permute
  (
    unsigned int nrwords,
    const char * const * words,
    permute_action action,
    void * action_arg
  )
  {
    if (nrwords > 0)
      {
        struct permute_ctx ctx;
        ctx.nrwords = nrwords;
        ctx.words = words;
        ctx.action = action;
        ctx.action_arg = action_arg;
        ctx.permbuf = (const char **)malloc(nrwords * sizeof(char *));
        ctx.used = (bool *)malloc(nrwords);
        for (unsigned int i = 0; i < nrwords; ++i)
          {
            ctx.used[i] = false;
          } /*for*/
>
        permute1(&ctx, 0);
>
        free(ctx.permbuf);
        free(ctx.used);
      } /*if*/
  } /*permute*/
>
[...]

More complicated than it needs to be.  Besides that, in a beauty
contest this coding style would lose out even to Frankenstein.

Simpler:

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

typedef void    *Voidp;
typedef struct  array_CB_s ArrayCB;
struct array_CB_s {
  void (*run)( ArrayCB *cb, unsigned n, const Voidp[ n ] );
};

static  void  permute_r( unsigned n, Voidp[n], unsigned, ArrayCB * );
static  void  voidp_exchange( Voidp [], unsigned, unsigned );

void
permute( unsigned n, const Voidp in_array[n], ArrayCB *cb ){
    for(  Voidp *pva = malloc( n * sizeof *pva );  pva;  pva = 0  ){
        memcpy( pva, in_array, n * sizeof *pva );
        permute_r( n, pva, n, cb );
        free( pva );
    }
}

void
permute_r( unsigned n, Voidp values[n], unsigned k, ArrayCB *cb ){
    for(  unsigned i = 0;  i < k;  i++  ){
        voidp_exchange( values, n-k, n-k+i );
        permute_r( n, values, k-1, cb );
        voidp_exchange( values, n-k, n-k+i );
    }
    if(  k == 1  )  cb->run( cb, n, values );
}

void
voidp_exchange( Voidp values[], unsigned i, unsigned j ){
    if(  i != j  ){
        Voidp pi = values[i], pj = values[j];
        values[i] = pj, values[j] = pi;
    }
}