0

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my disposal, I have a single method that I can use:

move(fromIndex, toIndex)

Thus, to achieve my desired array, I could call the method a number of times:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

Thus, I also have a list of move() operations to achieve my desired result. The list of move() operations can possibly be reduced in size by changing the order and the indexes, to end up with the same result.

Is there an algorithm that I can use on my list of move() operations to reduce the number of operations to a minimum?

HelloWorld
  • 3,381
  • 5
  • 32
  • 58
  • This should be helpful: https://stackoverflow.com/questions/22899401/number-of-swaps-in-a-permutation Can you clearly explain what move does, as it does not seems to be a `swap` operation. – Thibault D. Apr 19 '19 at 09:50
  • Thanks. That is indeed interesting. move() moves an item at an index fromIndex to an index toIndex. If something already exists at toIndex, everything from there on out will be shifted right. Look at e.g. the comment in the first line of code. Two move() operations can be used to achieve a swap. – HelloWorld Apr 19 '19 at 10:00

1 Answers1

0

We can create a graph with an element pointing towards the number it needs to be swapped with to get to the desired position. Hence we will get multiple graphs with possible cycles. In your particular case,we will get

2->0->3->5->4->2 (first and last elements denote a cycle)

This means that 2 wants to be swapped with 0 to get to the desired position. Similarly,0 wants to be swapped with 3 to get to the desired position. Notice that 1 does not want to be swapped.

Now, we can swap two adjacent elements of the graph to reduce the graph size by 1. Say we swap 3 and 5 so now the arr = [0,1,2,5,4,3]. Now 3 is in desired state so we can remove it from graph

2->0->5->4->2

We need to repeat this process (m-1) times to remove the graph completely. Here m represents the number of edges of the graph. We can have multiple disconnected graphs or graphs without cycles. We need to make sure that we are swapping elements from the same graph. The final answer would be the sum of all steps (that is m-1 for each component) of the graph.

Community
  • 1
  • 1
P.Gupta
  • 485
  • 4
  • 18
  • Wouldn't that get me 6 moves as above example? How does it reduce the number of moves? E.g. the 6 moves could be reduced to 4, as such: move(5, 3);move(0, 2);move(1, 0);move(5, 2); – HelloWorld Apr 19 '19 at 11:52
  • yes, the answer would be m-1 where m represent edges. for the above case we can take move(2,0);move(0,3);move(3,5);move(4,5); This is because if the graph is 4->5->4. We need one move to resolve it that is exchange (4,5). – P.Gupta Apr 20 '19 at 13:45