How does this permutations function work (Scala)?

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 purp开发者_高级运维ose 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.)

---

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.

---

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.

---

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)
}