Groups > comp.lang.c > #62039

Re: permutation generator in C

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: permutation generator in C
Date	2015-05-15 11:32 +0100
Organization	A noiseless patient Spider
Message-ID	<87wq0aku5t.fsf@bsb.me.uk> (permalink)
References	<e7aaceef-80c0-429f-8b77-14dc2e514d07@googlegroups.com>

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
> But when authors write
> Swap(n%2? 0:c, n)

That line does not appear.  The algorithm has

  exch(N % 2 ? 1 : c, N);

but you are right that there is an error here.

> Than n is constant...
> It would swap only first and last
> element, always
> Than what is c?

c is an auxiliary array.

> Possibly in that page would be
> n= sizeof sub permutation
> c= c[j]
> Swap(n%2? 0:c, n)
>
> Than what is the meaning of "doit()"
> I think it is "return"

doit() is a place-holder for whatever you want to do with the
permutation.  The algorithm wouldn't work if you used return there.

> I think that algo is wrong

Yes, but it's just a typo.  The line should be

  exch(N % 2 ? 1 : n, N);

In previous algorithms the author used c as a counter, so this was a
cut-and-paste typo.

-- 
Ben.

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