字符串分組

Question

我有一個可能的字符串列表組列表。每個字符串由幾個字組成，它們是字符串元素。我想根據這些元素對字符串進行分組。

每個組都基於一個常用單詞：組中的所有字符串必須包含該單詞 - 儘管我不要求包含該單詞的所有字符串都在同一組中。與N字符可以在任何N不同的組。每個字符串可能只在一個組中。每個組必須至少有兩個字符串。

目標：形成組以最大化組中的字符串數量（最小化「孤立」字符串）。

舉例來說，如果我有一個字符串以下列表：

cycle cost 
pump cost 
cycle analysis 
cost example 

我會每個字符串作爲潛在羣組的所有可能的話。我現在想把這些字符串分組，以便儘可能多地進入一個組。

我嘗試了一種天真的方法，首先在組中使用最多的字符串，在本例中它將是cost，但是這會在沒有組的情況下保留cycle analysis。

我在這個例子中尋找的結果是：

cycle: cycle cost, cycle analysis 
cost: pump cost, cost example 

是否存在一種算法，這種問題了嗎？任何關於採取方法的指針都會有所幫助。

Answer 1

它看起來像@ m69有很好的領先優勢。您的問題有幾個修改：

• 刪除所有大小爲1;
• 當一組是（暫定）加入到該溶液中，所有元素的集合 必須從所有剩餘的份數
  • 去除...並與少於兩個元件的任何組得到去除。

不幸的是，這是NP難，在最好。如果應用程序的輸入不是很大，我會使用自由回溯的蠻力啓發式。

初始化：

• 甲可行組是一個具有至少2個元素。
• 處理您的列表。
  • 將所有可行的集合到一個列表小號。
  • 將所有元素放入宇宙中，U。

過程：

1. 從小號挑選一組P;將其添加到解決方案列表中。
2. 從每個剩餘在小號設定刪除P的所有元素。
3. 從小號刪除所有非活套。
4. 如果小號是空
   • 然後如果ü所有元素中小號，
     • 存在然後停止並報告解決方案。
     • 否則返回以前的調用級別
   • 否則[小號不是空] 岑參在這個過程中與新小號
5. 如果遞歸成功報道，
   • 然後返回上一個呼叫列弗埃爾。
   • 否則回去從小號

第1步，並選擇下一組您可以通過套明智排序在小號獲得這個一定優勢。我推薦一個貪婪的算法，其值根據的合意其元素集合S。例如，出現在中的元素只有一個集合會將該集合推到列表的頂部。

這是否讓你開始？