將按字母順序排列的列表拆分爲相等塊

我的任務是將名稱目錄拆分爲四個（近似）相等的塊。該目錄實際上是一個已經alphebatised的電話簿。解決方案必須是通用的，並且適用於任何目錄，而不僅僅是一個特定目錄。如果它幫助目錄是一個字符串數組。將按字母順序排列的列表拆分爲相等塊

例如四大塊爲一個目錄可能是：

A-E, F-L, M-S and T-Z

而另一個可能是

A-B, C-D, E-F and G-Z

我已經考慮剛剛分裂4目錄的大小，然後計數直到達到這個數字，並注意到入口開始的字母，但這不是特別優雅。

我的意思是：將目錄設爲100個條目。我可以將它除以4得到25（每個塊應該有多少條目）。通過條目到25，然後採取該條目應該給我在第一個塊的最後一項。但是，如果字母表中每個字母的條目數量差別很大，則這不起作用。 A-J都可以有一個條目，K可以有32個條目，這會使我的過程無用。

有僞代碼而不是特定的C實現將是有幫助的，但真正在正確的方向上的一個點將是一個很大的幫助。

來源

2015-06-30 mforrest

這不是一個C-相關的問題，而是你所要求的我們給你的算法？ – Eregrith

@Eregrith我會在C中這樣做，但我提到了僞代碼，因爲我認爲它對我來說實際上知道發生了什麼會更有用，而不僅僅是複製和破解別人的實現。 – mforrest

該目錄已經排序。這樣你就可以輕鬆地將它們分爲四個如果考慮額外的字母作爲鍵，如（A-AE，AF-AZ等）的基本思想是

Store中的一些數據結構詞典（說陣列）在排序順序
現在將數組的長度除以4，並分別製作四個索引。
在每個索引處檢查帶有上一個索引詞的字母。
- 如果第一個索引詞是「Abandon」並且第二個索引詞是「Ascension」那麼第一個鍵將是「Ab」，第二個索引詞將是「As」。
- 因此，範圍內的所有單詞（Ab-As）將出現在按鍵之間。
- 如果前兩個字母與你所期望的字典部分分佈相同，那麼請爲該密鑰另外寫一個字母。（如阿壩 - 阿布斯）

來源

2015-06-30 10:45:33

感謝您的回答，我試圖通過堅持單個字符範圍儘可能簡化爲最終用戶，但如果我不能得到這個工作，我會看看使用您的方法肯定：） – mforrest

這是三個變量的優化問題;四大塊之間的界限。如果我們表示邊界X，ÿ，ž與塊半開區間A - X，XY，YZ，ž - Z那麼只會進一步約束是x < = y < = z，給出3276個可能性爲x，y，z這就是無足輕重的搜索。

然後，您只需要一種方法來評估一種配置比另一種更好或更差;我建議使用平方和的誤差例如對於塊長度20, 26, 32, 24，平方誤差爲(20-25)^2 + (26-25)^2 + (32-25)^2 + (24-25)^2 = 76。

把這個放在一起，你可以使用嵌套循環寫窮舉搜索：

best, best_error = Nothing, +Inf 
for A <= x <= Z: 
    for x <= y <= Z: 
     for y <= z <= Z: 
      error = (sum(lengths[i] for A < i <= x) - 25)^2 
        + (sum(lengths[i] for x < i <= y) - 25)^2 
        + (sum(lengths[i] for y < i <= z) - 25)^2 
        + (sum(lengths[i] for z < i <= Z) - 25)^2 
      if error < best_error: 
       best, best_error = (x, y, z), error

來源

2015-06-30 10:46:53 ecatmur

我主要了解你的建議，看起來它可能是一個好方法。但是，我在你的實現中對for循環有些困惑。如果你能更詳細地解釋它們，我將非常感激。 – mforrest

@mforrest很好，這是一個詳盡的搜索，所以* x *的範圍可以從'A'到'Z'的任何地方。假設，* y *可以從* x *到'Z'和* z *中的任意位置，從* y *到'Z'的任意位置。嵌套for循環是它的自然表示。 – ecatmur

好的，這是有道理的。我來自Java背景，我正在努力按原樣實現您的解決方案。這是僞代碼還是工作實現？對於A <= X <= Z'和'sum（長度[i]爲A mforrest

將按字母順序排列的列表拆分爲相等塊

回答

相關問題