益智遊戲算法

我正在研究一款遊戲，並且我正在努力獲得一些通用功能。假設我們有一個短語像"puzzle game using group of words"所以我生成這個可能的子集：益智遊戲算法

"puzzle"，"game"，"using"，"group"，"of"，"words"，並添加更多的樂趣我還加兩個連續的字組（現在組> 2話是不允許的）："puzzle game"，"game using"，"using group"，"group of"，"of words"

所以，現在的主要想法是ALL形成從這些子集構成原判可能的組合。請注意，在這種情況下，子集應該是一個分區。

例子：

"puzzle game", "using", "group", "of words" 
"puzzle", "game", "using group", "of", "words"

...

不允許：

"puzzle game", "game using", .. (it's not a partition as "game" is repeated)

是否有任何已知的算法生成所有可能的組合？我認爲這可能會花費很長時間的短語非常耗時，所以有沒有其他方法可以嘗試根據某些重量找到可能的最佳選項？

我不會假裝得到代碼（雖然那會很棒），但至少任何提示或想法在哪裏看將會非常感激！

來源

2011-08-08 Dan

是''拼圖遊戲使用「，」組合詞「'合法的解決方案？或者它必須是每個分區1或2個字？ – amit

嗨阿米，答案是至少目前沒有。使用更高級別的單詞（> 2）可以在未來添加，因此擁有通用解決方案將非常棒，儘管目前不需要。 – Dan

首先將您的字符串解析爲單詞，讓單詞列表爲S.創建一個空的結果列表（讓它爲L）可能的返回值。

使用遞歸解決方案：設置一個當前的解決方案（初始化爲空），並在每一步 - 添加可能的下一個字/雙。當你用完你的話時，'當前'將是一個分區，並將其添加到列表中。

僞代碼：

partitions(S,L) = partitions(S,L,{}) 

partitions(S,L,current): 
    if S is empty: 
     L.add current 
    else: 
     first <- S.first 
     second <- S.second 
     partitions(S-{first}-{second},L,current+{first second}) 
     partitions(s-{first},L,current+{first})

EDIT：注：此解決方案假定只有1或2個字是每個分區是合法的。如果不是這種情況，而不是硬編碼的遞歸調用，它將S減少1/2個字，則必須迭代1，...，S.size（）的第一個單詞。

無（使用堆棧和列表的ADT）遞歸解決方案：

partitions(S): 
    L <- empty_result_list() 
    stack <- empty_stack() 
    stack.push(pair(S,{})) 
    while (stack is not empty): 
     current <- stack.pop() 
     S <- current.first 
     soFar <- current.second 
     if S is empty: 
      L.add(soFar) 
     else: 
      stack.push(pair(S-{S.first}-{S.second},soFar+{S.first S.second}) 
      stack.push(pair(S-{S.first},soFar+{S.first}) 
    return L

來源

2011-08-08 14:22:20 amit

謝謝阿米特，非常感謝。說實話，我寧願遠離遞歸，因爲可能的堆棧溢出（我打算在堆棧大小可能有問題的平臺上執行） – Dan

@Dan：任何遞歸都可以轉換爲堆棧+循環。一個動態分配的堆棧[而不是調用堆棧]是一個很好的解決方案嗎？ – amit

當然，任何可以在堆上分配的ADT都可以。 – Dan

看看Stars and bars。

如果你有N字符串（又名星）

******

現在把它們之間N-1吧。只有一種方法可以做到這一點

*|*|*|*|*|*

這是一種可能性。現在他們之間放置N-2酒吧。

*|*|*|*|** 
*|*|*|**|* 
*|*|**|*|* 
*|**|*|*|* 
**|*|*|*|*

等，這些定義你的分區，如果你與你的字符串替換的星星。要生成所有可能的方式來將x條形圖顯示在N之間，您只需要一種生成組合的方法。

來源

2011-08-08 14:22:57 tskuzzy

放置N-3酒吧給出了一個可能的解決方案：*** | * | * | * [這是無效的，最大'星'之間酒吧是2]。另外，我不認爲OP需要的數量，但實際的可能性。 – amit

OP要求所有組合，而不是所有組合，其中條間的最大星數爲2.您可以使用此方法非常輕鬆地生成實際組合。我在答案的底部提到了這一點。 – tskuzzy

謝謝tskuzzy。對不起，不清楚這一點，但最初的想法是使用大小不超過2的子集。無論如何，我認爲你的想法可以被限制使這項工作。謝謝你的參考，看起來很整潔。 – Dan

非常簡單，如果你認爲每個單詞之間存在小的不可見的「障礙」。

例如，「使用詞組的拼圖遊戲」成爲「拼圖遊戲使用的詞組」。如果你有N個詞，你有N-1個障礙。

現在，對於每個「障礙」，您可以選擇障礙是上升還是下降。如果它起作用，它就像一個分離器。如果不是，則認爲它不存在。

實例：

「益智|遊戲|使用|話|的基團」 - 「的基團」，「字」
「益智遊戲使用|的| |組詞」 - >「益智遊戲使用」，「集團」，「中」，「字」

對於每一個「屏障」，你可以決定它是否是向上或向下，所以只有2個選擇。你有N-1 「的障礙」，則總共有2 ^（N-1）個這樣的分區

編輯：Argl =/

僅限於一個或兩個詞的組？

來源

2011-08-08 14:28:01 Fezvez

我認爲OP需要實際的可能性。也障礙之間的最大詞是2. – amit

是的非斯維茲，這些團體最多隻能有兩個詞。對不起，我的問題沒有更明確。 – Dan

益智遊戲算法

回答

相關問題