3
$\begingroup$

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. Assume each character in the set has a cost associated with it, consider the costs to be a=1, b=3, c=4, d=5, e=7.

for example

m = ['a', 'b', 'c', 'd', 'd', 'e', 'a']
n = ['b', 'b', 'b', 'a', 'c', 'e', 'd']

Suppose we would like to merge m and n to form a larger array s.

An example of s array could be

s = ['a', 'b', 'c', 'd', 'd', 'e', 'a', 'b', 'b', 'b', 'a', 'c', 'e', 'd']

or 

s = ['b', 'a', 'd', 'd', 'd', 'b', 'e', 'c', 'b', 'a', 'b', 'a', 'c', 'e']

If there are two or more identical characters adjacent to eachother a penalty is applied which is equal to: number of adjacent characters of the same type * the cost for that character. Consider the second example for s above which contains a sub-array ['d', 'd', 'd']. In this case a penalty of 3*5 will be applied because the cost associated with d is 5 and the number of repetitions of d is 3.

I need to design a dynamic programming algorithm which minimises the cost associated with s.

Does anyone have any resources, papers, or algorithms they could share to help point me in the right direction?

Improve this question
$\endgroup$
4
  • $\begingroup$ Please edit the question to show an merged array that minimises the cost associated. This is a general rule: always include an example that shows the expected correct answer. $\endgroup$ – John L. Apr 15 '19 at 14:32
  • $\begingroup$ Does s = ['b', 'a', 'd', 'b', 'd', 'e', 'd', 'c', 'b', 'a', 'b', 'a', 'c', 'e'] minimises the cost? $\endgroup$ – John L. Apr 15 '19 at 15:48
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W.♦ Apr 15 '19 at 18:05
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W.♦ Apr 19 '19 at 20:07
3
$\begingroup$

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible.

  1. Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum.
  2. Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ except $x$.
    1. If $c(x)\le 1 + \sigma$, return 0.
    2. Else return $p(x)(c(x) -\sigma))$, where $p(x)$ is the penalty associated with $x$.

The time-complexity of the algorithm is $O(\ell)$, where $\ell$ is the sum of the length of $m$ and the length of $n$.

Since the algorithm above is simple and clear, there is no need to apply the heavy machinery of dynamic programming.

Exercises

Here are two exercises that prove the correctness of the algorithm above.

Exercise 1. If $s(x)\le 1 + \sigma$, design a procedure to produce a merged array that does not have adjacent pairs of the same letter.

Exercise 2. If $s(x)\gt 1 + \sigma$, then any merged array must have at least $s(x) -\sigma$ $x$s each of which is adjacent to another $x$. Design a procedure to produce a merged array that has no other penalties except for $s(x) -\sigma$ $x$s.

Improve this answer
$\endgroup$
4
  • $\begingroup$ it also needs to produce s $\endgroup$ – user102961 Apr 15 '19 at 16:42
  • $\begingroup$ @DanielPahor The statements in two exercises are hints for how to produce a merge array with the minimum penalty. Here is a further hint for exercise 2. Treat all characters other than $x$ as the same letter, say, $z$. $\endgroup$ – John L. Apr 15 '19 at 18:30
  • $\begingroup$ In fact I was thinking items coming from both lists have to respect initial order. It would have made DP relevant. But your answer is consistant with the question 2nd example... Now I just don't understand the need to have 2 lists. $\endgroup$ – Optidad Apr 15 '19 at 21:26
  • $\begingroup$ @Vince I had thought the same as you before I posted my answer, as indicated by my comments to the question. DanielPahor, in case you had extra restrictions such as merging should be stable, i.e., the original array must be a subsequence of the merged array, please raise a new question. It would be great if you can add a reference to the problem or your motivation, bioinformatics. $\endgroup$ – John L. Apr 15 '19 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy