生成不同长度的单词，给出n个字符

Question

我需要生成给定n个字符的Ki长度的所有可能单词，例如：

给予

LNDJOBEAWRL公司

做 熊

我想不出len 5这个词，但这就是我的想法

n = 11
k1 = 2
k2 = 4
k3 = 5 

所以基本上所有的单词长度都是2，4和5，但是没有重复使用字符。最好的办法是什么？你知道吗

---

我的字典结构如下所示：

{
    3: [{u'eit': u' "eit":0'}], 
    5: [{u'doosw': u' "woods": 4601, '}, {u'acenr': u' "caner": 0, '}, {u'acens': u' "canes": 0, '}, {u'acden': u' "caned": 0, '}, {u'aceln': u' "canel": 0,'}], 
    6: [{u'abeill': u' "alible": 0, '}, {u'cdeeit': u' "deciet":0,'}, {u'demoor': u' "mooder": 0, '}], 
    7: [{u'deiprss': u' "spiders": 0, '}, {u'deiprsy': u' "spidery": 0, '}, {u'cersttu': u' "scutter": 0, '}], 
    8: [{u'chiiilst': u' "chilitis": 0, '}, {u'agilnrtw': u' "trawling": 0, '}, {u'abdeemns': u' "beadsmen": 0, '}], 
    9: [{u'abeiilnns': u' "biennials": 0, '}, {u'bclooortu': u' "oblocutor": 0, '}, {u'aabfiinst': u' "fabianist": 0, '}, {u'acdeiituz': u' "diazeutic": 0, '}, {u'aabfiimns': u' "fabianism": 0, '}, {u'ehnoooppt': u' "optophone": 0, '}], 
    10: [{u'aiilnoprtt': u' "tripolitan": 0, '}, {u'eeilprrsty': u' "sperrylite": 0, '}, {u'gghhiilttt': u' "lighttight": 0, '}, {u'aeegilrruz': u' "regularize": 0, '}, {u'ellnprtuuy': u' "purulently": 0, '}], 
    11: [{u'cdgilnoostu': u' "outscolding": 0, '}], 
    12: [{u'ceeeilnostuy': u' "leucosyenite": 0, '}, {u'aacciloprsst': u' "sarcoplastic": 0, '}], 
    13: [{u'acdeimmoprrsu': u' "cardiospermum": 0, '}, {u'celnnooostuvy': u' "noncovetously": 0, '}], 
    14: [{u'adeejmnnoprrtu': u' "preadjournment": 0, '}]
}

我修改过的代码如下：

wlen = self.table[pos]
if pos == 0:
    # See if the letters remaining in the bag are a valid word
    key = ''.join(sorted(bag.elements()))

    for d in wlen:
        if key in d.keys():
            yield solution + [key]
else:
    pos -= 1
    for dic in wlen:
        print(len(dic))
        for key in dic.keys():

Answer 1

下面的代码使用递归生成器构建解决方案。为了存储目标字母，我们使用^{}，这就像一个允许重复项的集合。你知道吗

为了简化搜索，我们为所需的每个单词长度创建一个字典，将每个字典存储在一个名为all_words的字典中，单词长度作为关键字。每个子字典存储包含相同字母的单词列表，排序后的字母作为关键字，例如'aet': ['ate', 'eat', 'tea']。你知道吗

我使用标准的Unix'/usr/share/dict/words'word文件。如果使用不同格式的文件，可能需要修改将单词放入all_words的代码。你知道吗

solve函数从最小的字长开始搜索，一直搜索到最大的字长。如果包含最长单词的集合是最大的，那么这可能是最有效的顺序，因为最终的搜索是通过执行简单的dict查找来执行的，这非常快。以前的搜索必须测试该长度的子字典中的每个单词，寻找仍在目标包中的关键字。你知道吗

#!/usr/bin/env python3

''' Create anagrams from a string of target letters and a list of word lengths '''

from collections import Counter
from itertools import product

# The Unix word list
fname = '/usr/share/dict/words'

# The target letters to use
target = 'lndjobeawrl'

# Word lengths, in descending order
wordlengths = [5, 4, 2]

# A dict to hold dicts for each word length.
# The inner dicts store lists of words containing the same letters,
# with the sorted letters as the key, eg 'aet': ['ate', 'eat', 'tea']
all_words = {i: {} for i in wordlengths}

# A method that tests if a word only contains letters in target
valid = set(target).issuperset

print('Scanning', fname, 'for valid words...')
count = 0
with open(fname) as f:
    for word in f:
        word = word.rstrip()
        wlen = len(word)
        # Only add words of the correct length, with no punctuation.
        # Using word.islower() eliminates most abbreviations.
        if (wlen in wordlengths and word.islower()
        and word.isalpha() and valid(word)):
            sorted_word = ''.join(sorted(word))
            # Add this word to the list in all_words[wlen],
            # creating the list if it doesn't exist
            all_words[wlen].setdefault(sorted_word, []).append(word)
            count += 1

print(count, 'words found')
for k, v in all_words.items():
    print(k, len(v))
print('\nSolving...')

