cancel
Showing results for
Did you mean:
Level 4
138 92 2 5
Message 1 of 14
2,214
Flag Post

Solved!

HP Recommended
HP 50g graphing calculator

Hi dear HP community ,

I have one question for you and that is for someone who well knows how to programme in HP 50g graphing calculator very easy.

So , my first problem is how to print elements from lists which repeats in input list like this { a b b c d e e e a a a b c d d g } in form of non repeating elements in output list . Outputted  list ( above written ) should look in a way like this { a b c d e g } . There is no matter about order in outputted list , its only matter that output list contain all elements from the input list but without any repeating

My second problem , or ask is how to sort elements in list in ascending or descending order from original input list.

So if i have list , as example like this one , as input list : { 1 3 5 4 3 2 1 3 4 2 3 4 2 1 10 }  i want to create a output list to look like this from those ( or similar ) elements : { 1 1 1 2 2 2 3 3 3 3 4 4 4 5 10 }  ( this is in ascending order ).

I would recommend selection sort because it's most easiest ... or i think so ... but I don't know how to do these thing in User RPL when programming on HP 50g graphing calculator.

Please if someone know how to do this I will be very very grateful because I really don't know how to do any of these

thing even I think it's a very basic stuff 🤔🙄

So , i want to know how to do both of these described problems , I hope that you understand my bad english ... sorry about that... if you did not understand well what I'm trying please reply and i will do my best to explain at the best way ,  but first please heeeelp !!

Best regards 🤗

Josip Kova

Tags (1)
1 ACCEPTED SOLUTION

Accepted Solutions
Level 8
641 628 121 214
Message 11 of 14
Flag Post
HP Recommended

@JKova wrote:

My goal is to do INSERTION SORT which takes a list , of course UNSORTED LIST  , from the stack and returns SORTED LIST on the stack or memory  ( if not possible with stack operations )  or so.

Ok, here's what you were looking for: A 100% standard User RPL program which uses stack operations to sort a list of numbers using the Insertion Sort algorithm, optimized with a binary search.  Two local variables are used, one to store the size of the original list, and one as the counter in the FOR-NEXT loop.  In a nutshell, the list is exploded onto the stack, then all the sorting is performed on the stack, and when the stack is all sorted, the numbers on the stack are placed back into a list.  Therefore, while the work of sorting is being performed, there are no lists or arrays of any kind either on the stack nor stored in a variable.

Input: List of numbers.

Output: Same list, sorted into ascending order.

Speed: Sorts 128 random reals in 9 seconds; 128 random integers in 35 seconds.

This program is useful only for study purposes, since the built-in SORT command (which uses the same logic as this program) is roughly 8 times faster.

« OBJ→ → s « 1. s FOR j s ROLL 0. j

WHILE DUP2 SWAP – 2. / IP DUP

REPEAT OVER SWAP – DUP 4. + PICK 5. PICK

IF > THEN UNROT END SWAP DROP

END ROT DROP2 ROLLD NEXT s →LIST » »

-Joe-
Tags (1)
13 REPLIES 13
Level 8
641 628 121 214
Message 2 of 14
Flag Post
HP Recommended

(1) The 50g has a built-in but hidden system command which removes all duplicates from any list.  Just make sure that your list is on level 1 of the stack, and then execute this:

#2FD006h FLASHEVAL

This will replace the list with a version of the list which has all duplicates removed.  Warning: Like most hidden system commands, this command performs no safety checks, so make sure that there is a list on level 1 before executing this command.  Executing it with anything else (or nothing) in level 1 may cause unwanted results, including memory loss.  Be sure you specify the hex number #2FD006h exactly, or Bad Things Will Happen.

If you'd prefer to use 100% User RPL and avoid using hidden system commands, the following routine does the same as above, namely, it takes any list and returns it with all the duplicates removed.

OBJ→ { } 1. ROT START SWAP IF DUP2 POS THEN DROP ELSE + END NEXT REVLIST

It simply starts with an empty list, then adds the original elements to it unless they are already there.  Single-stepping it on a short list will help you understand how it works.   Hopefully other folks reading this thread will submit shorter, faster, and more clever alternatives. For me, the most fun aspect of RPL is that there are usually many ways to program any given task.

