1

我目前正在通过递归学习排列生成。

我发现以下代码非常适合打印排列，但我似乎无法存储值：堆栈中的所有值在升级时都会丢失。

def permute_util(str, count, result, level):

    if level == len(result):
        print(result)
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)

结果：

['A', 'A', 'B', 'C']
['A', 'A', 'C', 'B']
['A', 'B', 'A', 'C']
['A', 'B', 'C', 'A']
['A', 'C', 'A', 'B']
['A', 'C', 'B', 'A']
['B', 'A', 'A', 'C']
['B', 'A', 'C', 'A']
['B', 'C', 'A', 'A']
['C', 'A', 'A', 'B']
['C', 'A', 'B', 'A']
['C', 'B', 'A', 'A']

我已经尝试在基本情况下将结果添加到全局列表中，但只有最新级别会被存储，而所有其他以前的值都会被覆盖，就像这样

 def permute_util(str, count, result, level):
    global glob 
    if level == len(result):
        **glob += [result]**
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)

['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']

也试过这个达到同样的效果：

 def permute_util(str, count, result, level, lists):
    global glob 
    if level == len(result):
        return [result]


    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        foo = permute_util(str, count, result, level + 1, lists)
        lists = lists + foo
        count[i] += 1

   lists = []
   permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0, lists)

将基本案例中的所有“结果”存储在列表中并在完成时返回它的最佳方法是什么？

4

2 回答 2

1

随着递归的进行，您会一遍又一遍地改变结果。
你可以这样做：

def permute_util(string, count, result, level):

    if level == len(result):
        print(result)
        res.append(tuple(result))   # stores current result as a copy in an immutable tuple
        return

    for i in range(len(string)):
        if count[i] == 0:
            continue;
        result[level] = string[i]
        count[i] -= 1
        permute_util(string, count, result, level + 1)
        count[i] += 1


if __name__ == '__main__':

    res = []

    permute_util(list("ABC"), [2, 1, 1], [None]*len("AABC"), 0)
    print(res)
于 2018-05-03T04:40:12.380 回答
0

Python 将指针附加到列表而不是实际列表。因此，您所拥有的是大量指向结果最终状态的指针，因此存在重复值。每次追加时尝试创建副本，如下所示：

final_ans = []
def permute_util(str, count, result, level):

    if level == len(result):
        final_ans.append(result[:])    # if you don't explicitly want list, try final_ans.append(''.join(result))
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)
for ans in final_ans:
    print(ans)
于 2018-05-03T04:42:36.463 回答