1
$\begingroup$

If I have a sorted array, e.g.

['A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'C', 'C']

Is there an algorithm for turning this into:

['A', 'B', 'C', 'B', 'A', 'B', 'A', 'B', 'C', 'B']

i.e. One of the maximally unsorted permutations, when considered as a circular buffer.

There may be many maximally unsorted permutations; many will be rotations or mirrors of each other.

The "circular buffer" restriction means that the first and last positions should be considered adjacent, like any other two neighbours.

The "unsortedness" is the sum of the reciprocals of the (circular) offsets between identical elements.

For the sorted list, far above:

A: 1 + 1 + 1/8                 ==  2 1/8
B: 1 + 1 + 1 + 1 + 1 + 1/5     ==  5 1/5
C: 1 + 1/9                     ==  1 1/9
                                  -------
                  unsortedness ==  7.436

For the unsorted list, above:

A: 1/4 + 1/2 + 1/4             ==  1
B: 1/2 + 1/2 + 1/2 + 1/2 + 1/2 ==  2 1/2
C: 1/6 + 1/4                   ==    5/12      
                                  -------
                  unsortedness ==  3.917
Improve this question
$\endgroup$
6
  • $\begingroup$ Have you tried a greedy method? $\endgroup$
    – Nathaniel
    Commented Nov 22 at 17:32
  • $\begingroup$ How large are your arrays in practice? $\endgroup$
    – D.W. ♦
    Commented Nov 22 at 21:12
  • 2
    $\begingroup$ This sounds like the problem of evenly distributing items in a list. See stackoverflow.com/q/37452547/56778 and cs.stackexchange.com/q/29709/8314 $\endgroup$
    – Jim Mischel
    Commented Nov 23 at 1:16
  • $\begingroup$ @D.W. They are 100 items or less, and the process only needs to happen once. Any sane amount of big-O complexity will be fine @ 3GHz. $\endgroup$
    – fadedbee
    Commented Nov 23 at 11:19
  • $\begingroup$ Got it, thank you. How many unique items do you expect to have? Also do you need the exact optimum or would you be satisfied with an algorithm that usually yields a solution that is fairly close to optimal? $\endgroup$
    – D.W. ♦
    Commented Nov 23 at 21:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.