Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 2 down vote favorite

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];
share|improve this question
Could you please tell us what perm is supposed to do? Is it working correctly or not? And what specifically is your question? – whuber Feb 6 at 3:07
1  
@whuber perm is equivalent to Permutations. It looks like it is a question of how to implement it functionally. – rcollyer Feb 6 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. – whuber Feb 6 at 3:24
1  
@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. – whuber Feb 6 at 3:33
3  
@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 at 4:49
show 4 more comments

1 Answer

up vote 5 down vote accepted

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[36]= {{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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.