Author |
Topic: Permutations with unique neighbours (Read 3895 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Permutations with unique neighbours
« on: May 7th, 2012, 9:15am » |
 Quote  Modify
|
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)
|
| « Last Edit: May 7th, 2012, 9:16am by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations with unique neighbours
« Reply #1 on: May 7th, 2012, 9:47am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Permutations with unique neighbours
« Reply #2 on: May 7th, 2012, 10:13pm » |
Quote Modify
|
Towr, does your algorithm ensure maximum number of permutations? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations with unique neighbours
« Reply #3 on: May 7th, 2012, 11:18pm » |
Quote Modify
|
I don't know; possibly. Not by design, but perhaps by serendipity.
And another question, can the theoretical maximum number,  n/2 , always be reached?
|
| « Last Edit: May 7th, 2012, 11:18pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Permutations with unique neighbours
« Reply #4 on: May 7th, 2012, 11:32pm » |
Quote Modify
|
on May 7th, 2012, 11:18pm, 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".
One way to start is to note that any number could be at the permutation boundary exactly once
Any takers?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations with unique neighbours
« Reply #5 on: May 8th, 2012, 12:30am » |
Quote Modify
|
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]
|
| « Last Edit: May 8th, 2012, 12:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Permutations with unique neighbours
« Reply #6 on: May 12th, 2012, 8:59pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations with unique neighbours
« Reply #7 on: May 13th, 2012, 1:08am » |
Quote Modify
|
Both those permutations have the pair 1,2 and 3,4
Unless you interpret pair as ordered pair.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
d33p4k
Newbie
Posts: 12
|
|
Re: Permutations with unique neighbours
« Reply #8 on: May 14th, 2012, 12:54pm » |
Quote Modify
|
How about this,
For a sequence where ai's are at odd position and bi'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 n/4 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,
n/4+ n/8+ n/16+... n/2 times.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
@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.
|
| « Last Edit: May 17th, 2012, 11:49pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Permutations with unique neighbours
« Reply #10 on: May 20th, 2012, 10:50am » |
Quote Modify
|
| hidden: |
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)
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
permutationswithuniquepairs.pdf