Path: csiph.com!news.swapon.de!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Recursion, Yo
Date: Wed, 10 Apr 2024 10:14:01 -0700
Organization: A noiseless patient Spider
Lines: 142
Message-ID: <86cyqx16p2.fsf@linuxsc.com>
References: <uut24f$2icpb$1@dont-email.me> <uutqd2$bhl0$1@i2pn2.org> <uv2u2a$41j5$1@dont-email.me> <87edbestmg.fsf@bsb.me.uk> <uv4r9e$mdd3$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 10 Apr 2024 19:14:03 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5ec1c0fb8572bf9a2af34710c5b65b61"; logging-data="1153169"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/XoCz5xSZ97t+vu2y8Wnrpv2ghKU9Ge34="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:/rqkl0CRnmwiOCav2mj5haEqGBs= sha1:2X4d97gERzP2amSobOnYct3EgSo=
Xref: csiph.com comp.lang.c:384263

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