Searching for uniqness in a list of data

Alexander Schmolck a.schmolck at
Wed Mar 1 19:02:15 CET 2006

Alexander Schmolck <a.schmolck at> writes:

> The easiest way to do this is to have a nested dictionary of prefixes: for
> each prefix as key add a nested dictionary of the rest of the split as value
> or an empty dict if the split is empty. Accessing the dict with an userinput
> will give you all the possible next choices.

Oops I was reading this too hastily -- forgot to compact and take care of sep.
You might also want to google 'trie', BTW.

(again, not really tested)

def addSplit(d, split):
    if len(split):
        if split[0] not in d:
            d[split[0]] = addSplit({}, split[1:])
            addSplit(d[split[0]], split[1:])
    return d
def compactify(choices, parentKey='', sep=''):
    if len(choices) == 1:
        return compactify(choices.values()[0],
                          parentKey+sep+choices.keys()[0], sep)
        for key in choices.keys():
            newKey, newValue = compactify(choices[key], key, sep)
            if newKey != key: del choices[key]
            choices[newKey] = newValue
        return (parentKey, choices)
def queryUser(chosen, choices, sep=''):
    next = raw_input('So far: %s\nNow type one of %s: ' %
    return chosen+sep+next, choices[next]
choices = compactify(reduce(addSplit,(s.split('_') for s in wordList),  {}),
chosen = ""

while choices:
    chosen, choices = queryUser(chosen, choices, '_')
print "You chose:", chosen

More information about the Python-list mailing list