1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 1. I can't understand the objective function you are trying to minimize. Can you specify it mathematically, rather than by a complicated example? A simple math formula is often a cleaner way to specify something (a single example is rarely a good specification). For instance, I can't understand the precise definition of what counts as a "peak change". 2. How long are your strings? How many unique letters do they have? (typically, roughly) $\endgroup$
    – D.W.
    Commented May 20, 2015 at 6:44
  • $\begingroup$ Unfortunately I have not such math background to being able to define this, but your answer gives a big clue of how to do this. Distance is change between subsequent letters and peek changes are changes between subsequent distances represented as a true or false. $\endgroup$ Commented May 20, 2015 at 7:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you D.W. never heard of anything that is called SAT, a brief googling shows very interesting stuff, wow. If I understand you say that I can specify the problem exactly as you've described and put it inside off-the-shelf SAT solver and it will give result? Are there any off-the-shelf SAT solver available or I have to code it myself (I have no idea how). $\endgroup$ Commented May 20, 2015 at 7:30
  • $\begingroup$ D.W. Maybe I will say some nonsense but doesn't functional languages like haskell work similar to SAT? I'm referring to fact that in functional you specify what yo want as a result and now how to do it as it is in procedural (this perfectly fits on the question you've posted "is there an assignment that maps each letter to a different number in {1,2,…,n}, such that any pair of adjacent letters are mapped to numbers that differ by at most d?") I suppose this is what functional languages are made for. Is this correct or not? $\endgroup$ Commented May 20, 2015 at 7:42
  • $\begingroup$ @WakanTanka, no. You might be thinking of declarative languages (e.g., Prolog), though. $\endgroup$
    – D.W.
    Commented May 20, 2015 at 7:43
  • $\begingroup$ D.W. can you please point me to some library or software or something that I can use to solve this? Thank you $\endgroup$ Commented May 20, 2015 at 12:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.