Can my permutations function be defined using iteration?

I have two functions, tuples and perm. They are similar.

tuples[L_, 0] := {{}};
tuples[L_, k_] := Join @@ Table[{x}~Join~y, {x, L}, {y, tuples[L, k - 1]}];

perm[L_, 0] := {{}};
perm[L_, k_] := Join @@ Table[{x}~Join~y, {x, L}, {y, perm[Select[L, # != x &], k - 1]}];

(*tuples[{1, 2, 3}, 2]*)
(*{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}*)
(*perm[{1, 2, 3}, 2]*)
(*{{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}}*)

I know tuples can be defined using Nest, but I don't know whether perm can be defined using Nest or Fold.

tuples2[L_, k_] := Nest[Join @@ Table[x~Join~{y}, {x, #}, {y, L}] &, {{}}, k];
• Could you please tell us what perm is supposed to do? Is it working correctly or not? And what specifically is your question? Feb 6 '13 at 3:07
• @whuber perm is equivalent to Permutations. It looks like it is a question of how to implement it functionally. Feb 6 '13 at 3:10
• By comparing to the documentation, it is clear that the implementation given in the question is not equivalent to Permutations. For instance, the present implementation would not reproduce the behavior of Permutations with just one argument or with a list as a second argument. I think it's incumbent on the OP to tell us more precisely what he wants, rather than hoping our guesses will be correct. Feb 6 '13 at 3:24
• @rc Yes, one would guess that... Another point: exactly how much of that behavior should be reproduced? For instance, the sequence of elements in the output list does not appear to be documented, so would it be okay for perm to produce the same output as Permutation but in a different order? We don't know because the OP has not specified what the desired behavior is. Feb 6 '13 at 3:33
• @whuber and @rcollyer: I think the OP's question can be boiled down to this: "Assuming perm is correct and does what the OP wants it to do (regardless of similarity to Permutation), can it be written using Nest or Fold?".
– rm -rf
Feb 6 '13 at 4:49

An iterative procedure could look as follows: when you call your perm function and when k>0, then a first step would be, to build your result for k==1. This is all elements of the list wrapped in List

Permutations[{1,2,3},{1}]
(* Out= {{1},{2},{3}} *)

With this start, you could concentrate to think about how a function would take e.g. {1} and create all children. This process is done in the recursion of your original function. Nevertheless, it's not hard to calculate this without recursion. The {1} would be transformed into a list {{1,2},{1,3}}, meaning you append to the initial list {1} all members of your all list which are not contained in the initial {1}.

When you want to do this for {{1},{2},{3}}, you can Map the same function over the list. Since this would leave you with 3 sublists, you need to join them. This basic idea can be put into a function step, which is called after we initialized our result

step[partialRes_, all_] :=
Join @@ Map[Table[Append[#, new], {new, Complement[all, #]}] &, partialRes];

permHalirutan[l_, k_Integer] := Module[{res, iter = k - 1},
res = Partition[l, 1];
Nest[step[#, l] &, res, iter]
]

That should do an equivalent work as your original function.

And before someone asks, yes, there is of course a more compact form of the same method kicking some of the unnecessary characters which make it more readable, but less nerdy:

p[l_,k_]:=Nest[Join@@(Table[Append[#,n],{n,Complement[l,#]}]&/@#)&,List/@l,k-1]