Recursive Word Wrap Algorithm

I am working on an algorithm that has three parts. The first is a recursive method that will wrap words to a specific length with the least penalty. The second is an algorithm that is a Dynamic implementation of the recursive method. The last one is a Greedy Algorithm of the problem. I already have the Greedy one coded but I'm struggling on the Recursive solution. I'm not quite sure where exactly I'm running into an issue with my Recursive method but I know it should be something similar to the Knuth-Plass Algorithm. The recursive algorithm is supposed to have a factorial running time, and used more to help with the dynamic solution. If anyone has a link to a Knuth-Plass implementation or can spot something huge in my code, any help would be appreciated.

Recursive Algorithm:

public static ArrayList<String> recursive(ArrayList<String> input, int size) {
    if(input.size() <= 1)
        return input;
    ArrayList<String> temp1 = input;
    ArrayList<String> temp2 = input;
    for(int i = 0; i < input.size(); i++) {
        if(input.size() - 1 >= size)
            break;
        else {
            for(int j = 0; j < input.size(); j++) {
                temp1.set(j, temp1.get(j) + " " + temp1.get(j + 1));
                temp1.remove(j + 1);
                if(totalPenalty(blankChars(temp1, size)) < totalPenalty(blankChars(temp2, size))) {
                    input = recursive(temp1, size);
                } else {
                    input 开发者_如何学JAVA= recursive(temp2, size);
                }
            }
        }
    }
    return input;
}

The totalPenalty() and blankChars return the amount of penalty at the end of each line.

EDIT: I'm still not seeing any immediate solutions. Any help would be appreciated.

---

That looks like Java, and in Java there is no implicit copy-constructor.

ArrayList<String> temp1 = input; <-- this will not create another object with the same content, but instead a reference to the same object.

You need to change line 4 and 5 to:

ArrayList<String> temp1 = new ArrayList<String>(input);
ArrayList<String> temp2 = new ArrayList<String>(input);

I haven't looked for any other mistakes, so try this out and update the question if you have any more problems.

About the Knuth-Pass breaking algorithm; You can find a Python implementation at http://oedipus.sourceforge.net/texlib/. I haven't looked closer at it, but the description seems to be what you are looking for.

---

I hope the following code runs. Here I have added the cost for the last line as well. Though word processors use greedy algorithms most of the time and they neglect the cost of the last line. Let me know if this is clear to you.

import java.lang.Math;

public int RCS(int[] l , int n , int m , int index) {

    // first base condition - if index gets beyond the array 'l' , then return 0;
    if (index > n - 1) return 0;

    // second base condition - if index is the last word i.e there is only one word left in the
    // array to be inserted in the line then return the cost if added in that line.
    if (index == n - 1) return (m - l[n - 1]) * (m - l[n - 1]) * (m - l[n - 1]);

    // make a global cost variable to be returned
    int cost = Integer.MAX_VALUE;

    // Here , we try to select words from the array and apply RCS on the rest of the array.
    // From index to last element , we iteratvely select first , or first two and so on.
    for (int i = index ; i < n ; i++) {
        int current_space_sum = 0 ;
        // we add the length of the selected word. We have selected words in array from index to i.
        for (int k = index ; k <= i ; k++) {
            current_space_sum = current_space_sum + l[k] ;
        }
        // Adding the space between the words choses. If 2 words are chosen , there is one space and so on
        current_space_sum = current_space_sum + i - index;
        // If the length of the chosen words is greater than the line can accept , no need of looking beyond.
        if (current_space_sum > m) break;
        // Iteratively find the minimum cost
        cost =  Math.min(cost , (m - current_space_sum) * (m - current_space_sum) * (m - current_space_sum) + RCS(l , n , m , i + 1));
    }
    return cost;
}



public static void main(String[] args) {
    WordWrap w = new WordWrap();
    int[] l = {3, 2 , 2 , 5};
    int n = l.length;
    int m = 6;
    int result = w.RCS(l , n , m , 0);

    System.out.println(result);
}