Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Lawrence D'Oliveiro <ldo@nz.invalid>
Newsgroups: comp.lang.c
Subject: Re: Recursion, Yo
Date: Wed, 10 Apr 2024 01:50:38 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 141
Message-ID: <uv4r9e$mdd3$1@dont-email.me>
References: <uut24f$2icpb$1@dont-email.me> <uutqd2$bhl0$1@i2pn2.org>
	<uv2u2a$41j5$1@dont-email.me> <87edbestmg.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 10 Apr 2024 01:50:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7ce03bb5457ab82bf7e463e8fecedba8";
	logging-data="734627"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/OtVl/NF0OWkRX9OBkkXIR"
User-Agent: Pan/0.155 (Kherson; fc5a80b8)
Cancel-Lock: sha1:6U9Yvkpu1qOMQhYxKD0reuSyqyc=
Bytes: 4172

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