permutations II

[Bill Cunningham]

Well this is as far as I've got with my permutations program if you call
it that. This is what I want it to look like though. With a prompt. I have
to be able to read the number of characters and sift them around. Any hints?

#include <stdio.h>
#include <limits.h>

int main(void)
{
char input[CHAR_MAX];
printf("enter word-> ");
fflush(stdout);
fgets(input, CHAR_MAX, stdin);
}

Bill

 

[osmium]

"Bill Cunningham" wrrote:

Well this is as far as I've got with my permutations program if you
call it that. This is what I want it to look like though. With a prompt. I
have to be able to read the number of characters and sift them around. Any
hints?

#include <stdio.h>
#include <limits.h>

Don't include things, such as limits.h, that you don't use. It's confusing.

int main(void)
{
char input[CHAR_MAX];
printf("enter word-> ");
fflush(stdout);
fgets(input, CHAR_MAX, stdin);
}

Decide whether you want to do it recursively or not. Then go back to last
weekend's hints and follow the ones that pertain to that approach. I think
most seasoned programmers would favor the recursive approach but YMMV. I
think there might be easier ways to get your arms around recursion. Have
you written ANY working program that uses recursion? If not, I would look
for something a bit simpler to do first.

 

[Eric Sosman]

"Bill Cunningham" wrrote:


Don't include things, such as limits.h, that you don't use. It's confusing.

He's using CHAR_MAX. There's no good reason why he should
be using it, but using it he is.

int main(void)
{
char input[CHAR_MAX];
printf("enter word-> ");
fflush(stdout);
fgets(input, CHAR_MAX, stdin);
}

Decide whether you want to do it recursively or not. Then go back to last
weekend's hints and follow the ones that pertain to that approach. I think
most seasoned programmers would favor the recursive approach but YMMV. I
think there might be easier ways to get your arms around recursion. Have
you written ANY working program that uses recursion? If not, I would look
for something a bit simpler to do first.

 

[Guest]

    Well this is as far as I've got with my permutations program if you call
it that. This is what I want it to look like though. With a prompt. I have
to be able to read the number of characters and sift them around. Any hints?

define "read the number of characters"
define "sift them around"


<snip>

 

[Bill Cunningham]

define "read the number of characters"
define "sift them around"


<snip>

I think I need a char** definition here. Maybe I could replace CHAR_MAX
with 40 or something like that. I'll post something soon that I believe
might get me closer.

Bill

 

[CBFalconer]

"Bill Cunningham" wrrote:
....snip ...

#include <stdio.h>
#include <limits.h>

Don't include things, such as limits.h, that you don't use. It's
confusing.

int main(void) {
char input[CHAR_MAX];
printf("enter word-> ");
fflush(stdout);
fgets(input, CHAR_MAX, stdin);
}

Without <limits.h>, how do you suggest discovering the value of
CHAR_MAX?

 

[Bill Cunningham]

define "read the number of characters"
define "sift them around"


<snip>

Now I need to understand this factorial formula right first. If a word
is 7 letters long is this how it is to be figured?

7*6*5*4*3*2*1=possible permutations?

Bill

 

[luserXtrog]

define "read the number of characters"
define "sift them around"

<snip>

    Now I need to understand this factorial formula right first. If a word
is 7 letters long is this how it is to be figured?

7*6*5*4*3*2*1=possible permutations?

Alright. This would be easier in person with paper, but here goes.
The usual way to tackle this sort of thing is build up a sense
of the pattern involved. It's rather like constructing an inductive
proof; you start with the simplest example; then the next one;
then notice how the two differ and make a prediction about how
each case will differ from the previous; then you examine the third
example and check how it jives with the prediction. If your pattern
applies no matter how many cases you can produce (in a proof, this
is the inductive step), you're home free.

With permutations, you're likely to confuse yourself by not
sufficiently distinguishing between the set of source elements
(which here is a string) and the ordered selection that needs
to be generated (which also happens to be a string). On paper,
this can be made more clear by writing the source vertically
and constructing your permutations horizontally.

Example. Permute the single character 'a'.

source
a
permutations: a

Example. Permute the two characters 'a' and 'b'.

source
a
b
permutations: ab ba

With me so far?
Now you may not be able to fully enunciate the pattern at this
point. Keep going and something will have to click eventually.

Example. Permute the characters in "abc".

source
a
b
c
permutations:
abc acb
bac bca
cab cba

