On Fri, 7 Jul 2006, Levi Bard wrote:
> OK, piggers!
>
> Say you have four (in this instance) numbers: 0, 1, 2, 3.
> Can you determine a good way to programmatically enumerate all the
> possible permutations of these numbers?
>
> As in:
> 0 1 2 3
> 0 1 3 2
> 0 2 1 3
> 0 2 3 1
> ...
We had to do that as an exercise in recursion. I thought the algorithm was
something like:
1 permute (thelist) {
2 if there are >2 in thelist,
3 print thelist.1
4 permute (thelist - thelist.1)
5 else if there are 2 in thelist,
6 print thelist.1 thelist.2
7 print thelist.2 thelist.1
8 else /* there is only 1 */
9 print thelist.1
10 end if
11 }
but I was wrong, since that doesn't work. Maybe instead of lines 4 & 5,
have
for foo in (each member of thelist)
print thelist.foo
permute (thelist - thelist.foo)
end for
The prof said any recursive algorithm can be turned into a non-recursive
algorithm, which is reasonable, as that's what compiled code with loops
completely unrolled is.
--
-eben QebWenE01R@vTerYizUonI.nOetP royalty.no-ip.org:81
> A: It's annoying as hell
> Q: Why do most people hate top-posting? -- Lots42 The Library Avenger
http://www.fscked.co.uk/writing/top-posting-cuss.html
-----------------------------------------------------------------------
This list is provided as an unmoderated internet service by Networked
Knowledge Systems (NKS). Views and opinions expressed in messages
posted are those of the author and do not necessarily reflect the
official policy or position of NKS or any of its employees.
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 20:37:02 EDT