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

Groups > comp.lang.c > #62038 > unrolled thread

permutation generator in C

Back to article view | Back to comp.lang.c

Contents

  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

#62038 — permutation generator in C

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)
Than n is constant...
It would swap only first and last
element, always
Than what is c? 
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"

I think that algo is wrong 

[toc] | [next] | [standalone]

#62039

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.

[toc] | [prev] | [next] | [standalone]

#62040

Ben wrote:"
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."

Ok it is as above
but N is fixed (it would be the number
of element to permute {1..N})
And there is not a place in the code
of the not recursive routine that
change N.
If N%2==0
Than the algo can swap only
1 and last N in ordered {1..N}

So it can not be right

[toc] | [prev] | [next] | [standalone]

#62041

Ben wrote:" 
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." 


Ok it is as above 
but N is fixed (it would be the number 
of element to permute {1..N}) 
And there is not a place in the code 
of the not recursive routine that 
change N. 
If N%2==1
Than the algo can swap only 
1 and last N in ordered {1..N} 

So it can not be right

[toc] | [prev] | [next] | [standalone]

#62044

asetofsymbols@gmail.com writes:

> Ben wrote:"
> 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."
>
> Ok it is as above
> but N is fixed (it would be the number
> of element to permute {1..N})
> And there is not a place in the code
> of the not recursive routine that
> change N.
> If N%2==0
> Than the algo can swap only
> 1 and last N in ordered {1..N}
>
> So it can not be right

Yes, I was way too hasty in suggesting the correction.  The iterative
version uses an array of c values (that's why c went from an int to an
array) and the recursive parameter N is replaced with an iterated n.
Thus the original

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

should be

  exch(n % 2 ? 1 : c[n], n);

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#62062

Ben wrote:"
Thus the original 

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

should be 

  exch(n % 2 ? 1 : c[n], n);"

Yes you are right...
My little problem was the set on build
permutations was {0,..,N-1} and
not {1,..,N}
Something as:
exch((n+1) % 2 ? 0 : c[n], n);

Thank you

[toc] | [prev] | [next] | [standalone]

#62045

asetofsymbols@gmail.com writes:
> Ben wrote:"
> 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."
>
> Ok it is as above
[...]

Is there some reason that you're unable or unwilling to quote
properly?

By quoting previous articles using quotation marks rather than
the conventional "> " at the beginning of each line, you make
your articles unnecessarily difficult to read.  The only division
between Ben's quoted text and your new text is a single double-quote
character at the end of a line -- which could easily appear in the
text itself.

You seem to be posting via Google Groups which, for all its flaws,
automatically uses proper "> " quotation indicators.  Are you
deliberately removing them?  Why?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#62064

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.

[toc] | [prev] | [next] | [standalone]

#62066

Ben wrote:
<           c[n] += 1; 
<           n = 1;

Instead here result something as
++c[n]; n=0;

[toc] | [prev] | [next] | [standalone]

#62068

asetofsymbols@gmail.com writes:

> Ben wrote:
> <           c[n] += 1; 
> <           n = 1;
>
> Instead here result something as
> ++c[n]

Why?

> n=0;

The n = 0 vs. n = 1 is interesting.  I deliberately wrote 1 and not 0
despite having moved to zero-based arrays and I think it's correct
(though 0 works too).  Have you found an error case?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#62070

Ben wrote:
<Have you found an error case?

No. as in the algo authors use 1
for permutation on {1..N}

I would use 0 for permutations
on {0..N-1}

The algo is not so clear, it
seems here ok case {0,1} {0,1,2} 

[toc] | [prev] | [next] | [standalone]

#62075

asetofsymbols@gmail.com writes:

> Ben wrote:
> <Have you found an error case?
>
> No. as in the algo authors use 1
> for permutation on {1..N}

You can use 2 in this case...

> I would use 0 for permutations
> on {0..N-1}

which is why 1 works for zero-based arrays.

> The algo is not so clear, it
> seems here ok case {0,1} {0,1,2} 

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#62078

asetofsymbols@gmail.com writes:
> Ben wrote:
> <Have you found an error case?
>
> No. as in the algo authors use 1
> for permutation on {1..N}
[...]

It looks like you've paid some attention to my request that you use the
usual "> " quoting convention, but now you're using "<" rather than "> ".

I don't understand.  Google Groups does this for you.  It's easier to
get it right than to get it wrong.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#62082

Keith wrote:...

In the tablet it is as you say
when one press the button for write
the post: All is already quoted

In the cellphone instead when I 
press the button for write the post:
nothing is quoted.
This means one can easily to copy and
paste, but it is not easy add a
quote ">" to each line

[toc] | [prev] | [next] | [standalone]

#62084

asetofsymbols@gmail.com writes:

> Keith wrote:...
>
> In the tablet it is as you say
> when one press the button for write
> the post: All is already quoted
>
> In the cellphone instead when I 
> press the button for write the post:
> nothing is quoted.
> This means one can easily to copy and
> paste, but it is not easy add a
> quote ">" to each line

Wow, this really does turn out to be true (just tried it).  Google
groups is even worse an interface to usenet on a cell phone than on a
desktop.

If you click the "Desktop site" button at the lower right it'll send you
to the desktop site and you'll get the expected behavior when replying
to a post.  I'll agree, this shouldn't be necessary...

[toc] | [prev] | [next] | [standalone]

#62105

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
> asetofsymbols@gmail.com writes:
>> Keith wrote:...
>>
>> In the tablet it is as you say
>> when one press the button for write
>> the post: All is already quoted
>>
>> In the cellphone instead when I 
>> press the button for write the post:
>> nothing is quoted.
>> This means one can easily to copy and
>> paste, but it is not easy add a
>> quote ">" to each line
>
> Wow, this really does turn out to be true (just tried it).  Google
> groups is even worse an interface to usenet on a cell phone than on a
> desktop.
>
> If you click the "Desktop site" button at the lower right it'll send you
> to the desktop site and you'll get the expected behavior when replying
> to a post.  I'll agree, this shouldn't be necessary...

Interesting.  Changing the way the site is displayed between the
"desktop" and "mobile" versions is sensible.  Changing the behavior like
this is just annoying.

I just tried this on my phone (Android, Chrome browser).  The browser's
"Request desktop site" option doesn't work on groups.google.com, but the
"Desktop" link at the bottom right corner of the page does.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web