根据键符合模式的条件从字典中选择值

Question

给定一个像

这样的字典

dic = {
'AB': ['a', 'b', 'c', 'd'],
'ABA': ['e', 'f', 'g'],
'BA': ['h', 'i', 'j'],
'BAB': ['k', 'l'], ...

}

我想写一个函数，从字典中随机选择值，使它们的键合起来匹配输入参数定义的模式。

def match_pattern(source, time, feature):
pattern = feature * time
...

因此，match_pattern(dic, 4, 'AB')将随机返回类似

的结果['a'， 'f'， 'l']，或

['f'， 'k'， 'd']，或

['d'， 'd'， 'a'， 'c']…

它们符合'ABABABAB'的模式。

指出:

很抱歉我讲得不清楚。

实际的字典非常大，并且可以作为参数输入的内容将受到限制，因此将有足够的值可供选择。

因为键的长度不同，所以返回的列表的长度也可能不同。您可以在返回的列表中有3个或4个或其他数量的项目。

选择应该依次完成。对于模式'AB' * 4，可以选择键以'AB'开头的值('AB'， 'ABA'等)。只有在确定了第一个值之后，才会选择下一个值以适应其余模式。例如，如果第一个选择的项目是"AB"，那么下一个将是"AB"或"ABA"，而如果第一个选择的项目是"ABA"，那么下一个将是"BA"或"BAB"。我猜倒序选择是一样的，但它必须是连续的。

Answer 1

一个可能的解决方案是使用一些路径搜索算法来查找" path"(在这种情况下是最短的模式-但也可以随机化)。在这个例子中，我使用A* *:

import random
from heapq import heappop, heappush

def valid_moves(s):
for k in dic:
if pattern.startswith("".join(s) + k):
yield s + tuple([k])

def distance(s):
return len(pattern) - len("".join(s))

def always(value):
return lambda *args: value

def a_star(start, moves_func, h_func, cost_func=always(1)):
"""
Find a shortest sequence of states from start to a goal state
(a state s with h_func(s) == 0).
"""
frontier = [
(h_func(start), start)
]  # A priority queue, ordered by path length, f = g + h
previous = {
start: None
}  # start state has no previous state; other states will
path_cost = {start: 0}  # The cost of the best path to a state.
Path = lambda s: ([] if (s is None) else Path(previous[s]) + [s])
while frontier:
(f, s) = heappop(frontier)
if h_func(s) == 0:
return Path(s)
for s2 in moves_func(s):
g = path_cost[s] + cost_func(s, s2)
if s2 not in path_cost or g < path_cost[s2]:
heappush(frontier, (g + h_func(s2), s2))
path_cost[s2] = g
previous[s2] = s

dic = {
"AB": ["a", "b", "c", "d"],
"ABA": ["e", "f", "g"],
"BA": ["h", "i", "j"],
"BAB": ["k", "l"],
}
pattern = "AB" * 4
path = a_star(tuple(), valid_moves, distance)
final_pattern = path[-1]
out = [random.choice(dic[key]) for key in final_pattern]
print(final_pattern)
print(out)

打印(例如):

('ABA', 'BAB', 'AB')
['g', 'l', 'b']

---

如果你不想要最短的模式而是随机的，你可以改变valid_moves()和distance()函数，例如:

def valid_moves(s):
valid_patterns = []
for k in dic:
if pattern.startswith("".join(s) + k):
valid_patterns.append(s + tuple([k]))
random.shuffle(valid_patterns)
yield from valid_patterns

def distance(s):
return (len(pattern) - len("".join(s))) * random.randint(1, 100)

输出如下:

('AB', 'AB', 'AB', 'AB')
['c', 'b', 'a', 'b']
# OR
('AB', 'ABA', 'BAB')
['c', 'f', 'l']
...