# Minimum number of moves to create a new permutation

Edit: Before you begin, please note that a move refers to swapping a pair of letters (thanks to ferfer93)

Ok, so I understand the title is a bit ambiguous, so I'll clarify it further below:

Let us take two objects only, A and B, that are repeated to make a, I don't know what to call it, a set, say. This 'set' would look like, for example, AABABAAB, that is, a permutation of 5 As and 3 Bs.

Now, it is intuitive that to generate another permutation with the same number of As and Bs, you need not move all letters about... there is indeed the smallest number of moves that will have to be made to produce something like (I'm not trying to be creative here) AAABBAAB. Obviously, the smallest move that should be done to make AABABAAB into AAABBAAB is just one (move the first B ahead of the third A).

I've been thinking that it might be possible to arrive at a solution if the permutations were lexicographically ordered, the following is a list of them excluding repetitions (56);

AAAAABBB AAAABABB AAAABBAB AAAABBBA AAABAABB AAABABAB AAABABBA AAABBAAB AAABBABA AAABBBAA AABAAABB AABAABAB AABAABBA AABABAAB AABABABA AABABBAA AABBAAAB AABBAABA AABBABAA AABBBAAA ABAAAABB ABAAABAB ABAAABBA ABAABAAB ABAABABA ABAABBAA ABABAAAB ABABAABA ABABABAA ABABBAAA ABBAAAAB ABBAAABA ABBAABAA ABBABAAA ABBBAAAA BAAAAABB BAAAABAB BAAAABBA BAAABAAB BAAABABA BAAABBAA BAABAAAB BAABAABA BAABABAA BAABBAAA BABAAAAB BABAAABA BABAABAA BABABAAA BABBAAAA BBAAAAAB BBAAAABA BBAAABAA BBAABAAA BBABAAAA BBBAAAAA

So... AABABAAB is the 14th permutation by alphabetical order, and AAABBAAB is the 9th. So the questions are;

A. What is the least amount of moves (which obviously cannot be greater than the total number of As and Bs in the 'set') that have to be made to convert the $n$th permutation to the $m$th, given a 'set' of only $x$ As and $y$ Bs? Do note that all As and all Bs are similar, so all AABBABAAs are the same AABBABAA.

B. How would you know which As and which Bs to move? Probably an alphabetically ordered permutation list (excluding repetitions) would help...? (because I suppose this is a sorting problem)

C. And a final question... under which values for $n$ and $m$ would the solution to A be greatest?

And oh, I forgot - thanks!

-
You may need to define what you mean by a "move." That is, what are the legal moves that you allow? –  Anon Jan 10 '13 at 9:43
By move, I mean any reposition of an item in the 'set' back or forth its former position. Like for example I have the possible moves for A in the 'set' 123A: 12A3, 1A23 and A123. So to say, all repositions are legal. And FYI all As and Bs are similar, as in the 'set' [A A BB] is the same as [A ABB]. –  Sushruth Sivaramakrishnan Jan 10 '13 at 11:15
And in my above example, no movement is not a move, so 123A isn't a valid move for A in 123A. –  Sushruth Sivaramakrishnan Jan 10 '13 at 11:22

You're being a little ambigous with some things, specially with the word "move". I guess you mean move is swaping a pair of letters. If that's it, then as you list of permutations all have the same numbers of As and Bs, and you only have two kind of symbols, the minimum amount of moves consist of swaping every pair of As and Bs that are not in place, that is the minimum amount of moves is $n/2$, where $n$ is the number of symbols (As or Bs) that are not in place.
Yeah thanks, I made the necessary edits. But now that I think of it... the answer IMO has to be $n/2$... at most. See, AABABAAB is the 14th permutation in alphabetic order, and AAABBAAB is the 9th. So, there is a swap of only one pair, which is [AB] in AA[AB]BAAB to make AA[BA]BAAB = AABABAAB. –  Sushruth Sivaramakrishnan Jan 10 '13 at 11:57
What I'm asking is - what's the least number of swaps it takes to get from the $n$th to the $m$th permutation, where $n$ and $m$ are the indices of the permutations when they are ordered lexicographically, excluding repetitions? –  Sushruth Sivaramakrishnan Jan 10 '13 at 12:01
It's what I said. If you go through both strings: AAABBAAB and AABABAAB, then the only different letters are the third and the fourth, so $n=2$ and the minimum moves are $n/2=1$. Is that what you meant for moves? Or are moves just moves from one to one in the list you made in your first post? –  MyUserIsThis Jan 10 '13 at 12:30