def solve(pos, bag, solution):
    wlen = wordlengths[pos]
    if pos == 0:
        # See if the letters remaining in the bag are a valid word
        key = ''.join(sorted(bag.elements()))
        if key in all_words[wlen]:
            yield solution + [key]
    else:
        pos -= 1
        for key in all_words[wlen].keys():
            # Test that all letters in key are in the bag
            newbag = bag.copy()
            newbag.subtract(key)
            if all(v >= 0 for v in newbag.values()):
                # Add this key to the current solution and 
                # recurse to find the next key
                yield from solve(pos, newbag, solution + [key])

# Find all lists of keys that produce valid combinations
for solution in solve(len(wordlengths) - 1, Counter(target), []):
    # Convert solutions to tuples of words
    t = [all_words[len(key)][key] for key in solution]
    for s in product(*t):
        print(s)

输出

Scanning /usr/share/dict/words for valid words...
300 words found
5 110
4 112
2 11

Solving...
('ad', 'jell', 'brown')
('do', 'jell', 'brawn')
('ow', 'jell', 'brand')
('re', 'jowl', 'bland')

---

FWIW，以下是

target = 'nobigword'
wordlengths = [4, 3, 2]

输出

Scanning /usr/share/dict/words for valid words...
83 words found
4 31
3 33
2 7

Solving...
('do', 'big', 'worn')
('do', 'bin', 'grow')
('do', 'nib', 'grow')
('do', 'bow', 'grin')
('do', 'bow', 'ring')
('do', 'gin', 'brow')
('do', 'now', 'brig')
('do', 'own', 'brig')
('do', 'won', 'brig')
('do', 'orb', 'wing')
('do', 'rob', 'wing')
('do', 'rib', 'gown')
('do', 'wig', 'born')
('go', 'bid', 'worn')
('go', 'bin', 'word')
('go', 'nib', 'word')
('go', 'bow', 'rind')
('go', 'din', 'brow')
('go', 'now', 'bird')
('go', 'own', 'bird')
('go', 'won', 'bird')
('go', 'orb', 'wind')
('go', 'rob', 'wind')
('go', 'rib', 'down')
('go', 'row', 'bind')
('id', 'bog', 'worn')
('id', 'gob', 'worn')
('id', 'orb', 'gown')
('id', 'rob', 'gown')
('id', 'row', 'bong')
('in', 'bog', 'word')
('in', 'gob', 'word')
('in', 'dog', 'brow')
('in', 'god', 'brow')
('no', 'bid', 'grow')
('on', 'bid', 'grow')
('no', 'big', 'word')
('on', 'big', 'word')
('no', 'bow', 'gird')
('no', 'bow', 'grid')
('on', 'bow', 'gird')
('on', 'bow', 'grid')
('no', 'dig', 'brow')
('on', 'dig', 'brow')
('or', 'bid', 'gown')
('or', 'big', 'down')
('or', 'bog', 'wind')
('or', 'gob', 'wind')
('or', 'bow', 'ding')
('or', 'wig', 'bond')
('ow', 'bog', 'rind')
('ow', 'gob', 'rind')
('ow', 'dig', 'born')
('ow', 'don', 'brig')
('ow', 'nod', 'brig')
('ow', 'orb', 'ding')
('ow', 'rob', 'ding')
('ow', 'rid', 'bong')
('ow', 'rig', 'bond')

---

这段代码是为python3编写的。您可以在Python2.7上使用它，但需要进行更改

yield from solve(pos, newbag, solution + [key])

至

for result in solve(pos, newbag, solution + [key]):
    yield result

Answer 2

第一件事是标准化的话，这样两个字，互为字谜将处理完全相同。我们可以通过转换成小写并对单词的字母进行排序来实现这一点。下一步是区分给定字母的多次出现。为此，我们将每个字母映射到一个包含该字母的符号，以及一个表示该字母在字符串中出现的数字。你知道吗

target = "LNDJOBEAWRL".lower()
symbols = sorted([c + str(target[i+1:].count(c)) for i, c in enumerate(target)])

现在我们已经有了每个单词的标准表示法，我们需要一种快速的方法来检查是否有任何排列与它们匹配。为此，我们使用trie datastructure。以下是一些入门代码：

class Trie:
    def __init__(self, symbol):
        self.symbol = symbol
        self.words = []
        self.children = dict()

    def add_word(self, word):
        self.words.append(word)

    def add_child(self, symbol, trie):
        self.children[symbol] = trie

现在需要将一个空的trie作为根，用任何东西作为符号，专门用来保存所有顶级尝试。然后迭代我们之前转换的每个单词，对于我们生成的第一个符号，检查根trie是否有一个子符号。如果没有，则为其创建一个trie并添加它。如果是，则转到下一个符号，并检查带有该符号的trie是否在上一个trie中。以这种方式继续，直到用尽所有符号，在这种情况下，当前trie节点表示我们转换的单词的标准化形式。将原单词存储在此trie中，然后继续下一个单词。你知道吗

完成后，整个单词列表将包含在这个trie数据结构中。然后，你可以这样做：

def print_words(symbols, node):
    for word in node.words:
        print(word)
    for sym in node.children:
        if sym in symbols:
            print_words(symbols, node.children[sym])

print_words(symbols, root_trie)

打印所有可以由目标单词的符号组成的单词。你知道吗