Now a pattern has emerged. The pattern was already present in
the way I (consciously or otherwise) chose to write these down.
I started by putting something in the leftmost slot and then
performing the 2-character permutation on the remaining slots
with the remaining elements.

I'd recommend you skip in-place manipulations for now.
Make a copy to use as the source set and make an empty
array to be filled in with characters selected from the
source. When you fill a slot erase the character from
the source. When the source is empty, your string should
be filled and you can blank out the string and refill
the source from the *real* source (which you've wisely
left unmodified for just this purpose). It'll mean
3 character arrays instead of just one, but if they're
named sensibly this should help you keep them straight.

hth

 

[Barry Schwarz]

define "read the number of characters"
define "sift them around"


<snip>

I think I need a char** definition here. Maybe I could replace CHAR_MAX
with 40 or something like that. I'll post something soon that I believe
might get me closer.

Your just guessing again. If you don't know how you intend to use it,
you don't need it.

 

[Barry Schwarz]

define "read the number of characters"
define "sift them around"


<snip>

Now I need to understand this factorial formula right first. If a word
is 7 letters long is this how it is to be figured?

7*6*5*4*3*2*1=possible permutations?

Only if the letters are distinct. There are two permutations of "ab"
but only one unique permutation of "aa".

 

[Bill Cunningham]

Alright. This would be easier in person with paper, but here goes.
The usual way to tackle this sort of thing is build up a sense
of the pattern involved. It's rather like constructing an inductive
proof; you start with the simplest example; then the next one;
then notice how the two differ and make a prediction about how
each case will differ from the previous; then you examine the third
example and check how it jives with the prediction. If your pattern
applies no matter how many cases you can produce (in a proof, this
is the inductive step), you're home free.

With permutations, you're likely to confuse yourself by not
sufficiently distinguishing between the set of source elements
(which here is a string) and the ordered selection that needs
to be generated (which also happens to be a string). On paper,
this can be made more clear by writing the source vertically
and constructing your permutations horizontally.

Example. Permute the single character 'a'.

source
a
permutations: a

Example. Permute the two characters 'a' and 'b'.

source
a
b
permutations: ab ba

With me so far?
Now you may not be able to fully enunciate the pattern at this
point. Keep going and something will have to click eventually.

Example. Permute the characters in "abc".

source
a
b
c
permutations:
abc acb
bac bca
cab cba

Now a pattern has emerged. The pattern was already present in
the way I (consciously or otherwise) chose to write these down.
I started by putting something in the leftmost slot and then
performing the 2-character permutation on the remaining slots
with the remaining elements.

I'd recommend you skip in-place manipulations for now.
Make a copy to use as the source set and make an empty
array to be filled in with characters selected from the
source. When you fill a slot erase the character from
the source. When the source is empty, your string should
be filled and you can blank out the string and refill
the source from the *real* source (which you've wisely
left unmodified for just this purpose). It'll mean
3 character arrays instead of just one, but if they're
named sensibly this should help you keep them straight.

Is this recursion the recursion dmr did his doctorate on? Or
mathematicall recursion? Anyway Is recursion what I need? I have found this.
http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argument_passing.html

 

[Bill Cunningham]

Alright. This would be easier in person with paper, but here goes.
The usual way to tackle this sort of thing is build up a sense
of the pattern involved. It's rather like constructing an inductive
proof; you start with the simplest example; then the next one;
then notice how the two differ and make a prediction about how
each case will differ from the previous; then you examine the third
example and check how it jives with the prediction. If your pattern
applies no matter how many cases you can produce (in a proof, this
is the inductive step), you're home free.

With permutations, you're likely to confuse yourself by not
sufficiently distinguishing between the set of source elements
(which here is a string) and the ordered selection that needs
to be generated (which also happens to be a string). On paper,
this can be made more clear by writing the source vertically
and constructing your permutations horizontally.

Example. Permute the single character 'a'.

source
a
permutations: a

Example. Permute the two characters 'a' and 'b'.

source
a
b
permutations: ab ba

With me so far?

So far


Now you may not be able to fully enunciate the pattern at this
point. Keep going and something will have to click eventually.

Example. Permute the characters in "abc".

source
a
b
c
permutations:
abc acb
bac bca
cab cba

Now a pattern has emerged. The pattern was already present in
the way I (consciously or otherwise) chose to write these down.
I started by putting something in the leftmost slot and then
performing the 2-character permutation on the remaining slots
with the remaining elements.

Oh ok I see.


