MC: Permutations of chars in a string
joe...@usa.net
Input: STRING of any length > 1. (Bonus points if it works for len=1)
Output: LIST of STRINGS (every possible permutation of the characters).
Example:
"XYZ" --> { "XYZ" "XZY" "YXZ" "YZX" "ZXY" "ZYX" }
Winner: BYTES * TIME.
Usual MC rules.
Stand-alone User-RPL program only; no SYSEVAL; no LIBEVAL; no library
functions; assumes default flag settings; leaves other stack contents
alone; leaves no extraneous junk on the stack; etc etc etc.
For what it's worth, Richard Nelson proposed this as a "mini-challenge"
at last Friday's meeting of the Southern California PPC Chapter (hosted
by Gary Tenzer), and nobody even came up with a program that worked,
let alone a short or fast program. We're getting old much too fast...
-Joe-
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Hubert Canon
> Input: STRING of any length > 1. (Bonus points if it works for len=1)
> Output: LIST of STRINGS (every possible permutation of the characters).
>
> Example:
> "XYZ" --> { "XYZ" "XZY" "YXZ" "YZX" "ZXY" "ZYX" }
Maybe something like that will work (I have not my HP48 with me to
test it) :
'PERMUT'
« DUP LENGTH -> s l
« IF l 1 <=
THEN s 1 ->LIST
ELSE
1 l
FOR i
s 1 i 1 - SUB
s i 1 + l SUB
+ PERMUT
s i DUP SUB
ADD OBJ-> DROP
NEXT
l FACT ->LIST
END
»
»
--
Hubert Canon
Erwann ABALEA
joe...@usa.net a écrit:
> New Mini-Challenge: Rearrange a string in all the possible ways.
>
> Input: STRING of any length > 1. (Bonus points if it works for len=1)
> Output: LIST of STRINGS (every possible permutation of the characters).
>
> Example:
> "XYZ" --> { "XYZ" "XZY" "YXZ" "YZX" "ZXY" "ZYX" }
>
> Winner: BYTES * TIME.
>
Here's my first contribution to the MC:
The program is recursive, so it should be called PERMS
PERMS:
<< -> S
<< { } IF S SIZE 1 == THEN S +
ELSE 1 S SIZE FOR I S I DUP SUB S 1 I 1 - SUB S I 1 + S SIZE SUB +
PERMS
LIST-> DUP 2 + ROLL -> T PREFIX
<<
1 T FOR J PREFIX J 1 + ROLL + J ROLLD NEXT T ->LIST
>>
+ NEXT END
>>
>>
BYTES -> #1A8Ch 243.5
"ABCDE" 'PERMS' MEM DROP TIM -> 2: {...} 1: 262097.39:31.99431_s on my GX
(I use MEM DROP to force a garbage collection before the program)
Erwann.
Erwann ABALEA
> PERMS:
> << -> S
> << { } IF S SIZE 1 == THEN S +
> ELSE 1 S SIZE FOR I S I DUP SUB S 1 I 1 - SUB S I 1 + S SIZE SUB +
> PERMS
> LIST-> DUP 2 + ROLL -> T PREFIX
> <<
> 1 T FOR J PREFIX J 1 + ROLL + J ROLLD NEXT T ->LIST
> >>
> + NEXT END
> >>
> >>
Funny thing... I just wanted to speedup my code and reduce it, so I tried to
replace the part
LIST-> DUP 2 + ROLL -> T PREFIX
<<
1 T FOR J PREFIX J 1 + ROLL + J ROLLD NEXT T ->LIST
>>
+ NEXT END
by a simple ADD statement, which does exactely the same thing (this part of my
program takes a prefix string in level 2, a list of strings in level 1, and
adds the prefix to each of the strings of the list)... It is smaller, but also
slower!
My first version takes 32.04s to find the premutations of "ABCDE", and with
the ADD version, it takes about 39s!!
Why?
Erwann.
Donald Bachman
be shortened a bit). Unfortunately I'm going to be out of town for
the next 3 days (and need desperately to pack), but if something
brilliant comes to mind, I'll post.
<< -> S
<< 1 S SIZE FOR i S i DUP SUB NEXT
S SIZE ->LIST {""} SWAP 1
<< -> L C
<< L 1
<< C
<< -> S D
<< 0 S SIZE FOR i S 1 i SUB D + S i 1 + S SIZE SUB + NEXT >>
>> EVAL
>>
DOLIST
>>
>>
DOLIST
>>
>>
This comes in at 241 bytes.
Using << "ABC" -> m << TICKS m PRMS TICKS ROT - >> >> as my test timer
I'm averaging over 10 tests (6265 6268 6308 6346 6268 6308 6332 6266 6258 6316)
6293.5 ticks, or .76825s.
185.148 byte_secs
joe...@usa.net
Erwann ABALEA's program 'PERMS': 243.5 bytes, 32 seconds.
Hubert Canon's program 'PERMUT': 173.0 bytes, 33 seconds.
TinyWanda's proposed program: fun idea but impractical
(similar in spirit to BOGOSORT; see it on Goodies Disk #8).
My current best (beat this!) is: 153.5 bytes, 4.5 seconds.
It runs "ABCDEF" in 25.6 seconds. It's not recursive, so it can
be named anything you wish.
For the hackers out there, it uses (among other things) a nifty
trick suggested by Richard Nelson: A fast way to obtain all the
possible *rotations* of any string is to append the string to
itself and then loop through that, SUBbing out successive chunks:
Concept:
"ABC/" --> "ABC/ABC/"
^--^ -------> "ABC/" \
^--^ ------> "BC/A" \ All the possible
^--^ -----> "C/AB" / rotations of "ABC/"
^--^ ----> "/ABC" /
Input: "ABC/"
Run: << DUP DUP + 1 ROT SIZE DUP 4 ROLLD START DUP 1 4 PICK SUB
3 ROLLD 2 OVER SIZE SUB NEXT DROP2 >>
Output: "ABC/"
"BC/A"
"C/AB"
"/ABC"
I'll post the complete MC program if nobody beats 153.5 bytes,
"ABCDE" in 4.5 seconds, "ABCDEF" in 25.6 seconds.
dbac...@ionet.net
Actually, I considered playing with rotations but I got lost
in considerations of how to be sure all permutations came up.
Trimmed my beastie a bit from last night, but still it isn't
getting anywhere near Mr. Horn's program. Still, for what it
is worth:
<< DUP 1 SWAP SIZE
FOR i
DUP i DUP SUB SWAP
NEXT SIZE ->LIST {""} SWAP 1
<< -> C
<< 1
<< C
<< -> S D
<< 0 S SIZE FOR i S 1 i SUB D + S i 1 + S SIZE SUB + NEXT >>
>> EVAL
>> DOLIST
>>
>> DOLIST
>>
This comes in at 216.5 bytes.
Using << "ABC" -> m << TICKS m PRMS TICKS ROT - >> >> as my test timer
I'm averaging over 10 tests 6130.9 ticks, and for "ABCDE" it comes in
at an average of 64829.s ticks (7.913 secs). Unfortunately, I don't
think this approach is going to yield much in the way of getting down
to Mr. Horn's stunning results. Oh well, on that long drive to Amarillo
I may think of something. If this isn't over by Friday, I'll try to
post something new.
Donald
TinyWanda
Darn that Joe Horn. . .how does he get his programs so short?!?
Actually, I considered playing with rotations but I got lost
in considerations of how to be sure all permutations came up.
it seemed to me that it was always a folding program...
if you could figure out how to fold it just right, it could become a very short
loop...???
( i'm working on my chrstmsa wee-books and i can't concintrate on ANYTHING...!
)
----------- :: o
.---..-..-..-..-..-..-. . .-. .-. .-..-..-.. .-.
`| |'| || .` | > / \ \/ \/ / / \ | .` || | ) / \
`-' `-'`-'`-' `-' `. ^ .' `--^--'`-'`-'`-'' `--^--'
Join The BabyNous Cult : The Friendly Neighborhood Cult
joe...@usa.net
%%HP: T(3)A(D)F(.);
@ ARR$ by Joe Horn, 2 Dec 1998.
@ Input: String
@ Output: List of all its rearrangements.
\<< DUP HEAD 1 \->LIST SWAP TAIL SWAP 1 3 PICK SIZE
FOR j OVER j DUP SUB ADD 1
\<< DUP DUP + 1 ROT SIZE DUP 4 ROLLD
START DUP 1 4 PICK SUB 3 ROLLD 2 OVER SIZE SUB
NEXT DROP2
\>> DOSUBS
NEXT SWAP DROP
\>>
BYTES: #64B3h 153.5
Execution time: Handles "ABCDEF" in 25.4 seconds.
+---------+
| CONCEPT | for processing a string beginning with "ABCD"
+---------+
Start with "A". Now insert "B" into all the possible positions
(namely, in front and behind) as shown in this diagram:
A
^ ^
B B
This yields BA and AB, the only two possible arrangements of AB.
Now take those and insert C into all the possible positions, as shown
in this diagram:
B A A B
^ ^ ^ ^ ^ ^
C C C C C C
This yields CBA, BCA, BAC, CAB, ACB, and ABC, the six possible
arrangements of ABC. Now do the same thing for "D":
C B A B C A B A C C A B A C B A B C
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
D D D D D D D D D D D D D D D D D D D D D D D D
This yields the 24 possible arrangements of ABCD.
The process is repeated for each remaining letter (if any).
+-------+
| TRICK |
+-------+
Rather than *inserting* each character into the string, it's faster to
merely add it to the front and then *rotate* the string to obtain all
the other positions of the character. This yields a different order of
the final strings, but that's okay since the order doesn't matter as
long as all the possible rearrangements are generated, which they are.
Example:
Rather than doing this,
B A A B
^ ^ ^ ^ ^ ^
C C C C C C
merely do this instead:
B A A B
^ ^
C C
CBA DUP + --> CBACBA
^^^----> CBA
^^^---> BAC
^^^--> ACB
CAB DUP + --> CABCAB
^^^----> CAB
^^^---> ABC
^^^--> BCA
Thus we obtain CBA, BAC, ACB, CAB, ABC, and BCA, the six possible
arrangements of ABC.
Notice that the order of these six strings is different from the order
shown under "CONCEPT" above, but none are repeated and none are
missing, and that's all that matters.
-Joe-
werner_h...@my-dejanews.com
@ bytes: 122.0
@ check: # EE7Fh
@ timing: "ABCDEF" 23.95_secs (jkh's took 27.41_secs on EMU48)
\<<
{ "" }
OVER SIZE 1 SWAP
FOR j
OVER j DUP SUB ADD
1
\<<
DUP +
1 j
START
TAIL DUP 1 j SUB SWAP
NEXT
DROP
\>>
DOSUBS
NEXT
SWAP DROP
\>>
--
Best Regards,
Werner Huysegoms
Reply-To: werner.h...@dgx11.cec.be
remove the x before replying