Re: Recursion, Yo

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*/

struct main_ctx
  {
    FILE * out;
    unsigned int count;
  } /*main_ctx*/;

void collect
  (
    unsigned int nrwords,
    const char * const * words,
    struct main_ctx * ctx
  )
  {
    ctx->count += 1;
    fprintf(ctx->out, "[%d](", ctx->count);
    for (unsigned int i = 0; i < nrwords; ++i)
      {
        if (i != 0)
          {
            fputs(", ", ctx->out);
          } /*if*/
        fputs(words[i], ctx->out);
      } /*for*/
    fputs(")\n", ctx->out);
  } /*collect*/

int main
  (
    int argc,
    char ** argv
  )
  {
    struct main_ctx ctx;
    ctx.out = stdout;
    ctx.count = 0;

    permute
      (
        /*nrwords =*/ argc - 1,
        /*words =*/ (const char * const * )(argv + 1),
        /*permute_action =*/ (permute_action)collect,
        /*action_arg =*/ (void *)&ctx
      );

    fprintf(stdout, "Nr found: %d\n", ctx.count);
  } /*main*/