Assign numbers to letters with respect to lowest graph peaks

Question

I have string which is composed of letters. I want to assign each letter a unique number (letters that repeats should have assigned same number as first unique letter occurrence) and plot those numbers on graph. X-axis will represent the particular letters of string (read from left to right) and y-axis will represent the particular value assigned to letter. The problem is that I want to have graph with minimum peaks. String can be long sequence with repeating letters. In other words I need to assign to letters such numbers that will cause that the plot change over time will be minimal.

So basically this is OK:

STRING
123456

But this not, because graph does not grows/decreases continuously and there are peaks e.g. between S-T, T-R, R-I and I-N (actually it fits criteria only for N-G)

STRING
162534

More complicated example: imagine string "STRINGS" and those two possibilities:

##############
# 1s example #
##############

Letter-Number mapping:
######################
STRINGS
6431256

Distances:
##########
S-T:2
T-R:1
R-I:2
I-N:1
N-G:3
G-S:1

Peak changes:
#############
2-1:T
1-2:T
2-1:T
1-3:T
3-1:T

###############
# 2nd example #
###############

Letter-Number mapping:
######################
STRINGS
1356421

Distances:
##########
S-T:2
T-R:2
R-I:1
I-N:2
N-G:2
G-S:1

Peak changes:
#############
2-2:F
2-1:T
1-2:T
2-2:F
2-1:T

Then the winner is 2nd example because it's maximum distance is less than the maximum distance in 1st example. I can imagine situations where both max distances can be same then the criteria should be the peak changes. In this case 2nd also beats 1st (F - does not change, T - change) because 1st is always changing and 2nd does not change in 2/5 cases

1st: TTTTT
vs
2nd: TFTFT

Is there any theory related to this? Is this even CS theory or some genetic algorithm or what problem set is this? Some library that already does this would be fine e.g. for python, perl etc.

PS: Sorry but I did not know which tags or what title describe this problem the best.

Answer 1

This smells like it might be hard (e.g., NP-hard).

Therefore, I suggest solving it with a SAT solver. SAT solvers implement a number of clever optimizations. Rather than trying to devise custom optimizations for this specific problem, you might try using an off-the-shelf SAT solver: that might be a much more efficient use of your time. In particular, here's what I would try. I would formulate the problem as follows:

Input: a string $S$ with $n$ unique letters, an integer $d$

Question: is there an assignment that maps each letter to a different number in $\{1,2,\dots,n\}$, such that any pair of adjacent letters are mapped to numbers that differ by at most $d$?

You can then formulate this as a SAT instance, in a fairly straightforward way. For instance, you can use a one-hot encoding: introduce boolean variables $x_{c,j}$, where $x_{c,j}=$ True means that the letter $c$ is mapped to the number $j$. Now if letters $c,c'$ are adjacent in the string $S$, you get a constraint $\bigvee_{|j-j'|\le d} (x_{c,j} \land x_{c',j'})$. You also get constraints forcing different letters to map to different numbers.

Finally, throw this to an off-the-shelf SAT solver. If it finds a solution, you know that distance $d$ is achievable. Otherwise, it's not: distance $d$ is unattainable. You can now iterate over $d=1$, $d=2$, $d=3$, etc., until you get the first solution. (You can also try binary search, but I suspect it might be less efficient.)

This doesn't account for peaks, because I couldn't understand your definition of the peak stuff.