Creating custom dictionary from two lists

Question

I have following two python lists.

prob_tokens = ['119', '120', '123', '1234', '12345']

complete_tokens = ['112', '120', '121', '123', '1233', '1234', '1235', '12345']

min_len_sec_list = 3
max_len_sec_list = 5

I want to create a dictionary with elements from first list as keys and with following constraints :

1. if key does not exists in second list then the value will be False.
2. if key exists in second list with variants then the value will be False.

Eg:

(i) while checking 123, if 1234, 12345 exists (123*) in second list then value of 123 will be False.

(ii). Similarly while checking 1234, if 12345 exists (1234*) then value will be False.

Here * will be [0-9]{(max_len-len_token)}

3. if key exists in second list with no variants then value will be True.

OUTPUT :

final_token_dict

{'119': False,'120': True, '123': False, '1234': False, '12345': True}

Can I get any suggestions on how to achieve this? Thanks in advance!!!

Answer 1

You can use a custom function with a dictionary comprehension:

prob_tokens = ['119', '120', '123', '1234', '12345']
complete_tokens = ['112', '120', '121', '123', '1233', '1234', '1235', '12345']

def mapper(val, ref_list):
    if any(x.startswith(val) and (len(x) > len(val)) for x in ref_list):
        return False
    if val in ref_list:
        return True
    return False

res = {i: mapper(i, complete_tokens) for i in prob_tokens}

print(res)

{'119': False, '120': True, '123': False, '1234': False, '12345': True}

If the number of characters criterion is important to you, you can adjust your logic accordingly using chained comparisons and an additional input:

def mapper(val, ref_list, max_len):
    if any(x.startswith(val) and (0 < (len(x) - len(val)) <= max_len) for x in ref_list):
        return False
    if val in ref_list:
        return True
    return False

min_len_sec_list = 3
max_len_sec_list = 5

add_lens = max_len_sec_list - min_len_sec_list

res = {i: mapper(i, complete_tokens, add_lens) for i in prob_tokens}

Answer 2

You can convert your list into a Trie, or Prefix Tree, structure, then check whether any of the keys is a prefix in that Trie. This will be faster than checking whether its a prefix of each element in the list individually. More specifically, if you have k elements in your prob_tokens list, and n elements in complete_tokens, then this will make only O(n+k), whereas checking each pair is O(n*k).¹

def make_trie(lst):
    trie = {}
    for key in lst:
        t = trie
        for c in key:
            t = t.setdefault(c, {})
    return trie

def check_trie(trie, key):
    for c in key:
        trie = trie.get(c, None)
        if trie is None: return False # not in trie
        if trie == {}: return True    # leaf in trie
    return False  # in trie, but not a leaf

prob_tokens = ['119', '120', '123', '1234', '12345']
complete_tokens = ['112', '120', '121', '123', '1233', '1234', '1235', '12345']

trie = make_trie(complete_tokens)
# {'1': {'1': {'2': {}}, '2': {'0': {}, '1': {}, '3': {'3': {}, '4': {'5': {}}, '5': {}}}}}
res = {key: check_trie(trie, key) for key in prob_tokens}
# {'119': False, '120': True, '123': False, '1234': False, '12345': True}

¹⁾ Actually, the average length of the keys also is a factor, but it is so in both approaches.

Answer 3

This might be another alternative

import re

prob_tokens = ['119', '120', '123', '1234', '12345']

complete_tokens = ['112', '120', '121', '123', '1233', '1234', '1235', '12345']

dictionary = dict()
for tok in prob_tokens:
    if tok not in complete_tokens or any([bool(re.compile(r'^%s\d+'%tok).search(tok2)) for tok2 in complete_tokens]):
        dictionary[tok] = False
    else:
        dictionary[tok] = True

print(dictionary)`

Answer 4

You can use any:

a = ['119', '120', '123', '1234', '12345']
b = ['112', '120', '121', '123', '1233', '1234', '1235', '12345']
new_d = {c:c in b and not any(i.startswith(c) and len(c) < len(i) for i in b) for c in a} 

Output:

{'120': True, '1234': False, '119': False, '123': False, '12345': True}