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.
Using entropy measured as sum of distance between same numbers, there exists very simple polynomial-time algorithm:
Count number of occurrences of each number.
Sort pairs < number,ocurrences > descending by occurrences.
Create empty table of the same size as input.
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.
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