Given a dictionary like

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

I would like to write a function that randomly selects the values from the dictionary so that their keys together match a pattern that is defined by input arguments.

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

so, match_pattern(dic, 4, 'AB') will randomly return results like

['a', 'f', 'l'], or

['f', 'k', 'd'], or

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

They fit into the pattern 'ABABABAB'.

Notes:

Sorry for some unclearness.

The actual dictionary is very large, and there will be restrictions on what can be input as the arguments, so there will be enough values to select.

Because the lengths of the keys are different, so the length of the returned list may also be different. You can have 3 or 4 or other numbers of items in the returned list.

The selection should be done sequentially. For the pattern 'AB' * 4, values whose keys start with 'AB' ('AB', 'ABA', etc.) can be selected. Only after the first value is determined, the next value will be selected to fit in the rest pattern. For example, if the first selected item is 'AB', the next will be 'AB', or 'ABA', while if the first selected item is 'ABA', the next will be 'BA', or 'BAB'. I guess selecting in reverse order is the same, but it has to be sequential.

CodePudding user response：

One possible solution is to use some path-search algorithm to find "path" (in this case shortest pattern - but also it can be randomized). In this example I use 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)

Prints (for example):

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

If you don't want shortest pattern but random, you can change valid_moves() and distance() functions, for example:

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)

This outputs for example:

('AB', 'AB', 'AB', 'AB')
['c', 'b', 'a', 'b']

# OR

('AB', 'ABA', 'BAB')
['c', 'f', 'l']

...

CodePudding user response：

You start with taking the keys of the dict:

dic_keys = dic.keys()

Then you create a list with all possible keys which contains the feature = pattern

options_list = [key for key in dic_keys if key.startswith(feature)]

you get one of the selected keys

random_key = random.choice(options_list)

then you get a char out of the list

res = random.choice(dic[random_key])

All that is left to do now is to go through it with a loop and change feature based on the selected key, you can do that by comparing the selected key to the pattern