Search code examples
algorithmpolynomial-mathheuristicsentropynp-complete

Maximizing entropy inside integers array

I have an array as follow 44477125, and I would like to maximize the entropy so that the maximum of n-tuple be scattered. A result example would be 74574214.

This problem seems to be NP-Complete and I don't really have a function to measure the "entropy" of my array. (It could be the sum of distance between same numbers entropy(44477125)=3, entropy(74574214)=9)

What I'm looking for is an heuristic which could give me an acceptable result in a polynomial time.

Solution

  • Algorithm

    Using entropy measured as sum of distance between same numbers, there exists very simple polynomial-time algorithm:

    1. Count number of occurrences of each number.

    2. Sort pairs < number,ocurrences > descending by occurrences.

    3. Create empty table of the same size as input.

    4. For each pair< number, ocurrences >:

      a) get maximum_possible_distance = array_size/occurrences

      b) insert all occurrences of number in following indexes: 0*maximum_possible_distance, 1*maximum_possible_distance, 2*maximum_possible_distance, etc. If index is already taken, use the nearest empty index.

    Example

    Input array: 44477125

    1.Counting occurrences:

    <4 - 3>, <7 - 2>, <1 - 1>, <2 - 1>, <5 - 1>

    2.Sorting pairs < number - occurrences >

    It is already sorted.

    3.Create empty table:

    . . . . . . . .

    4.Insert occurrences:

    a) 1st pair <4 - 3> : maximum_possible_distance=8/3=2
    b) insert occurrences: we have: 4..4..4.
    c) 2nd pair <7 - 2> : maximum_possible_distance=8/2=4
    d) insert occurrences: we have: 47.4.74.
    e) 3rd pair <1 - 1> : maximum_possible_distance=8/1=8
    f) insert occurrences: we have: 4714.74.
    g) 4th pair <2 - 1> : maximum_possible_distance=8/1=8
    h) insert occurrences: we have: 4714274.
    i) 5th pair <5 - 1> : maximum_possible_distance=8/1=8
    j) insert occurrences: we have: 47142745