Select 个字典中的值，条件是它们的键符合模式

Question

给定一个像

这样的字典

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

我想编写一个函数，随机 selects 字典中的值，以便它们的键一起匹配由输入参数定义的模式。

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

所以，match_pattern(dic, 4, 'AB') 会随机 return 结果像

['a'、'f'、'l'] 或

['f'、'k'、'd'] 或

['d', 'd', 'a', 'c'] ...

它们符合模式 'ABABABAB'。

备注：

抱歉有些不清楚。

实际的字典很大，对于可以输入的参数会有限制，所以会有足够的值select。

因为key的长度不同，所以returned列表的长度也可能不同。您可以在 returned 列表中包含 3 或 4 或其他数量的项目。

select离子应该按顺序进行。对于模式 'AB' * 4，键以 'AB' 开头的值（'AB'、'ABA' 等）可以被 selected。只有在确定第一个值后，下一个值才会 selected 以适应剩余模式。例如，如果第一个 selected 项目是 'AB'，下一个将是 'AB'，或 'ABA'，而如果第一个 selected 项目是 'ABA'，下一个将是 'BA'，或 'BAB'。我猜 select 倒序是一样的，但它必须是顺序的。

Answer 1

一种可能的解决方案是使用某些 path-search 算法来查找“路径”（在本例中为最短模式 - 但它也可以随机化）。在这个例子中我使用 A*Star:

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']

...

Select 个字典中的值，条件是它们的键符合模式

Select values from a dictionary on the condition that their keys fit into a pattern

python

dictionary

key-value