gpt4 book ai didi

scala - 这个排列函数是如何工作的(Scala)?

转载 作者:行者123 更新时间:2023-12-04 22:15:49 26 4
gpt4 key购买 nike

我正在查看 Pavel 对 Project Euler 问题 24 的解决方案,但不能完全弄清楚这个函数是如何工作的——有人能解释一下它在做什么吗?其目的是返回数字 0 到 9 的百万分之一词典排列。

def ps(s: String): Seq[String] = if(s.size == 1) Seq(s) else 
s.flatMap(c => ps(s.filterNot(_ == c)).map(c +))

val r = ps("0123456789")(999999).toLong

我知道当输入字符串的长度为 1 时,该函数将该字符作为 Seq 返回,然后我想会发生什么事情是它被附加到唯一剩下的其他字符上,但我无法真正想象你是如何得到的那一点,或者为什么这会导致排列列表。

(我自己已经解决了这个问题,但使用了 permutations 方法,这使它成为一个相当简单的 1-liner,但希望能够理解上述内容。)

最佳答案

对于给定字符串 flatMap(c => ...) 的每个字母 ( s ), ps 通过排列剩余的字母 ps(s.filterNot(_ == c)) 并在此排列 ( map(c +) ) 前面加上取用的字母来生成排列。对于单字母字符串的微不足道的情况,它什么都不做( if(s.size == 1) Seq(s) )。

编辑 :为什么这有效?

让我们从打乱一个单字母字符串开始:

[a]
-> a # done.

现在对于两个字母,我们将任务拆分为子任务。取集合中的每个字符,将其放在第一个位置并排列其余的字符。
a [b]
-> b
b [a]
-> a

对于三个字母,它是一样的。取每个字符并将其添加到剩余字母的每个子排列中。
a [b c]
-> b [c]
-> c
-> c [b]
-> b
b [a c]
-> a [c]
-> c
-> c [a]
# ... and so on

所以,基本上最外面的函数保证每个字母到达第一个位置,第一个递归调用保证第二个位置相同,依此类推。

关于scala - 这个排列函数是如何工作的(Scala)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6343717/

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