scala - 这个排列函数是如何工作的(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

我知道当输入字符串的长度为 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

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