wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Permutations with unique neighbours
        
(Message started by: Barukh on May 7^th, 2012, 9:15am)

Title: Permutations with unique neighbours
Post by Barukh on May 7^th, 2012, 9:15am

Devise an algorithm for generating a set of permutations of n numbers with the property that every pair of adjacent numbers appears only once.

Example: set of permutations for 4 elements:

(1 2 3 4), (2 4 1 3)

Title: Re: Permutations with unique neighbours
Post by towr on May 7^th, 2012, 9:47am

[hide]Make an undirected graph where each vertex represents one element and all elements are connected by edges; repeatedly extract a path through the all n elements (removing the edges used; which ensures each pair of adjacent numbers occurs only once)[/hide]

Title: Re: Permutations with unique neighbours
Post by Barukh on May 7^th, 2012, 10:13pm

Towr, does your algorithm ensure maximum number of permutations? ;)

Title: Re: Permutations with unique neighbours
Post by towr on May 7^th, 2012, 11:18pm

I don't know; possibly. Not by design, but perhaps by serendipity.

And another question, can the theoretical maximum number, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn/2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, always be reached?

Title: Re: Permutations with unique neighbours
Post by Barukh on May 7^th, 2012, 11:32pm

on 05/07/12 at 23:18:01, towr wrote:

And another question, can the theoretical maximum number always be reached?

I don't posses a proof for this (which automatically implies that I haven't got a way to turn serendipity into a design :-)).

But my intuition tells me "yes".

[hide]One way to start is to note that any number could be at the permutation boundary exactly once[/hide]

Any takers?

Title: Re: Permutations with unique neighbours
Post by towr on May 8^th, 2012, 12:30am

Well, as it is my algorithm definitely doesn't ensure the maximum number of permutations.
For n=6, you might get (1, 2, 3, 4, 5, 6), (4, 1, 3, 5, 2, 6), after which you can't pick a 3rd path through the graph (which does exist for some other choices for the second permutation).

[e]~~Perhaps it might help to add a condition that you have to use the edge(s) between vertices that have the most edges....~~ Oh, never mind...not sufficient..[/e]

Title: Re: Permutations with unique neighbours
Post by nks on May 12^th, 2012, 8:59pm

Quote:

Example: set of permutations for 4 elements:

(1 2 3 4), (2 4 1 3)

As pair inclusive , following combination is also possible . right ?
(1 2 4 3) , (2 1 3 4)

Title: Re: Permutations with unique neighbours
Post by towr on May 13^th, 2012, 1:08am

Both those permutations have the pair 1,2 and 3,4
Unless you interpret pair as ordered pair.

Title: Re: Permutations with unique neighbours
Post by d33p4k on May 14^th, 2012, 12:54pm

How about this,
For a sequence where a_i's are at odd position and b_i's at even,
a1 b1 a2 b2 a3 b3 a4 b4....
Keeping one subsequence fixed and rotating the other by two places,
an/2-1 b1 an b2 a1 b3 a2 b4...
The rotation can be done http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn/4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif times.

Then, the sequence can be partitioned into two,
a1 a2 a3 a4 ....... an-1/2 b1 b2 b3 b4.....bn-1/2
Since, members in a's and b's were not together in the previous permutation, the same operation can be applied to them individually. This can be done recursively. At, each recursion, the rotation of every group is done together but the number of rotations reduces by half.

This can be done,

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn/4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif+ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn/8http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif+ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn/16http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif+...http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/thickapprox.gif n/2 times.

Title: Re: Permutations with unique neighbours
Post by towr on May 17^th, 2012, 10:59am

@d33p4k
Either I'm not understanding your algorithm correctly, or it doesn't work as advertised.
For 12345678
It gives me
first 12345678
second 52741638
third 13572468, which gives a conflict.
Even if we swap it around to 24681357, I'm not seeing how to get to the fourth permutation.

As an improvement to my previous algorithm. I seem to get good results for even n, by taking using the pair that would close the previous permutation in a loop as the middle of the next one, taking the outermost edge the leads to an unused vertex and keeping it symmetric.
(And for odd n we can stick the last element in the middle.)

I've attached an example..
It remains to be proven this would always work.

Title: Re: Permutations with unique neighbours
Post by Grimbal on May 20^th, 2012, 10:50am

[hideb]
For n even, you can use the permutation
(0, 1, n-1, 2, n-2, ..., n/2-1, n/2+1, n/2)
and increment each value by 1 mod n.
For n=8 it gives
(0 1 7 2 6 3 5 4)
(1 2 0 3 7 4 6 5)
(2 3 1 4 0 5 7 6)
(3 4 2 5 1 6 0 7)
If you put the elements on a circle and draw these permutations, it is obvious what it does and how it works.

You have n(n-1)/2 possible pairs. Each permutation covers (n-1) pairs, so the max is n/2 permutations.

For n odd, the maximum is rounded down to (n-1)/2 permutations. That's the maximum for size n'=(n-1).
So you can just use the solution for (n-1), which is even, and add the extra element at the end. For n=9 you have an extra element '8' so you get:
(0 1 7 2 6 3 5 4 8)
(1 2 0 3 7 4 6 5 8)
(2 3 1 4 0 5 7 6 8)
(3 4 2 5 1 6 0 7 8)
[/hideb]

Title: Re: Permutations with unique neighbours
Post by towr on May 20^th, 2012, 12:39pm

I wish I'd thought of that.