Velocity Reviews > permutations II

# permutations II

Bill Cunningham
Guest
Posts: n/a

 04-28-2009

"luserXtrog" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

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

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

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...t_passing.html

Bill Cunningham
Guest
Posts: n/a

 04-28-2009

"luserXtrog" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

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

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

hth
--
lxt

Ben Bacarisse
Guest
Posts: n/a

 04-28-2009
"Bill Cunningham" <(E-Mail Removed)> writes:

> "luserXtrog" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>
> Alright. This would be easier in person with paper, but here goes.

<snip>
> 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...t_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).

--
Ben.

Keith Thompson
Guest
Posts: n/a

 04-28-2009
"Bill Cunningham" <(E-Mail Removed)> writes:
> <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...

[...]
> 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.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

luserXtrog
Guest
Posts: n/a

 04-28-2009
On Apr 27, 8:39*pm, "Bill Cunningham" <(E-Mail Removed)> wrote:
> "luserXtrog" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>

<snip intro to inductive exploration>

> 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
>
> * * 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...rsion_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.

--
lxt

BartC
Guest
Posts: n/a

 04-28-2009

"Barry Schwarz" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
> <(E-Mail Removed)> wrote:
>
>>
>><(E-Mail Removed)> wrote in message
>>news:(E-Mail Removed)...
>>
>>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".

How many of "Aa"?

--
Bartc

Keith Thompson
Guest
Posts: n/a

 04-28-2009
"BartC" <(E-Mail Removed)> writes:
> "Barry Schwarz" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
>> <(E-Mail Removed)> wrote:

[...]
>>>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".

>
> 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?)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Bill Cunningham
Guest
Posts: n/a

 04-28-2009

"Ben Bacarisse" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> 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?

> 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).
>
> --
> Ben.

Carl
Guest
Posts: n/a

 04-28-2009
Bill Cunningham wrote:
> "Ben Bacarisse" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>
>> 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?
>
>> 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).
>>
>> --
>> Ben.

>
>

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

BartC
Guest
Posts: n/a

 04-28-2009

"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "BartC" <(E-Mail Removed)> writes:
>> "Barry Schwarz" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed)...
>>> On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
>>> <(E-Mail Removed)> wrote:

> [...]
>>>>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".

>>
>> 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?)

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).

--
Bartc