Ok. That means given a list A (lists are more natural in FP),
you will need to split this list for each element into the element
itself and the rest B. Assume we have a function that does that,
say "splitUp". What's the type signature of this function?

While we're at it, let's call the main function "perms". What's
its type signature?

Given "splitUp", how exactly do you combine the results of
the recursive call in the definition of "perms"?

(I think you didn't say which language you want to use, but for
example in Haskell, one nice way to write this down would be to
use list comprehensions).

- Dirk

Ok, but using a concrete language helps to fix the notation :-)
Again: in FP one usually thinks in "lists" -- the difference to arrays
is that there is no constant-time access to the n-th element (and
in a pure language, one cannot update an element, either).

Just so you see some notation in a concrete language, in e.g. Haskell
this function is an infix operator (++), as in

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
That function won't be a primitive in most languages. Again in Haskell,
one could implement it with a list comprehension:

concat x yss = [x:ys | ys <- yss]

where : puts a single element in front of a list. Read this similar
to a "set comprehension" in mathematics, i.e.

The list of all "x:ys" for all elements ys in the list yss

In Haskell, the type of a list is denoted by square brackets, so
"[Integer]" is a list of Integers. If the concrete type does not matter,
one can use type variables (which start in lower case). The type of
concat is

concat :: a -> [[a]] -> [[a]]

That means, the first argument can be any type (including an integer),
the second argument must be a list of lists of this type, and the
result is again a list of lists of this type. Note that this is both
more general than your type (it's not restricted to integers) and
more specific (the second argument is not just any array).
Test in ghci:

Prelude> let concat x yss = [x:ys | ys <- yss]
Prelude> :t concat
concat :: a -> [[a]] -> [[a]]
Prelude> concat 4 [[1,2], [1,3]]
[[4,1,2],[4,1,3]]
Again, that's not primitive, but can be implemented in a similar
way (exercise :-).

Also, I assume the code you gave for "concatnat" is a copy-and-paste
error, because it doesn't match this description.
That assumes that you can identify the integer in the array (by
equality), and will fail if your array consists of elements that
cannot be compare (functions, for example).

Moreover, if you want to use that function, that means that now
you have an algorithm different to the one we discussed before.
There's a type error in your case for length one: The result must be
a list of lists, so you don't return the first (and only) element of
"a", but the whole list instead.

Also, in FP it's more convenient to do the case distinction for an
empty list (what should the result be in this case)?

Finally, I can guess what you want to do, but I don't think it will
work quite in this way, given that I understood your "concatnat"
correctly.

So there are two things unfinished:

1) Implement the above algorithm correctly; and
2) Implement the (different) algorithm from the other posting.

I also recommend using a concrete FP language (no matter which one),
in this way, you can test out that it really works. With ad-hoc
notation and handwaving, it's easy to make mistakes.

- Dirk