More on dynamic programming

Question

Two weeks ago I posted THIS question here about dynamic programming. User Andrea Corbellini answered precisely what I wanted, but I wanted to take the problem one more step further.

This is my function

def Opt(n):
    if len(n) == 1:
        return 0
    else:
        return sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                            for i in range(1, len(n)))

Let's say you would call

Opt( [ 1,2,3,4,5 ] )

The previous question solved the problem of computing the optimal value. Now, instead of the computing the optimum value 33 for the above example, I want to print the way we got to the most optimal solution (path to the optimal solution). So, I want to print the indices where the list got cut/divided to get to the optimal solution in the form of a list. So, the answer to the above example would be :

[ 3,2,1,4 ] ( Cut the pole/list at third marker/index, then after second index, then after first index and lastly at fourth index). That is the answer should be in the form of a list. The first element of the list will be the index where the first cut/division of the list should happen in the optimal path. The second element will be the second cut/division of the list and so on.

There can also be a different solution:

[ 3,4,2,1 ]

They both would still lead you to the correct output. So, it doesn't matter which one you printed. But, I have no idea how to trace and print the optimal path taken by the Dynamic Programming solution. By the way, I figured out a non-recursive solution to that problem that was solved in my previous question. But, I still can't figure out to print the path for the optimal solution. Here is the non-recursive code for the previous question, it might be helpful to solve the current problem.

def Opt(numbers):
prefix = [0]
for i in range(1,len(numbers)+1):
    prefix.append(prefix[i-1]+numbers[i-1])
results = [[]]
for i in range(0,len(numbers)):
    results[0].append(0)
for i in range(1,len(numbers)):
    results.append([])
    for j in range(0,len(numbers)):
        results[i].append([])
for i in range(2,len(numbers)+1): # for all lenghts (of by 1)
    for j in range(0,len(numbers)-i+1): # for all beginning
        results[i-1][j] = results[0][j]+results[i-2][j+1]+prefix[j+i]-prefix[j]
        for k in range(1,i-1): # for all splits
            if results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j] < results[i-1][j]:
                results[i-1][j] = results[k][j]+results[i-2-k][j+k+1]+prefix[j+i]-prefix[j]
return results[len(numbers)-1][0]

It is worth mentioning that finding the "path" of a dynamic programming solution is much more difficult than just finding the solution. — OneCricketeer
– OneCricketeer, Commented Feb 18, 2016 at 21:27
@cat how to change the output from the algorithm as I explained — TheTask1337
– TheTask1337, Commented Feb 18, 2016 at 21:38
@TheTask1337 Not only is your "question" buried in an unnecessary wall of text that doesn't help me to understand why I'm reading this, but the problem statement itself is nearly incomprehensible for a native speaker. Please try to pinpoint exactly what you'd like help with, and explain it so the casual observer can get what's going on. — cat
– cat, Commented Feb 18, 2016 at 21:41
@cat After admin reformated my question, it might be more clear. Thank you though. — TheTask1337
– TheTask1337, Commented Feb 18, 2016 at 21:42

phoenix · Accepted Answer · 2016-02-20 14:36:20Z

Here is one way of printing the selected :

I used the recursive solution using memoization provided by @Andrea Corbellini in your previous question. This is shown below:

cache = {}

def Opt(n):
    # tuple objects are hashable and can be put in the cache.
    n = tuple(n)

    if n in cache:
        return cache[n]

    if len(n) == 1:
        result = 0
    else:
        result = sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                              for i in range(1, len(n)))

    cache[n] = result
    return result

Now, we have the cache values for all the tuples including the selected ones.

Using this, we can print the selected tuples as shown below:

selectedList = []
def printSelected (n, low):

    if len(n) == 1:
        # No need to print because it's 
        # already printed at previous recursion level.
        return

    minVal = math.Inf
    minTupleLeft = ()
    minTupleRight = ()
    splitI = 0

    for i in range(1, len(n)):
        tuple1ToI = tuple (n[:i])
        tupleiToN = tuple (n[i:])

        if (cache[tuple1ToI] + cache[tupleiToN]) < minVal:
            minVal = cache[tuple1ToI] + cache[tupleiToN]
            minTupleLeft = tuple1ToI
            minTupleRight = tupleiToN
            splitI = low + i


    print minTupleLeft, minTupleRight, minVal
    print splitI   # OP just wants the split index 'i'.
    selectedList.append(splitI) # or add to the list as requested by OP

    printSelected (list(minTupleLeft), low)
    printSelected (list(minTupleRight), splitI)

You call the above method like shown below:

printSelected (n, 0)

Thank you, but it doesn't precisely do what I wanted. The problem is with line: print n[ splitI ] I wanted the position of the cut, not the element of the cut. So I tried to change it to: print n.index( n[splitI] ) but the problem is, that it is not with relation to the original list, because as the function calls itself recursively, the original list splits and we have no information about it anymore. So for input [ 7,6,5,4,3,2,1 ] The output could be for example: [2, 1, 4, 3, 5, 6] But I can only get: [ 2,1,2,1,1,1 ] It works correctly but it doesn't do what I want. Thank you
Ok. I can fix that part. I was not clear about what you wanted. I will updated and inform you.
Thank you, but please note that the input can contain more than one unique number, so the input can also be for example [ 1,4,14,12,3,4,5,3 ].
I have updated the answer. Now, it keeps track of the index. Update me once you try this. I am appending the index to the selectedList.

Collectives™ on Stack Overflow

More on dynamic programming

1 Answer 1

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Linked

Related