这个排列函数如何工作（Scala）？

发布于 2024-11-15 14:52:51 字数 465 浏览 5 评论 0原文

我正在查看 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 返回，我认为接下来发生的情况是它被附加到唯一的另一个留下的字符，但我无法真正想象你如何到达这一点，或者为什么这会导致排列列表。

（我自己已经解决了这个问题，但使用了排列方法，这使得它成为一个相当简单的 1-liner，但希望能够理解上面的内容。）

原文

I'm looking at Pavel's solution to Project Euler question 24, but can't quite work out how this function works - can someone explain what it's doing? Its purpose is to return the millionth lexicographic permutation of the digits 0 to 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

I understand that when the input String is length 1, the function returns that character as a Seq, and I think then what happens is that it's appended to the only other character that was left, but I can't really visualise how you get to that point, or why this results in a list of permutations.

(I already solved the problem myself but used the permutations method, which makes it a fairly trivial 1-liner, but would like to be able to understand the above.)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

清风疏影 2024-11-22 14:52:51

对于给定字符串 s 的每个字母 (flatMap(c => ...))，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

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

For each letter (flatMap(c => ...)) of the given string s, ps generates a permutation by permutating the remaining letters ps(s.filterNot(_ == c)) and prepending the taken letter in front of this permutation (map(c +)). For the trivial case of a one letter string, it does nothing (if(s.size == 1) Seq(s)).

Edit: Why does this work?

Let’s begin with shuffling a one letter string:

[a]
-> a   # done.

Now for two letters, we split the task into subtasks. Take each character in the set, put it to the first position and permutate the rest.

a [b]
-> b
b [a]
-> a

For three letters, it’s the same. Take each character and prepend it to each of the sub-permutations of the remaining letters.

a [b c]
-> b [c]
   -> c
-> c [b]
   -> b
b [a c]
-> a [c]
   -> c
-> c [a]
# ... and so on

So, basically the outermost function guarantees that each letter gets to the first position, the first recursive call guarantees the same for the second position and so on.

回复收藏 0 原文

素罗衫 2024-11-22 14:52:51

让我们用伪代码写出来：

for each letter in the string
  take that letter out
  find all permutations of what remains
  stick that letter on the front

因为它适用于字符串中的每个字母，所以它的有效作用是将每个字母依次移动到字符串的前面（这意味着第一个字母可以是任何存在的字母的数量，这就是您进行排列所需的）。由于它递归地工作，因此余数是每个剩余的排列。

请注意，该算法假设所有字母都不同（因为 filterNot 用于删除所选字母）；集合库中的排列方法不假设这一点。

Let's write it out in pseudocode:

for each letter in the string
  take that letter out
  find all permutations of what remains
  stick that letter on the front

Because it's working for each letter in the string, what this effectively does is move each letter in turn to the front of the string (which means that the first letter can be any of the letters present, which is what you need for a permutation). Since it works recursively, the remainder is every remaining permutation.

Note that this algorithm assumes all the letters are different (because filterNot is used to remove the selected letter); the permutations method in the collections library does not assume this.

回复收藏 0 原文

时光倒影 2024-11-22 14:52:51

与此无关，但您可能有兴趣知道您可以计算第一百万个词典排列，而无需计算任何先前的排列。

这个想法非常简单：对于 N 位数字，有 N! 种排列。这意味着 10 位数字可以产生 3628800 个排列，9 位数字可以产生 362880 个排列，依此类推。有了这些信息，我们就可以计算出下表：

First digit    First Permutation    Last Permutatation
0              1                    362880
1              362881               725760
2              725761               1088640
3              1088641              1451520
4              1451521              1814400
5              1814401              2177280
6              2177281              2540160
7              2540161              2903040
8              2903041              3265920
9              3265921              3628800

因此第一个数字将是 2，因为这是 1000000 的范围。或者，更简单地说，第一个数字是索引 (1000000 - 1) / fat(9) 处的数字。所以你只需要递归地应用它：

def fat(n: Int) = (2 to n).foldLeft(1)(_*_)
def permN(digits: String, n: Int): String = if (digits.isEmpty) "" else {
    val permsPerDigit = fat(digits.length - 1)
    val index = (n - 1) / permsPerDigit
    val firstDigit = digits(index)
    val remainder = digits filterNot (firstDigit ==)
    firstDigit + permN(remainder, n - index * permsPerDigit)
}

Unrelated to this, but you might be interested in knowing you can compute the millionth lexicographical permutation without computing any of the previous ones.

The idea is pretty simple: for N digits, there are N! permutations. That means 10 digits can yield 3628800 permutations, 9 digits can yield 362880 permutations, and so on. Given that information, we can compute the following table:

First digit    First Permutation    Last Permutatation
0              1                    362880
1              362881               725760
2              725761               1088640
3              1088641              1451520
4              1451521              1814400
5              1814401              2177280
6              2177281              2540160
7              2540161              2903040
8              2903041              3265920
9              3265921              3628800

So the first digit will be 2, because that's the range in which 1000000 is. Or, to put it more simply, the first digit is the one at the index (1000000 - 1) / fat(9). So you just need to apply that recursively:

def fat(n: Int) = (2 to n).foldLeft(1)(_*_)
def permN(digits: String, n: Int): String = if (digits.isEmpty) "" else {
    val permsPerDigit = fat(digits.length - 1)
    val index = (n - 1) / permsPerDigit
    val firstDigit = digits(index)
    val remainder = digits filterNot (firstDigit ==)
    firstDigit + permN(remainder, n - index * permsPerDigit)
}

回复收藏 0 原文

~没有更多了~