I'd recommend you skip in-place manipulations for now.
Make a copy to use as the source set and make an empty
array to be filled in with characters selected from the
source. When you fill a slot erase the character from
the source. When the source is empty, your string should
be filled and you can blank out the string and refill
the source from the *real* source (which you've wisely
left unmodified for just this purpose). It'll mean
3 character arrays instead of just one, but if they're
named sensibly this should help you keep them straight.

hth

 

[Ben Bacarisse]

Alright. This would be easier in person with paper, but here goes.

Is this recursion the recursion dmr did his doctorate on? Or
mathematicall recursion? Anyway Is recursion what I need? I have found this.
http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argument_passing.html

Yes. You can do it non-recursive in stead if you want: Keep a
counter that acts like an odometer but with each digit having its own
range. For n=4

0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
0 1 0 0
1 1 0 0
2 1 0 0
3 1 0 0
0 2 0 0
1 2 0 0
2 2 0 0
3 2 0 0
0 0 1 0
1 0 1 0
2 0 1 0
3 0 1 0
0 1 1 0
1 1 1 0
2 1 1 0
3 1 1 0
0 2 1 0
1 2 1 0
2 2 1 0
3 2 1 0

We can't count any more because the last counter has only on valid
value. Can you see the pattern? Could you take an array of n ints an
make the "next" counter value from it?

int increment_factorial_counter(int n, int *counter);

Every time this counter in increased, you can generate the
permutation it represents (but that bit can wait).

 

[Keith Thompson]

news:[email protected]... [...]
Now I need to understand this factorial formula right first. If a word
is 7 letters long is this how it is to be figured?

7*6*5*4*3*2*1=possible permutations?

Yes, assuming all the letters are distinct.

 

[luserXtrog]

I'd recommend you skip in-place manipulations for now.
Make a copy to use as the source set and make an empty
array to be filled in with characters selected from the
source. When you fill a slot erase the character from
the source. When the source is empty, your string should
be filled and you can blank out the string and refill
the source from the *real* source (which you've wisely
left unmodified for just this purpose). It'll mean
3 character arrays instead of just one, but if they're
named sensibly this should help you keep them straight.

    Is this recursion the recursion dmr did his doctorate on? Or
mathematicall recursion? Anyway Is recursion what I need? I have found this.http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argu...

I haven't read the paper; if Ben says so (and he does), I have
no reason to doubt it.

This link looks like good stuff but not necessarily the most
pertinent to this problem. The ability to think about the problem
in terms of recursion is definitely valuable. While the relation
between factorials and permutation is not necessarily useful
for producing the permutations (except perhaps for verifying
that you found the correct number of them!), the recursive
implementation of the factorial function is definitely useful
in its own right and could definitely shed some light on
how to go about constructing a recursive permutation function.
[goddam! that's a dense sentence!]

Basically, a recursive function needs to reduce the problem
to a self-call over a smaller problem.

I wouldn't say that permutations require recursion, but
permutations are possibly the perfect means to learn about
recursion.

 

[BartC]

Only if the letters are distinct. There are two permutations of "ab"
but only one unique permutation of "aa".

How many of "Aa"?

 

[Keith Thompson]

How many of "Aa"?

Two, "Aa" and "aA". Why do you ask? (There's been no suggestion that
uppercase and lowercase letters should be considered equivalent; is
there some reason they should be?)

 

[Bill Cunningham]

Yes. You can do it non-recursive in stead if you want: Keep a
counter that acts like an odometer but with each digit having its own
range. For n=4

0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
0 1 0 0
1 1 0 0
2 1 0 0
3 1 0 0
0 2 0 0
1 2 0 0
2 2 0 0
3 2 0 0
0 0 1 0
1 0 1 0
2 0 1 0
3 0 1 0
0 1 1 0
1 1 1 0
2 1 1 0
3 1 1 0
0 2 1 0
1 2 1 0
2 2 1 0
3 2 1 0

We can't count any more because the last counter has only on valid
value. Can you see the pattern? Could you take an array of n ints an
make the "next" counter value from it?

I don't think so. I don't know how to code it. I'm thinking using for?

 

[Carl]

I don't think so. I don't know how to code it. I'm thinking using for?

I believe you can code it that way. If you are interested, I can post
the source.

 

[BartC]

Two, "Aa" and "aA". Why do you ask? (There's been no suggestion that
uppercase and lowercase letters should be considered equivalent; is
there some reason they should be?)

In the real world letter case usually has no significance.

It only seems to be important in C code (and languages created by people
exposed to C) and Unix file names (possibly for the same reasons).