可以給予骰子給定的字符串？

我想看看給定的骰子是否可以彌補給定的字符串。以這種特殊情況爲例，如果我們給出'IAM'和可以給予骰子給定的字符串？

given_set= [['I', 'B', 'A'], ['J', 'I', 'P',], ['M', 'R', 'S'], ['T', 'U', 'V']]

我的代碼返回False。但是如果我們從第二個列表中獲取'I'並從第一個列表中獲取'A'，我們仍然可以創建字符串。我想我除了這個之外還涵蓋了大部分其他案例。

任何人都可以指導我如何解決這個特殊情況？

這裏是我的代碼：

def possible(string, given_set): 
    a = False 

    if len(string) > len(given_set): 
     return False 

    if string == '': 
     return True 

    for i in string: 

     for index, value in enumerate(given_set): 

      if i in value: 
       a = possible(string[1:],given_set[0:index] + given_set[index+1:]) 
       return a 
      else: 
       return False

來源

2015-08-26 277roshan

如果你是將它作爲一個遞歸實現，刪除'我在字符串'，只能在字符串的第一個字符 – fferri

它看起來像問題是你在第一集中找到「我」，然後試圖找到「AM」在最後的三組中，這是錯誤的，它會返回到變量'a'中，並返回False。你需要繼續前進，因爲在這種情況下，你需要從第二組中選擇「我」。只有返回True才返回。 –

@JordanTrudgett我跟着你說的話。我在答案中添加了我的解決方案。你認爲這樣可以嗎？ – 277roshan

如果你看看來電正在取得：

possible('IAM',[['I', 'B', 'A'], ['J', 'I', 'P'], ['M', 'R', 'S'], ['T', 'U', 'V']]) 
possible('AM',[['J', 'I', 'P'], ['M', 'R', 'S'], ['T', 'U', 'V']])

你會看到，它返回False，因爲它會使用含有一套既'I'和'A' ，因此在第二次迭代中不可能找到包含'A'的集合。

把它變成一臺發電機，因此可以探索一切可能的解決方案（即原路返回），並且它會工作：

def possible(string, given_set): 
    if len(string) > len(given_set): 
     return 

    if string == '': 
     yield True 
     return 

    for index, value in enumerate(given_set): 
     if string[0] in value: 
      yield from possible(string[1:], given_set[0:index] + given_set[index+1:])

你會使用any()檢查是否有可能使一個字符串與骰子：

>>> print(any(possible('IAM',given_set))) 
True 

>>> print(any(possible('IAB',given_set))) 
False

注意：yield from ...需要Python 3.4+。在之前的版本中，您可以編寫for x in ...: yield x

來源

2015-08-26 01:58:51 fferri

您需要確保您不會太快地返回False，因爲您仍然可以嘗試其他可能性。在這裏，你會看到我們只返回a，如果它是True - 因爲一旦你找到了解決方案，沒有必要繼續尋找，你可以直接返回True。 True將通過遞歸調用返回。

你也有return False如果i不在value - 這意味着你放棄，如果它不在你看第一集，這也是錯誤的。我搬到了環之外的迴歸，因爲你只知道這是不可能的，一旦你看了所有的集：

def possible(string, given_set): 
    a = False 

    if len(string) > len(given_set): 
     return False 

    if string == '': 
     return True 

    for i in string: 

     for index, value in enumerate(given_set): 
      if i in value: 
       a = possible(string[1:],given_set[0:index] + given_set[index+1:]) 
       if a: 
        return a 
     return False

現在我相信它的工作原理：

given_set= [['I', 'B', 'A'], ['J', 'I', 'P',], ['M', 'R', 'S'], ['T', 'U', 'V']] 

# possible cases 
print possible("IJM", given_set) # True 
print possible("IJT", given_set) # True 
print possible("IIM", given_set) # True 
print possible("JMT", given_set) # True 
print possible("IMA", given_set) # True 
print possible("VIB", given_set) # True 
print possible("VPA", given_set) # True 

# impossible cases 
print possible("ZZZ", given_set) # False 
print possible("ABC", given_set) # False 
print possible("AIJ", given_set) # False 
print possible("IJB", given_set) # False 
print possible("VPT", given_set) # False 
print possible("JRP", given_set) # False 
print possible("RAS", given_set) # False

來源

2015-08-26 20:22:28

可以給予骰子給定的字符串？

回答

相關問題