如何使用递归获取满足特定要求的列表列表？

Question

我有一个单词列表，这些单词是字符串的子集

例如，如果字符串是 'abb'

列表是

['a','ab','b']

我想创建一个列表列表，这些列表加起来就是原始字符串。因此列表列表中的一个列表的字母数必须完全等于字符串中的字母数

所以对于给定的例子，一个是 ['b','ab']

有一个辅助函数可以跟踪每个字符串中的字母，因此可以将字母视为数字，并可以像 'b' + 'ab' == 'abb' 会被认为是 True

我是递归的新手，我想不出创建这个函数的方法，请帮忙。

完整示例：

string = 'office key'
lst_of_possibilities = ['icky', 'fee', 'coy', 'key', 'ice', 'office', 'fief', 'icy', 'iffy', 'eye', 'foe', 'eke', 'yoke', 'coffee', 'coke', 'off', 'foci', 'fife']

函数结束后输出为：

[['eke', 'icy', 'off'], ['eke', 'off', 'icy'], ['ice', 'key', 'off'], ['ice', 'off', 'key'], ['icy', 'eke', 'off'], ['icy', 'off', 'eke'], ['key', 'ice', 'off'], ['key', 'off', 'ice'], ['key', 'office'], ['off', 'eke', 'icy'], ['off', 'ice', 'key'], ['off', 'icy', 'eke'], ['off', 'key', 'ice'], ['office', 'key']]

所以我想表达的意思是，上面列表中的每个列表加起来组成 'office key'

Answer 1

执行此操作的最愚蠢的方法可能是以下方法：令字符串为 s，单词列表为 p

s = "office key"
p = ['icky', 'fee', 'coy', 'key', 'ice', 'office', 'fief', 'icy', 'iffy', 'eye', 'foe', 'eke', 'yoke', 'coffee', 'coke', 'off', 'foci', 'fife']
res_list = []
s = "".join(s.split())
n = len(p)
for mask in range(2**n):
    str = ""
    cur_list = []
    for i in range(n):
        if mask & (2**i) > 0:
             str += p[i]
             cur_list.append(p[i])
             if len(str) > len(s):
                 break
             bad = 0
             for ch in p[i]:
                if ch not in s:
                    bad = 1
                    break
             if bad == 1:
                break
    ok = 1
    for ch in s:
        if ch == " ":
            continue
        pos = str.find(ch)
        if pos == -1:
            ok = 0
            break
        else:
            str = str[:pos] + str[(pos+1):]
    if len(str) > 0:
        ok = 0
    if ok == 1:
        res_list.append(cur_list)

print res_list

这是一个稍微优化的暴力搜索，我认为这对你的特定问题来说是可以的，因为你想要所有可能解决方案的列表。

P.S。您拥有每个特定输出的所有排列，可以在最后输出 res_list

中每个列表的所有排列更快地实现

如何使用递归获取满足特定要求的列表列表？

How to get a list of lists that meet a certain requirement using recursion?

python

recursion

list

permutation