(2) Have you tried the SORT command?  There are faster sorting routines available at hpcalc.org but for small lists SORT is probably fast enough.

-Joe-
Level 4
138 92 2 5
Message 3 of 14
Flag Post
HP Recommended

Hi dear Joe ,

I'm really glad that You answered on any of those really problems for me which bothers my mind right now.

(1)  First of all thanks for code ... for this particular problem which i described on my first post and most importantly thanks for advice that i can use #2FD006h FLASHEVAL for doing same thing.

I think that YOU ARE REALLY PRO !!

Because even I did not know if is that possible to solve on any way with a little of code or not but anyway ... and you did it !! CONGRATULATIONS !!!

(2) I must to say ( in this case write ) that i did not use SORT command for this problem - 2.nd in the row which i described in my previous post.

I don't know how SORT command actually works but it is usefull to know that those type of command exist for doing such things.

If you can describe that would be nice 🙂

But also , thing  that i want to know is how to do some easy sorting - like SELECTION SORT.

I tried to do this but i don't know how to swap ( or replace ) an iterator j with index of minimun element in the list and also few other things which in common programming languages like Python , Java , C++ and so on will probably work.

So what I'm trying to do is described in the link below :

https://www.geeksforgeeks.org/selection-sort/

Also , i used selection sort because it is quite , on my opinion  , easy to learn. And I also used it for school ( or college ... university ).

So I'm wondering how to do that , particulary with HP 50g graphing calculator and using User RPL 🤔🙄

Thanks for your answer , or who knows answer thanks to them ... in forward way .

Best regards ,

Josip Kova

Level 8
641 628 121 214
Message 4 of 14
Flag Post
HP Recommended

> I don't know how SORT command actually works but it is useful to know that those type of command exist for doing such things. If you can describe that would be nice.

• If you mean, "How does SORT work in a program?" the answer is: Just put the list on the stack and execute SORT. That's all. To sort backwards, use SORT REVLIST.
• If you rather mean, "What algorithm does the SORT command use internally?" the answer is: It uses the insertion-sort algorithm, using a binary search to find each element's new position.

You ask about finding the minimum value in a list.  That's easy:

« MIN » STREAM

To find the index of the minimum value:

DUP « MIN » STREAM POS

You also ask about how to insert and swap elements in a list. It's doable but there's a faster and easier way: Convert the list into a vector using the AXL command, then use the built-in vector commands COL+ to insert a value, COL- to delete a value, and CSWP to swap two elements.  Then (if desired) you can convert the vector back into a list by executing the AXL command again.

Example: Take the list { 11 22 33 44 55 }, delete the 3rd element, then insert 99 into position 2, and then swap positions 4 and 5.

{ 11 22 33 44 55 } AXL --> [ 11 22 33 44 55 ] (it has changed into a vector)

3 COL- DROP --> [ 11 22 44 55 ]

99 2 COL+ --> [ 11 99 22 44 55 ]

4 5 CSWP --> [ 11 99 22 55 44 ]

AXL --> { 11 99 22 55 44 } (it has changed back into a list)

Using the above tools to create a program that uses the Selection Sort algorithm is left as a learning opportunity for the student.  If you get stuck on any step, we're here for you.

Disclaimer: I still don't work for HP, or anybody else.

-Joe-
Level 4
138 92 2 5
Message 5 of 14
Flag Post
HP Recommended

Hi dear Joe Horn and others ,

Joe , thanks for your advice that you mentioned in previous post.

Unfortunately , i did not get selection sort algorithm right.

I also used a geeks for geeks webpage for help but ... it does not help too much , for me of course .. I'm not telling that webpage is bad or so but i did not get it correctly .

This is what I done with selection sort algorithm  ( picture below ) and don't be fooled because it's not working correctly ...

Although i don't know how to setup two FOR loops correctly because I need to swap those elements and also it's necessary to enable that loop repeats correctly.

I't seems that i have classical problems with programming but i don't know 🤔

Anyway here is my code ...

