CODEWITHSUNDEEP
rubyarraysalgorithmmathsequence
edc505
edc505

Reputation: 871

Rearranging a sequence to maximize difference in order, ruby

I have an ordered sequence in the form of an array. e.g.

original_order = [1,2,3,4,5,6,7,8,9,10]

I want to know how to re-order the sequence, with the maximum difference in order, with regard to the original order. Specifically, I want to know what order would give the Maximum "score", when running the code below:

Put simply, the below calculates the distance that each value from the sequence has "moved" in the rearranged sequence (array called rearranged), when compared to its position in the original_order sequence. It then sums the differences (distances moved) for each value, to give an overall score of "difference in order" for the rearrangement. Someone told me that this "score" I am calculating can be defined as the ordinal similarity between the two sequences (original order and rearranged).

I think the max score can be obtained by running the code with the rearranged order as the reversed original order. I have not found a method of rearrangement that has a higher score than this, though If anyone thinks I am wrong please let me know (for the example original_order above this would be max_score = 50). I think that no other rearrangement of the sequence order can give a higher score (although there are other orders that give the same score).

position = original_order.map{|x| rearranged.index(x)} #works out the index of original_order values in rearranged
index_values = Array(0..(original_order.length - 1)) # array of index values for original_order
both = []
both << position
both << index_values
difference = both.transpose.map {|x| x.reduce(:-)} # taking away old position from new position, to find the distance that the value has "moved" when re-ordered
difference_abs = []
difference.each do |i|
    difference_abs << i.abs
end
score = difference_abs.inject(:+)

What I would like to know is:

  1. if my hypothesis that the reversed order will always give the highest possible score, regardless of the length of the sequence array, is correct

  2. a mathematical explanation of what my code does, and why simply reversing the original order gives the highest possible score

  3. if ordinal similarity is an accurate way of defining my score metric, and if not, what is?

Also, any tips on simplifying my code are welcome.

Upvotes: 2

Views: 504

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

The problem can be modelled as an assignment problem.

If the original array is {1, 2, 3, 4}, then in the final array, there are 4 positions that need to be filled with a single element each. This results in a 4x4 assignment matrix with the corresponding scores. 

  positions
   1 2 3 4 
1  0 1 2 3
2  1 0 1 2
3  2 1 0 1
4  3 2 1 0

Convert the scores to costs by negating them and adding 3 to all the elements (although as pointed out, adding a constant is not necessary).

  positions
   1 2 3 4 
1  3 2 1 0
2  2 3 2 1
3  1 2 3 2
4  0 1 2 3

You should be able to apply the Hungarian Algorithm to solve the above assignment problem. Note that there shall be more than 1 solution.

EDIT: As Cary Swoveland pointed out, the above problem can be solved quickly by a normal LP solving algorithm like the revised Simplex where the variables need not be integers.

Upvotes: 1

Related Questions