World: r4wp

/me pouring a glass of whisky

REBOL [title: "Anagram List"]


a:[]m: func[s p][repeat i length? s[append a rejoin[p k: s/:i r: 
head remove at copy s i]m r join p k]]m ask""""editor unique a probe 
length? a


a:[]m: func[s /local i][if 1 = i: length? s[append a copy head s 
exit]loop i[append s s/1 m next remove s]]m ask""editor a probe length? 
a

halt

Mine is the first one, yours is the second.

can you give a test case where mine is faling ?

Try each line above.  Mine gives 325 anagrams for "asdfg".  Yours 
is much faster, but only results in 120 anagrams for the same input 
string.

For a 5 letters word, the number of combinations should be 5! (factorial 
5) which gives 120.

never mind - stupid me.  didn't count the unique results in mine.

<-- bows low, and walks away :)

I still have the same question though - is there any way to evaluate 
this without the exponential increase in loop counts?

Nick, it would be actually nice if it was just "exponential growth". 
But the number of permutaions of N elements is N! (N factorial), 
which grows faster than the exponential function.

typo: "permutations"

So there's no way of reducing this problem beyond N! ?

How can you produce N! distinct results without producing N! distinct 
results?

(there is no way)

I was hoping to discover some ignorance on my part about the problem.

Thank you for the definitive answer Ladislav, and thanks for the 
code Steeve

(I was hoping that there was perhaps some sort of parallel processing 
solution or some sort of advanced math magic that I knew nothing 
about)

Aha, but Steeve's algorithm looks like being slower than O(N!), if 
I understand it well.

Nick -- sounds like you want an algorithm that, say, returns the 
next 50 -- that way you can work with a window rather than have to 
generate all perms in one gulp. Some of the offered solutions should 
be easily adaptable in that way.

Ladislav, can you make one which performs faster than Steeve's?


Sunanda, paging through windows of is a great way to be practical. 
 I'm more concerned with finding the fastest algorithm - no reason 
- just frustrated with myself for sitting last night for longer than 
I wanted with a CS101 type problem ;)

Just out of curiosity, has anyone written a difinitive article about 
the performance of various looping structures in REBOL?  I remember 
some discussion about it several years ago, related to how badly 
REBOL did in the language "shootout" benchmarks (lots of  "for'" 
loops, if I remember correctly).  That would be a nice article to 
have available.

Nick, the issue is many of the looping constructs were mezzanine...

For R2: native loops are faster than mezzanine (function) loops, 
so much faster that their individual differences amongst themselves 
are almost irrelevant. For R3 all loops are native (except FIND-ALL, 
temporarily), so the big difference is one-time-per-call bind/copy 
overhead for binding loops, versus not having that for non-binding 
loops.

LOOP is the fastest limited scope loop.

I always noticed that Carl used more "while" structures than I w

For R2 I would use LOOP, REPEAT, FOREACH or WHILE whenever possible. 
In R3, REPEAT and FOREACH have bind/copy overhead, while FORALL and 
FORSKIP don't, so the latter can be faster in many cases. WHILE and 
LOOP are the same in R3 as they were in R2, at least relative to 
the other native loops.

FOR has bind/copy overhead in R3 and is a complex mezzanine in R2, 
so I only use it when it is really appropriate.

UNTIL is native in both too, basically a slightly simplified WHILE.

R3 is currently missing anything like the feature that made it possible 
to write really well-integrated mezzanine control structures, instead 
turning all such control structures into natives. Which was a problem 
before R3 was open sourced, not as much of one now.

Nick -- Have you looked at using a variable base algorithm? It may 
be fast, and it should be amenable to windowing:
   http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation
Even if neither, it should be fun to write the script.

FOR ... is a complex mezzanine in R2
, with a lot of bugs, I have to add

Agreed :(

Do you have a non-buggy version? I'd love to add it to rebol-patches, 
with your permission.

Hmm, I do (I once submitted it to Carl, but he never used it). Nevertheless, 
in my code I prefer a general loop called CFOR (the name is unfortunate, 
I must admit). That is what I propose instead since it is both faster 
and more flexible at the same time. Do you think it makes sense to 
propose it in the CC?

Any good idea of a Rebol-compatible name for it?

The trouble with FOR is not only that it has bugs. Another problem 
is that it is incompatible with REPEAT, while assumed to be a generalization 
of it...

I remember CFOR, it was interesting. It's not FOR compatible though. 
What I was hoping to put in rebol-patches was a function with the 
same API as FOR, but without the bugs. Additional functions are great 
too, but out of scope for the rebol-patches project.

Hmm, I actually do not propose to use my patched FOR since it is 
extremely slow like the original, I think it would make more sense 
to use a more REPEAT-compatible version of it, which I do not have 
now.

I don't recommend using FOR in R2, patched or not, but I would rather 
have a patched version than a non-patched version. That's the whole 
point to rebol-patches. I don't judge the functions in some philosophical 
or practical way, I just make sure they at least work.

Better functions are more the purview of other projects.

Is 'for used much at all?

or, to tell it differently: I prefer to have a version of FOR which 
would be more R3 FOR compatible...

(instead of patching the R2 FOR, which I do have patches for, but 
which is extremely slow)

FOR is not used in R2 (at least I never recommended its usage) because:

* it is buggy
* it is extremely slow

Can that be done without breaking too much code? Because if so, that 
would definitely be in the project scope. A native FOR replacement 
would be ideal, but we can't change existing R2 versions to have 
always had such a function in the past. The rebol-patches project 
is for bringing up the compatibility and fixing known bugs when run 
on existing R2 versions. I hope to push its compatibility all the 
way back to 2.5.0. Replacing FOR with a non-buggy native version 
in some future R2 release would just mean that for that version going 
forward rebol-patches wouldn't need to patch that particular function.

So unless you have a way for rebol-patches to perform a retrofit 
of an existing R2 version with a new native function using cross-platform 
code, we're going to need not only the mezz patch for the past and 
the native for future R2 releases (if any).

I did not mean native. I just meant mezzanine FOR but implemented 
differently.

(to behave more like the native FOR in R3 or REPEAT in R2)

OK, cool. Will it have the same external API, so that if it is used 
in the same way (without obscure hacks) it will do the same thing? 
I'm OK with changing its behavior when you change the variable in 
mid loop, as long as that isn't commonly done in R2. If it's too 
incompatible that would be more something to put in R2/Forward (I'm 
spliting the fixes from the major changes).

How would it be different? Do you have a link to one of those articles 
you write about this kind of thing? :)