这种排列功能如何工作(Scala)？

Question

我正在研究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

我理解当输入String的长度为1时,该函数将该字符作为Seq返回,我认为接下来会发生的是它附加到剩下的唯一其他字符,但我无法直观地看到你是如何进行的那一点,或者为什么会产生一个排列列表.

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

Answer 1

每个字母(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

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