Stefan, There's nothing wrong with the way the standard library produces permutations. It does it faster than me (probably also because of a better algorithm) and in the same order. collect(permutations()) gives all the permutations in dictionary order, so I guess permutations() produces them in that same order. It is true that I do not know how to make it give me the next permutation to any one I provide it with, but that's not the reason why I wrote my function; as John Myles White says below, I am only giving myself some exercises to learn.
Having said that, even if my algorithm is not the best or the fastest, it works and is a well-defined and "normal" one (nothing really strange), so I would expect Julia to run it at least as fast as Matlab when coded well in both languages. Therefore I assumed I had not coded it well. Imagine there were no faster algorithm to obtain the next permutation of any given one; then one would have to do this: 1- Given any permutation p of [1:n], find the last element that is followed by another one greater than itself. Call it f, and its position k. We have to keep all elements 1:k-1 and rearrange the "tail" (elements k:n). 2- Sort the tail k:n. (I think doing it in-place should make it faster and save memory allocation.) 3- Find the first element in the "tail" (elements k:n) that is larger than f. 4- Move that element to position k, and push part of the tail accordingly. There's nothing strange there, no? Except for the sort() part, which is standard library so it should be well coded, my algorithm is basically rearranging the same numbers 1:n all the time. Therefore, running it in-place should produce very little memory allocation. The fact that my coding of the algorithm allocates a lot of memory allocation and that it runs slower (about 1.65 times slower than Matlab for n=9 in my system) made me think I had not coded the algorithm well. I was looking for type-instability issues, clumsy type declarations, and for the reason why my function allocates so much memory instead of using the same memory positions all the time. I just thought someone more expert than me would spot my mistake(s) in no time. I would also like to think that the point of view of clumsy people like me has some added value for those of you who are designing a language with the vocation to substitute them all :-) Btw, thank you for a great language, I am loving it (at my level). On Monday, October 27, 2014 5:27:44 PM UTC+1, Stefan Karpinski wrote: > > Speaking of which, what's wrong with the standard library function for > producing permutations? They're not produced in the order you want them in? > > On Mon, Oct 27, 2014 at 12:26 PM, Stefan Karpinski <[email protected] > <javascript:>> wrote: > >> I tried sort!(sub(p,fp:length(p))) but it any faster. I suspect that if >> you want to keep with the general shape of this code, it gets kind of >> verbose. You can probably do something that's different and much more >> efficient though – similar to what the standard library does. >> >> On Mon, Oct 27, 2014 at 12:22 PM, Ivar Nesje <[email protected] >> <javascript:>> wrote: >> >>> >>>> P.S. I have tried using in-place >>>> sort!(p[fp:end]) >>>> rather than >>>> p[fp:end] = sort(p[fp:end]) >>>> but it does not do what I expected. >>>> >>> >>> The thing here is quite subtle, but the problem is that currently >>> p[fp:end] returns a copy, rather than a reference. This will change in 0.4, >>> but there are still lots of discussion needed on some of the subtleties, so >>> that we don't do too many iterations before getting it right. >>> >>> I think you can get it now, by writing: >>> >>> sort!(sub(p,fp:length(p))) >>> >>> Regards Ivar >>> >> >> >