Also i tried to made a distinction , or maybe relation between what i'm trying to do and what i look on , by me very useful page which i found on internet. Btw , i do not advertise that page but I used it a lot for those things.

This is a code which i rely on when trying to do some programming.

this is a code from which i want to figure out how to create a code in User RPL

above mentioned code is for C++ but anyway

Also i tried to figure out flowchart for this particular problem but with no success , man ... i think that I'm so stupid or so but I don't get it right now ... how to do this ... here is an example for used flowchart , in my case ...

This is an example of selection sort flowchart which i used

That is it , i don't know what else i must to add , but the fact is that i don't know how to make this selection sort algorithm for HP 50g graphing calculator.

I really don't know ... if someone knows how to do this ... how to make this algorithm ( SELECTION SORT ) directly for HP 50g graphing calculator

in User RPL  .

Tnaks for effort 🙂

Have a nice day ,

Josip Kova

Level 4
138 92 2 5
Message 6 of 14
Flag Post
HP Recommended

If anyone knows how to do coding for selection sort on HP 50g graphing calculator by using User RPL please write here ,

Bye 🤗

Level 6
140 139 29 60
Message 7 of 14
Flag Post
HP Recommended

Hi Josip -

The gist of the selection sort algorithm is simply "repeatedly take the smallest element in the list until there's only one left, then take that one as the final element". There are many ways to implement this, some including the use of swaps to reduce the memory footprint. In RPL, swaps don't actually save any memory due to the way objects are created and deleted (copies are made any time an object is altered).

Here's one way to implement a selection sort in pure User RPL. This works with lists of 2 or more elements, but will fail with 0 or 1 element (I didn't include the checks for that just to keep things simple). This method uses a couple of the hints that Joe gave you above:

• DUPDUP << MIN >> STREAM POS to find the index of the smallest element
• temporarily converting the list to an array for more efficient manipulation with indices
``````\<<
@ result list starts with no elements
{ } SWAP

@ determine size of source list (count of elements)
DUP SIZE

@ process elements 1..(count-1)
1. SWAP OVER - START

@ get the index of the smallest element in the current list
DUPDUP \<< MIN \>> STREAM POS

@ extract the identified element
SWAP AXL SWAP COL-

@ append that element to the result list
ROT SWAP +

@ convert array back into a list and reposition for next iteration
SWAP AXL

NEXT

@ add final element to result list
+
\>>``````

I also couldn't help but notice in another post that you have the List Extensions library installed. Using commands from that library, you could shorten the code somewhat and speed up the process at the same time. The following shows an alternate approach (in particular using a WHILE-REPEAT-END loop instead of the START-NEXT one used above). The code is not only smaller (68.5 bytes vs. 97 bytes), but also faster. It also allows you to sort strings as well as numbers, since LMIN works with strings and MIN does not. It inherently works with lists of 0 or more elements, so no additional code is needed for handling 0 or 1 element.

``````\<<
@ result list starts with no elements
{} SWAP

@ repeat until the working list is empty
WHILE
DUP SIZE
REPEAT

@ find position of current smallest element
DUPDUP LMIN POS

@ extract found element
DUP2 GET UNROT

@ remove found element from working list
LRMOV UNROT

@ add found elements to current result
+ SWAP
END

@ drop the working list, leaving result on stack
DROP
\>>``````

While on the subject of ListExt, there's also some useful commands that implement the grouping functions you mentioned in your original question. In particular, see LGRP, LRPCT, and LDDUP. In particular, LDDUP is similar to the #2FD006h FLASHEVAL combination in that it creates a result list of the unique elements from a given source list in the same order they were encountered. The biggest difference is that LDDUP completes much faster as the list size grows.

I hope this gives you some ideas!

Level 4
138 92 2 5
Message 8 of 14
Flag Post
HP Recommended

Hi David_M ,

Thanks you for your answer !! And explanation how to do those things .

By the way I also figure out how to deal with those "problems" or maybe for me problems because on the other side I would not write what I want here on HP community.

So , this problem about selection sort I solved on "my way" , when i mean on my way I actually did not know how to make algorithm and even If i looked at the algorithm i did not know how to implement those knowledge , so after few days ... i mean not now but before few days. Hope that you understand me.

