遞歸自動換行算法

我正在研究具有三個部分的算法。第一種是遞歸方法，用最小的懲罰將文字包裝到特定的長度。第二種是遞歸方法的動態實現的算法。最後一個是這個問題的貪婪算法。我已經編寫了貪婪的代碼，但我在遞歸解決方案上苦苦掙扎。我不太清楚我遇到了遞歸方法的問題，但我知道它應該與Knuth-Plass算法類似。遞歸算法應該具有階乘運行時間，並且更多地用於幫助動態解決方案。如果任何人有一個Knuth-Plass實現的鏈接，或者可以在我的代碼中發現巨大的東西，任何幫助將不勝感激。遞歸自動換行算法

遞歸算法：

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 = recursive(temp2, size); 
       } 
      } 
     } 
    } 
    return input; 
}

的totalPenalty（）和blankChars返回在每一行的結束罰的量。

編輯：我還沒有看到任何即時解決方案。任何幫助，將不勝感激。

來源

2011-03-06 Zach

爲什麼你明確希望它是遞歸的？如果可以避免，遞歸是無效的編程。您最終可能會用完堆棧空間。 – 2011-03-06 23:03:54

這是讓我到一個動態編程解決方案。基本上我試圖去遞歸（糟糕的大O，但有助於轉換爲動態）>動態（更快，始終正確）>貪婪（並不總是會是正確的）。如果這是有道理的。 – Zach 2011-03-06 23:15:44

@Chris Dennett：說這樣的遞歸效率低下會更精確一些，因爲：a）它是Java b）沒有任何可以消除的尾部調用。然而，即使在這樣的條件下，如果我們可以保證輸入相當小，遞歸可以幫助我們更清楚地表達算法。 – hoha 2011-03-06 23:25:21

看起來像Java，在Java中沒有隱式的複製構造函數。

ArrayList<String> temp1 = input; < - 這將不創建具有相同內容的另一個對象，而是同一個對象的引用。

您需要更改行4和5：

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

我沒有看過任何其他錯誤，所以嘗試了這一點，如果您有任何更多的問題，更新的問題。

關於Knuth-Pass中斷算法;你可以在http://oedipus.sourceforge.net/texlib/找到一個Python實現。我沒有仔細看過它，但描述似乎是你正在尋找的。

來源

2011-03-06 23:00:12

感謝您的快速響應。似乎上述問題沒有解決。我認爲這個問題與我的邏輯有關。該鏈接並沒有那麼有用，因爲沒有實際的實現，只是框架工作。我不是在尋找一個確切的Knuth-Plass實現，但是在進行研究時，我發現Knuth-Plass算法與我試圖實現的最接近。 – Zach 2011-03-06 23:11:08

那裏肯定有一個實現。下載鏈接位於底部。 – 2011-03-07 01:54:20

遞歸自動換行算法

回答

相關問題