algorithm - 在非图行中找到所有可能解决方案的递归算法

Question

我正在尝试以一种蛮力的方式编写一个简单的非图解算器，但我被困在一个相对容易的任务上。假设我有一行长度为 10 的线索 [2,3]

所以解决方案是:

$$-$$$----
$$--$$$---
$$---$$$--
$$----$$$-
$$-----$$$
-$$----$$$
--$$---$$$
---$$--$$$
----$$-$$$
-$$---$$$-
--$$-$$$--

我想找到一行的所有可能的解决方案 我知道我必须分别考虑每个 block ，每个 block 都有 n-(剩余 block 长度总和 + 剩余 block 数)的可用空间，但我不知道如何从这里开始

Answer 1

好吧，这个问题已经有了很好的答案，所以把这个问题更多地看作是 python 实力的广告。

def place(blocks,total):
    if not blocks: return ["-"*total]
    if blocks[0]>total: return []

    starts = total-blocks[0] #starts = 2 means possible starting indexes are [0,1,2]
    if len(blocks)==1: #this is special case
        return [("-"*i+"$"*blocks[0]+"-"*(starts-i)) for i in range(starts+1)]

    ans = []
    for i in range(total-blocks[0]): #append current solutions
        for sol in place(blocks[1:],starts-i-1): #with all possible other solutiona
            ans.append("-"*i+"$"*blocks[0]+"-"+sol)

    return ans

测试它:

for i in place([2,3,2],12):
    print(i)

产生如下输出:

$$-$$$-$$---
$$-$$$--$$--
$$-$$$---$$-
$$-$$$----$$
$$--$$$-$$--
$$--$$$--$$-
$$--$$$---$$
$$---$$$-$$-
$$---$$$--$$
$$----$$$-$$
-$$-$$$-$$--
-$$-$$$--$$-
-$$-$$$---$$
-$$--$$$-$$-
-$$--$$$--$$
-$$---$$$-$$
--$$-$$$-$$-
--$$-$$$--$$
--$$--$$$-$$
---$$-$$$-$$