So this is my solution for selection sort and it does includes a global variables too , although i think that your algorithm David_M is much much better and your algorithm also proves that you have much knowledge than I have so far.

Also my code for this takes list from the stack and then through algorithm you basically get an output list in form of global variable stored in memory of HP 50g graphing calculator. I know that is not best approach to do like this but after all I was happy to see that algorithm do the work , it ordered a list of numbers from smallest to biggest or vice versa.

I rely on this web page when coding :

https://www.geeksforgeeks.org/selection-sort/  ( replicated code which was written in C++ )

Here is code for that selection sort

my algorithm for selection sorting

Also i have issues with posting a code , and also this HP Support forum seems as something unreliable when i use that external options as pictures , code , links and so on ... or i think so but i also get few problems with those forum.

Anyway here is what my code does simply takes a list from the stack then converts a input list which I named as

"listaul"  into outputted list which I named "listai"  then from there i used two for loops .

Outer for loop simply counter which i named with  converts to variable min and those variable actually represents nothing else but an index of element which will be , as algorithm goes on , compared to the others as the "minimum element"

I don't know what i done with this its basically just a index of element in unsorted list , known as input list.

In inner FOR loop i get second counter which i named with  and there is a condition IF the element taken from list at inner loop counter is smaller then outer loop counter then swap the position with those element countered by outer loop... in other words i and j simply swap their positions and i do it from this function listai AXL j min CSWP AXL 'listai' STO also if this not a case i used a set of functions or commands described after using ELSE command on my code.

Simply swap the elements , that's all.

Also i  manage to do a insertion sort and I do it a lot easier than selection sort , also i figure out that insertion sort is much faster on physically HP 50g graphing calculator than selection sort and when you increase elements of list the time difference between two of those algorithms for sorting gets bigger and bigger .

Also this is the algorithm which i used for a insertion sort.

Also i did it on the same way like selection sort and it also same elements which will be stored in memory of HP 50g graphing calculator, I know that is not maybe convenient way because you use memory instead of using as example stack.

Also I followed instructions from this source and tried to replicated a code which was written in C++ . Source which i used is :

https://www.geeksforgeeks.org/insertion-sort/

Ok , I do selection sort and insertion sort in some way like Joe Horn described , which using functions like CSWP and AXL

Also i stored a key , outputted list and counter variable j in memory of HP 50g graphing calculator.

This is my source code for INSERTION SORT

my code for insertion sort

lista is outputted list ( sorted list at the end ) , and list is input list ( unsorted input list )

So , my another question for you dear David_M and maybe all HP community including experts ,

Can you make a INSERTION SORT to look much smarter than this which I mentioned ( above ) and If possible without using elements which will be stored in memory of HP 50g graphing calculator also all that done with using a knowledge of User RPL and not adding some special commands or so ?

Also i found that INSERTION SORT WITH BINARY SEARCH perform much better and faster than INSERTION SORT without it so if someone knows an algorithm how to done that , or simply put the algorithm to HP Community it will be really nice 😎

OF COURSE FOR HP 50G GRAPHING CALCULATOR !!

Hope that you understand what I asking You with this post ,

I'm hoping for fast solution for INSERTION SORT ( SMARTER THAN MINE IF POSSIBLE - withuout using a global variables  ) or even more advanced BINARY SEARCH INSERTION SORT but without using SORT FUNCTION !!

Thanks for your time and understanding ,

Best regards ,

Bye 🤗

Level 8
641 628 121 214
Message 9 of 14
Flag Post
HP Recommended

JKova, please consider the following to be a kind of "intermediate reply" to your request.  It is not a complete Insertion Sort program, but it seems to me that your real goal is to LEARN RPL. The following will hopefully assist in that.

One vital step in an insertion sort is (as the name implies) the task of inserting a new number into an already-existing list of numbers.  The following RPL program called 'INSERT' takes any list, any object, and a position number, and inserts that object into that list at that position. Notice that it follows your request to use no variables at all, just stack operations, and 100% standard User RPL. 'INSERT' was featured on HP48 Goodies Disk #8 way back in 1993.

