3
$\begingroup$

Let's us say you have a finite sequence of things. Some are identical, some distinct. For example:

$$\langle 2,5,7,2,3\rangle$$

Now, under what conditions can each permutation of a sequence be reached through swapping adjacent items, such that you begin and end on the same sequence. Also, when it does exist, what order do you do the swaps.

Note that for those with experience in graph theory, you could represent each distinct permutation with a point, and have an edge for each swap. Than the problem reduces to if there is an Hamiltonian cycle.

Note: Partial answers are fine. Like for example, if you know an algorithm for a specific case, say, when all items are unique, post it. Or if you know a specific case that is impossible, post your explanation.

$\endgroup$
  • $\begingroup$ Well, surely every permutation is attainable. Are you asking to travel through each permutation once and only once? $\endgroup$ – chubakueno Jun 13 '14 at 3:04
  • $\begingroup$ Is it significant that some of the items are identical? That is, in your example $\langle2,5,7,2,3\rangle$, do you specifically want to avoid the permutation that swaps the first and the fourth item because it produces a sequence identical with the original? $\endgroup$ – Rahul Jun 13 '14 at 4:25
  • $\begingroup$ I didn't notice the "end on the same sequence" before but I think it's more appropriate to call it Hamiltonian cycle. Well, 1 special case is rather easy to figure out: if there are exactly 2 type of items, then it's impossible, as the state where everything of the same type is to a side is only reachable from 1 other state, so you cannot form a cycle. $\endgroup$ – Gina Jun 13 '14 at 5:03
  • $\begingroup$ Yes, it is possible. The problem is core to the British style of bell ringing. More on that subject at en.wikipedia.org/wiki/Change_ringing#Method_ringing $\endgroup$ – occulus Aug 24 '14 at 21:30
  • $\begingroup$ @occulus Huh, I thought that book i was reading was just making that up. I guess he plagiarized reality. $\endgroup$ – PyRulez Aug 24 '14 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.