1

假设我有一个像这样的元组列表：

list_of_tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

每个元组中的第二个值始终是R、B或G。我想创建一个函数validate，检查是否可以使用每个元组第一个位置的字母构造某个单词，但前提是该元组的节位置中的字母不重复。

例如，可以构造单词：

ACEwith (A, R), (C, G)and(E, B)因为每个元组中的第二个值对应于RGBwhich 不连续重复任何字母。

ACEDwith(A, R), (C, G), (E, B), and ('D', 'B')是不可能的，因为这对应RGBB于其中有一个连续的 B。

请注意，有时同一个字母的第二个位置可能有不同的字母，例如：

('A', 'R') and ('A', 'G'). ACE如果您选择了第一个元组，而不是第二个，您只能拼写，否则G's 会重复。

另请注意，GBRBG即使第二个位置字母“重复”它们不会连续重复，也可能出现类似的组合。

所以我想要一个可以通过以下方式验证单词的函数：

def validate(submitted_word, list_of_tuples)

一种可能性是构造该集合可能的序列的每个可能组合以及将由第二个序列中的字母产生的相应序列，过滤掉那些是有效单词的，然后过滤掉那些具有连续重复字母，但我担心考虑到元组列表可以变得有多大，这将是低效的。

4

4 回答 4

1

这是一个图遍历问题。您可用的节点是（字母，颜色）的元组；您的边缘是给定单词中的字母转换。

对于每个输入，“简单地”为该单词构建图形。给定 ACE，你有

Layer 1 -- transition START to any A
START -> AR
START -> AG

Layer 2 -- transition A to C
AR -> CG
not allowed: AG -> CG

Layer 3 -- transition C to E
CG -> EB

Layer 4 -- transition any E to GOAL
EB -> GOAL

现在您只需应用图遍历功能（任何自尊图包都有）来解决您的拼写问题。

于 2020-09-24T17:03:43.750 回答
1

请参阅下面的独立解决方案和测试：

list_of_tuples = [
    ('A', 'R'),
    ('B', 'R'),
    ('C', 'G'),
    ('D', 'G'),
    ('E', 'B'),
    ('D', 'B'),
    ('R', 'B'),
    ('F', 'R'),
    ('V', 'R'),
    ('A', 'G')
]

def validate(submitted_word, list_of_tuples):
    # Check length of word
    if len(submitted_word) == 0:
        raise ValueError("len(submitted_word) must be > 0")

    # Initialise options for first character
    options = [[tup for tup in list_of_tuples if tup[0] == submitted_word[0]]]
    # Iterate through the rest of the characters
    for char in submitted_word[1:]:
        # Initialise set of characters in second position of previous tuple
        forbidden_chars = set(tup[1] for tup in options[-1])
        # Add valid options for the next character
        options.append([
            tup
            for tup in list_of_tuples
            if (tup[0] == char) and len(forbidden_chars - set(tup[1])) > 0
        ])
        # If there are no options, then submitted_word does not validate
        if len(options[-1]) == 0:
            print(options)
            return False
    
    print(options)
    return True

print(validate("ACE", list_of_tuples))
print()
print(validate("ACED", list_of_tuples))
print()
print(validate("ACFFFED", list_of_tuples))

控制台输出：

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('E', 'B')]]
True

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('E', 'B')], [('D', 'G')]]        
True

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('F', 'R')], []]
False
于 2020-09-24T17:16:49.603 回答
1

我们可以使用回溯，其中状态是每个字母使用的 R、G、B 的计数，以及在我们构造单词时选择的先前“RGB”。

Python代码（未记忆）：

def f(i, word, prev, state):
  if i == len(word):
    return True

  letter = word[i]

  for second in ["R", "G", "B"]:
    if state[letter][second] and prev != second:
      state[letter][second] -= 1
      is_valid = f(i + 1, word, second, state)
      state[letter][second] += 1
      if is_valid:
        return True

  return False

def get_counts(tuples):
  result = {}
  for letter, rgb in tuples:
    if letter in result:
      result[letter][rgb] += 1
    else:
      result[letter] = {"R": 0, "G": 0, "B": 0}
      result[letter][rgb] = 1
  return result

tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

counts = get_counts(tuples)

print f(0, "ACE", "", counts) # True
print f(0, "ACED", "", counts) # True
print f(0, "BF", "", counts) # False
于 2020-09-24T17:17:05.520 回答
0

我建立了以下。首先，我们创建一个函数来比较 2 个列表并检查它们是否至少有一个不同的元素。其次，我们为单词中所有连续字母对的关联列表运行此函数。我认为单词的所有字母都表示在 list_of_tuples 中。否则将需要多几行来检查是否存在（在这种情况下让我知道，以便我添加它们）。

def validate(word, list_of_tuples):
    def rgb(l1,l2):
        return len(set(l1).difference(set(l2)))>0

l=[[i, [k[1] for k in list_of_tuples if k[0]==i]] for i in word]

for i in range(len(l)-1):
    if not rgb(l[i][1], l[i+1][1]):
        return False
return True
于 2020-09-24T17:12:46.480 回答