gpt4 book ai didi

java - 排列、递归

转载 作者:行者123 更新时间:2023-11-29 03:57:35 27 4
gpt4 key购买 nike

我有一个作业:用户输入一个字符串,例如 ABCD,程序必须给出所有排列。我不希望整个代码只是一个提示。这是我到目前为止在他们那里得到的,我没有得到任何实现。

以ABCD为例:

在本例中获取字符串长度的阶乘 4! = 24.

24/4 = 6 所以第一个字母必须在 6 之后改变。到目前为止一切顺利。

比得到剩余字母的阶乘,即三个 3! = 6.

6/3 =2 每个字母2个位置。从这里我不知道它如何继续填充 24 个位置。

有了这个算法我就拥有了

ABCD

ABD

空调

空调

广告

广告

B

B

B

B

B

B

.

. (继续 6 C 和 6 D)

我认为我的问题是我没有很多递归问题的经验,所以请推荐一些程序来帮助我更好地了解递归。

谢谢!如果有什么不清楚的地方请指出。

最佳答案

你说得对,递归是必经之路。您通过一点点数学运算得出的示例都是正确的,但有点间接。

这是一些伪代码:

 def permute(charSet, soFar):
if charSet is empty: print soFar //base case
for each element 'e' of charSet:
permute(charSet without e, soFar + e) //recurse

部分递归树的例子

                      permute({A,B,C}, '')
/ | \
permute({B,C}, 'A') permute({A,C}, 'B') permute({A,B}, 'C')
/ \
permute({A}, 'BC') permute({C}, 'BA')
|
permute({}, 'BCA')<---BASE CASE, print 'BCA'

编辑

处理重复字符而不重复任何排列。让 unique 成为一个函数,从集合中删除任何重复的元素(或通过索引被视为有序字符集合的字符串)。

1) 存储结果(包括重复的),然后过滤掉

 def permuteRec(charSet, soFar):
if charSet is empty: tempResults.add(soFar) //base case
for each element 'e' of charSet:
permute(charSet without e, soFar + e) //recurse

global tempResults[]

def permute(inString):
permuteRec(inString, '')
return unique(tempResults)

print permute(inString)

2)首先避免产生重复

 def permute(charSet, soFar):
if charSet is empty: print soFar //base case
for each element 'e' of unique(charSet):
permute(charSet without e, soFar + e) //recurse

关于java - 排列、递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5438960/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com