2
$\begingroup$

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];
Improve this question
$\endgroup$
9
  • $\begingroup$ Could you please tell us what perm is supposed to do? Is it working correctly or not? And what specifically is your question? $\endgroup$
    – whuber
    Feb 6, 2013 at 3:07
  • 1
    $\begingroup$ @whuber perm is equivalent to Permutations. It looks like it is a question of how to implement it functionally. $\endgroup$
    – rcollyer
    Feb 6, 2013 at 3:10
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Feb 6, 2013 at 3:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – whuber
    Feb 6, 2013 at 3:33
  • 3
    $\begingroup$ @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?". $\endgroup$
    – rm -rf ♦
    Feb 6, 2013 at 4:49

1 Answer 1

Reset to default
5
$\begingroup$

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]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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