Picky, picky.
See, I told you, you don't really believe in recursion. ;~P It takes a lot of practice.
I just don't quite understand how that block works.
The extended version of MAP still reports a list the same length as its input list. Somehow or other you need a deep recursion.
I don't understand why there is a list parameter in the bloc map. Because there is only one list entry possible.
Yes, but I could use some boolean and report a list of booleans of the same lenght. Then work on this return.
I'm just teasing you.
So, if you want all the permutations of (1 2 3), you have to find all the permutations that start with 1 (namely (1 2 3) and (1 3 2)), all the permutations that start with 2, etc. That's the job of the outer MAP: find all the permutations that start with OUTER for each value of OUTER in VALUES.
So, okay, how do you find all the permutations that start with 1? Well, you have to find all the permutations of the smaller list with 1 removed, which is the job of the recursive call, and you have to stick a 1 in front of each of them, which is the job of the inner MAP.
The rest of it really is just a lot of practice. Eventually you'll recognize situations in which the base case should return a list containing the empty list rather than just the empty list, and you'll recognize situations in which you have to flatten the results of a MAP.
(But note that you can't use the FLATTEN option of the LENGTH block, because that flattens all the way down to atoms, so you'd have (1 2 3 1 3 2 2 1 3 2 3 1...) as the result. Hence the APPEND INPUT LIST thing. (This comes up often enough that most Lisps have a primitive FLATMAP that applies APPEND to the result of a MAP.))
I think I understand now.
1 in front of each of permutations of 2,3,
2 in front of each of permutations of 1,3,
3 in front of each of permutations of 1,2.
Yeah, exactly. So that's three recursive calls, which happen because the code for the recursive call is inside a MAP.
Of course, it gets worse the longer the list, as with, say, a 10 item long list, that's 10 recursive calls to 9 item permutations, etc.
Naive implementation with the use of HOF
The same idea and iterative approach (as for me cleaner and more understandable)
Wouah ! Thank you @dardoro .
This is exactly what I was trying to do.
Then I can have the list of permutations of order n.
Yes, the value of LIST is always the same, namely, the second input to MAP. This is because I lost the argument with Jens, in which I wanted its value to be the sublist from VALUE to the end of the list.
If all you really wanted was to know if there are duplicates, then I don't see why you asked for permutations at all! But if you wanted permutations I don't see any reasonable way to do it without recursion. (Of course you could build your own stack of pending tasks, but that'd be ugly.)
And I have my bloc permutations
The problem is that using crossproduct, I create first a very huge list (of size n^n) to keep a list of size n!...
And CROSSPRODUCT is itself implemented recursively, for the same reason -- it's the only reasonable way to build anything in which the size of the output is an exponential function of the size of the input.
Anyway, this is fun, but it's way past my bedtime. Hasta la mañana!
So good night !!! and thanks for help.
Yes, but I do some maths, I am not a programmer. And this way seems to me more easy to explain...
This bloc is wrong.
Because I need to enter in crossproduct iota(n) n times... I don't know how to do that.
And now, I need to code the signature of a permutation σ : ε(σ)...
I know that I have to combine using product the function that returns sgn(σ(j)-σ(i)) mapped over the list of (i,j) where i < j .
But how to create the list of indexes that verify i < j ?
