Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #62064

Re: permutation generator in C

Show all headers | View raw

asetofsymbols@gmail.com writes:

> www.cs.princeton.edu/~rs/talks/perms.pdf
>
> I'm seeing this link...
> In the page where there is the *not* 
> recursive implementation of the
> permutation generator

Here's a version written in C, using (naturally) zero-based array
indexes.  It offers an example of a use-case for VLAs -- the arrays must
be small because large values of N and impractical.

#include <stdio.h>
#include <stdlib.h>

static inline void exchange(int *p, int i, int j)
{
     int t = p[i]; p[i] = p[j]; p[j] = t;
}

void generate_perms(int N, void (*use_it)(int, const int *, void *), void *dp)
{
     int p[N], c[N];
     for (int n = 0; n < N; n++) p[n] = n, c[n] = 0;
     
     use_it(N, p, dp);
     int n = 0;
     while (n < N) {
          if (c[n] < n) {
               exchange(p, n % 2 ? c[n] : 0, n);
               c[n] += 1;
               n = 1;
               use_it(N, p, dp);
          }
          else c[n++] = 0;
     }
}

void print_and_count(int n, const int *p, void *dp)
{
     for (int i = 0; i < n; i++)
          putchar(p[i] + 'A');
     putchar('\n');
     (*(int *)dp) += 1;
}

int main(int argc, char **argv)
{
     int counter = 0;
     generate_perms(argc > 1 ? atoi(argv[1]) : 5, print_and_count, &counter);
     fprintf(stderr, "%d\n", counter);
}

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

permutation generator in C asetofsymbols@gmail.com - 2015-05-15 02:19 -0700
  Re: permutation generator in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-15 11:32 +0100
    Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 04:44 -0700
      Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 04:49 -0700
      Re: permutation generator in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-15 16:21 +0100
        Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 11:44 -0700
      Re: permutation generator in C Keith Thompson <kst-u@mib.org> - 2015-05-15 08:26 -0700
  Re: permutation generator in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-15 19:51 +0100
    Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 13:38 -0700
      Re: permutation generator in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-15 21:48 +0100
        Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 14:05 -0700
          Re: permutation generator in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-15 22:32 +0100
          Re: permutation generator in C Keith Thompson <kst-u@mib.org> - 2015-05-15 14:43 -0700
            Re: permutation generator in C asetofsymbols@gmail.com - 2015-05-15 16:53 -0700
              Re: permutation generator in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2015-05-15 18:32 -0600
                Re: permutation generator in C Keith Thompson <kst-u@mib.org> - 2015-05-16 02:03 -0700

csiph-web