EXAMPLE: Insert 'X' into { 9 8 7 6 5 } at the 2nd position.

{ 9 8 7 6 5 } 2 'X'
INSERT --> { 9 X 8 7 6 5 }

Here's the RPL listing for 'INSERT':

« ROT OBJ→ 1 + DUP 1 + ROLL OVER DUP 3 + ROLL - 2 + ROLLD →LIST »

Lots of stack juggling going on there!  Busy stack manipulations are often semi-jokingly referred to by RPL programmers as "stackrobatics".  The only way to successfully program stackrobatics, or understand them later, is by writing out what's called a "stack analysis", which shows every step of the program and its corresponding stack contents.  A complete stack analysis for 'INSERT' can be found HERE.

Another vital step in an insertion sort is performing a binary search to find where the new item belongs in the already-sorted list.  The following RPL program called 'INSORT' does this, and then it inserts the new item into the list at that position.  Once again, it's 100% normal User RPL and uses no variables.

Example: { 5 7 9 11 13 } 10 INSORT
-- > { 5 7 9 10 11 13 }

Here's the RPL listing for 'INSORT':

« SWAP OBJ→ DUP 2 + ROLL OVER 6 + 5
WHILE DUP2 - 1 >
REPEAT DUP2 + 2 / CEIL DUP PICK 5 PICK
IF >
THEN SWAP DROP
ELSE ROT DROP SWAP
END
END DROP 4 -
ROLLD 1 + →LIST »

Even more stackrobatics here!  I do not have its stack analysis saved anywhere, so you'll have to map it out on your own. However, some useful info might be gleaned from its writeup HERE.  'INSORT' was featured on HP48 Goodies Disk #10 in 1995.

In case you were wondering, YES, it takes time and effort to write programs like this. The end result is such a small program that it LOOKS like it was easy to write... but the stack analysis must be done very carefully or the program won't work.  THAT is why I have not replied to your request for a complete Insertion Sort in 100% standard User RPL without using local variables; it would take a bigger unbroken block of time than I have right now.  Maybe next week, if I'm lucky. Meanwhile, PLEASE study the stack analysis for 'INSERT', and perform a stack analysis for 'INSORT'.  I promise you that it will be time well spent.

Happy Programming!

-Joe-
Level 4
138 92 2 5
Message 10 of 14
Flag Post
HP Recommended

Hi Joe my friend ,

Thanks for binary search algorithm !!

Also i like your word which you describe as "stackrobatics" , it's similar word to acrobatics. Very nice.

( i cut the other parts of your message and just remain this text with those word )

@Joe_Horn wrote:

Lots of stack juggling going on there!  Busy stack manipulations are often semi-jokingly referred to by RPL programmers as "stackrobatics".  The only way to successfully program stackrobatics, or understand them later, is by writing out what's called a "stack analysis", which shows every step of the program and its corresponding stack contents.  A complete stack analysis for 'INSERT' can be found HERE.

I'm really  thankful for other information's like links which you shared with me 😊

But , the real thing is that I need more knowledge , Yes , i know that so much knowledge if I want to perform those stackrobatics , i think so 🤔

Unfortunatelly your advices is not so applied , what does matters ,  in terms of my program except those binary search solution even with this binary search I can not ... or i don't know right know hot to properly implement those things in algorithm which i described. Do you maybe have a solution how to do that ?  If any have solution how to do these things or don't know any suggestion ... than thanks !!

My goal is to do INSERTION SORT which takes a list , of course UNSORTED LIST  , from the stack and returns SORTED LIST on the stack or memory  ( if not possible with stack operations )  or so.

I appreciate what you done Joe_Horn with your post and that are  really thankful advice's to after all , to be honest .

Don't think that I fooled you or so , that is not my intention. I see that you are really PROFESSIONAL and no doubt about that   ... and also on the other hand i see that I'M GREAT "NOOB"

I give you kudos !! You earn it !!

Thanks and bye 🤗

J.K.

† The opinions expressed above are the personal opinions of the authors, not of HP. By using this site, you accept the Terms of Use and Rules of Participation