Conference rusure::math

    Say you have an initial sequence of length "n", to which you wish to
    repeatedly apply the permutation transformation T, to eventually get
    all permutations.

    Look at the symbol which appears in a particular location, say location
    i1.  Now apply T.  T moves the symbol somewhere.  If it "moves" it back
    to i1, then that symbol will "stay" at i1 through all further
    applications and none of the reached permutations will have it at any
    other location, and so it will not be "complete".  It must, therefore,
    move it to some other location i2.

    Now apply T again.  T might leave the symbol at i2, in which case no
    other locations than i1 (once) and i2 will ever be reached.  T might
    leave the symbols at i1.  In that case it will on the next application
    end up at i2 again.  It will therefore move back and forth between i1
    and i2 and never reach other positions.  It must therefore go to
    a new location i3.

    The same argument applies until "in" at which point all of the
    locations will have been reached.  The next tranformation will bring
    the symbol back to its starting point.  It therefore moves through the
    locations with period n.

    But the same applies to all the symbols.  So if each symbol must be
    able to reach each location, T must produce a cycle of length n.  But
    for n>2 the number of permutations is greater than n, so no permutation
    transformation exists which will produce all permutations.

				    Topher

    What .0 seems to be asking for is the single generator of the full
    permutation group on a set. That would mean that the group is cyclic.
    But none of the permutation groups are cyclic -- unless the set has 2
    elements.

        How about this rule...go to the next higher lexicographically.
        Then we do 1234 -> 1243 -> 1324 -> 1342 -> 1423 -> 1432 ->
        2134 -> 2143 -> 2314 -> 2341 -> 2413 -> 2431 -> 3124 -> 3142
        -> 3214 -> 3241 -> 3412 -> 3421 -> 4123 -> 4132 -> 4213 ->
        4231 -> 4312 -> 4321 -> oops, got stuck.  It gets all 24 but
        it doesn't go back.
        
        Dan

I don't quite buy the proof yet.  Your proof seems to assume that the
element at position i1 will always either *stay* at position i1, or always
*move* in some cyclic fashion.

What't to say that some rule doesn't *sometimes* move the element at i1
and sometimes not.

Clearly, the lexicographical rule "works", but it's unclear how to state
it as a simple rule.

Let's try some more rules.  How about:

	If last digit is even, rotate left, and swap first two elements,
	otherwise rotate right and swap last two elements.

1 2 3 4
3 2 4 1
1 3 4 2
4 3 2 1
1 4 2 3
3 1 2 4
2 1 4 3
3 2 4 1

This rule managed to hit SEVEN of the elements.  So our cycle length is six
(since we're going to now loop on 3241), which is greater than n, so doesn't
that disprove your theory ?

    Somewhere we've got different levels of "rules".  We can easily
    "adjust" the lexicographic rule to work mod n! so that must be a
    workable solution.  Why doesn't it satisfy us?
    
    Dick

Article 13367 of sci.math:
Path: shlump.nac.dec.com!decuac!haven!uflorida!gatech!rutgers!cunixf.cc.columbia.edu!cunixd.cc.columbia.edu!kasdan
From: [email protected] (John Kasdan)
Newsgroups: sci.math
Subject: Re: kth permutation
Keywords: Campanology
Message-ID: <[email protected]>
Date: 13 Nov 90 16:24:29 GMT
References: <[email protected]> <[email protected]> <[email protected]>
Sender: [email protected] (The Daily News)
Distribution: usa
Organization: Columbia University
Lines: 68

In article <[email protected]> [email protected] (Ravikumar Chennagiri) writes:
>Hello everyone,
>
>I am interested in a procedure to generate the kth permutation
>in Fike's order.  [Fike's order enumerates permutations of
>1..n such that from one permutation to the next, there
>is a single pair of adjacent elements are interchanged.
>e.g. for n=3, 
> 123 132 312 321 231 213
>
>Has anyone got this procedure/a reference to it?
>
>Thanks a 10! 
>
>Ravikumar


Funny that you should ask this while cable television is showing a 
version of the Lord Peter Wimsey story 'The Nine Tailors'. I believe 
that there are several different ways of doing this and that the
original research in this area was done in aid of campanology, the
obscure English practice of ringing changes. 

The generalization of the example you give is done recursively. I take
the following description from "Combinatorial Algorithms" by Reingold,
Nievergelt and Deo. (By the way, I have found this to be a readable
and informative book but have rarely seen any references to it. Does
anyone else know of/ have opinions about this book?)

The idea is to assume that you have an enumerated set of permutations
of {1,...,n-1} and then to "add in" n by placing it to the right of
the i-th permutation, if i is odd and to the left if i is even. Then
you let n move to the other end. So, to extend your example to
{1,2,3,4}, we go

       (1234)
(123)  (1243)
       (1423)
       (4123)

       (4132)
       (1432)
(132)  (1342)
       (1324)

       (3124)
(312)  (3142)
        ...  etc.

The problem with this method, for bell ringing, is that the highest
numbered bell is the one whose position is changing n-1 of n times.
I think that there are many other methods (which I believe to have
quaint names like Grandsire triplets) of generating permutations by
single transposition. I also remember that some magazine, probably the 
Monthly, had an article on this a while ago. Does anyone happen to
have the reference?
_________________
/KAS            
                        John Kasdan,
   +----------+         Columbia University, School of Law
   | MY PART  |          435 West 116th St., New York, NY 10027
   |  WORQS   |
   +----------+         internet: [email protected]
    \___||___/          bitnet: [email protected]
    /oooooooo\          uucp: 
   /ooooooooo \     {rutgers,seismo,topaz}!columbia!cunixd!kasdan
  / oooooooooo \
  --------------

I suppose the only thing "wrong" with the lexicographic rule is that
it is hard to state as a rule.  I was curious about how simple a rule
we could come up with that permutes through a maximum of the combinations.

/Eric

    Yes, the problem is solvable if we allow the rule to be conditional
    either on the contents (relative to the original) of the last
    permutation, or on the number of the step, or both.  All your examples
    were "memoryless" (i.e., the rule was "apply this single permutation")
    and I assumed that is what you wanted.

					Topher

re: .6

While meandering through esoteric topics in a notes conference I read for 
entertainment, I love seeing an obscure reference to a book written by
two of my professors at University of Illinois...  Not to mention the equally
obscure art of ringing changes...

Dr. Jurg Nievergelt and Dr. Rheingold.  Dr. N was very entertaining educator.
Dr. R was very demanding.

>>The generalization of the example you give is done recursively. I take
>>the following description from "Combinatorial Algorithms" by Reingold,
>>Nievergelt and Deo. (By the way, I have found this to be a readable
>>and informative book but have rarely seen any references to it. Does
>>anyone else know of/ have opinions about this book?)

Well, actually, the lexicographic rule is definable without memory.

For example, suppose we're at

	2341

4 is greater than 1, so we know we've already been to 2314.

3 is less than 4, so we should go to 2413.

This is statable as a rule, but not easily.

    In this case the "memory" is built in, but it is there nevertheless.
    The memory is contained in the order of the elements.  You have to
    look at that state information to determine the permutation produced by
    the next application of the rule -- at least that is the sense that
    I meant by memory in my posting.

    Look at it this way.  You have two seperate processors.  One has a
    vector of objects.  The other sends it directions about how to
    rearrange the objects.  The "memoryless" (which might also be called
    "unconditional") processes to accomplish this (which as I showed, do
    not exist) need to keep neither internal state nor pay attention to
    the external state.  Since the rule is unconditional, it may be thought
    of as simpler than any conditional rule.

					Topher