As exposed
here I need to shuffle elements in a list, I did not find anything useful already existing so I share my rough solution. If you have or know better ones, it would be great if you would share them
If you know existing libraries handling userRPL lists , please share!
20170418 update: created a directory (feel free to use the programs as you wish, but give feedback if you find improvements/errors/better solutions).
most updated code,
here.
Code:
%%HP: T(0)A(D)F(.);
@ alternative found online %%HP: T(3)A(R)F(.);
@ You may edit the T(0)A(D)F(.) parts.
@ The earlier parts of the line are used by Debug4x.
@ in npp, just select language "normal" to get rid of the highlight.
@ Operations on list, also trying to recollect previous utility functions done before
DIR
generalRemarks
"- the library is built out of necessity, so it assume good
usage, without much error checking and checks for corner cases.
It can be even substituted by an existing library if this exists,
it is found and it is reliable. If you know one, please share!
Contact me: pier4r on the museum of HP calculators forum!"
builtIn50gFunctions
"see 50g user manual chapter 8 and relative commands in AUR"
communityLibraries
"users on the hpmuseum.org/forum suggests goferlists10.zip"
IncListElFuncHelp
"input:
L3: a list
L2: position of the element
L1: increment to apply
output:
L1: list with incremented element"
IncListElFunc
\<<
@ program to increase the value of an element in a list
@ trying to use a bit more stack instead of list operations,
@ but still limiting it for maintainability.
@ Done, it worked. Total execution of single round robin, 50 iterations, 857 seconds
@ one iteration 17 seconds on avg.
@ input on the stack, see variables
@output, the list in input, modified, on the stack
0
\->
@external inputs
lList
@list
lPosV
@position of the element
lincV
@increase
@local var
numEl
\<<
lList OBJ\->
@list on the stack, with end part number of elements.
'numEl' STO
@now to access the element in position, starting from the back
@we need to do (numberOfelements - position) +1 steps.
numEl lPosV - 1 +
@the position on the stack to pick from the back
@we recall the element
ROLL
@Something like the following
@{ 1 2 3 5} 1 1 1
@2 (pos) 2 2 3
@ 3 3 5
@ 5 5 2
@ 4 (4-2+1)
@increment the value on the stack
lincV +
@roll it back, the same number of postions like before
@so to counter the previous roll.
numEl lPosV - 1 +
ROLLD
@recreate the list and leave it on the stack.
numEl
\->LIST
\>>
\>>
shuffleListHelp
"input:
L2: a list
L1: numbers of shuffles (affecting single elements)
output:
L1: shuffled list
remarks:
to work properly the number of shuffles should not be low,
like the number of elements should do it"
shuffleList
@ TODO: consider something like this http://www.hpmuseum.org/forum/thread-2889.html
@ the point is that one receives a list, it is not creating it from the start.
@ TODO: consider analyze the results to suggest a proper number of shuffles or to
@ implement a better algorithm.
\<<
@program that receives a list in input, and shuffles the elements
@returning the shuffled list in output on the stack
@arguments on the stack.
@ 2: list
@ 1: number of random elements to shuffle around
0
\->
@external inputs
inputList
noShuffles
@local var
numEl
\<<
@explode the list on the stack
inputList OBJ\->
@save the num of elements
'numEl' STO
@roll randomily the elements in the list
1 noShuffles
START
numEl RAND * 1 + IP
ROLL
NEXT
@build the list back
numEl
\->LIST
\>>
\>>
headListHelp
"input:
L1: list
output:
L2: list without head element
L1: head element"
headList
\<<
@given a list in input, leaves on level1 the first element
@ and on level 2 the rest of the list.
@0
@numEl
\->
@external input
list
@local input
@numEl
@elements in the list.
\<<
list OBJ\-> 1 - \->LIST
@reducing the number of elements of 1 for the new list
@we have the tail on level 2
SWAP
@now the head element is on the level 1 stack
\>>
\>>
listHeadHelp
"input:
L1: list
output:
L2: head element
L1: list without head element"
listHead
\<<
@given a list in input, leaves on level1 the rest of the list
@ and on level 1 the head of the list
@0
@numEl
\->
@external input
list
@local input
@numEl
@elements in the list.
\<<
list OBJ\-> 1 - \->LIST
@reducing the number of elements of 1 for the new list
@we have the tail on the level 1
@ head level 2
\>>
\>>
tailListHelp
"input
L1: list
output:
L2: remaining list without tail element
L1: tail element
"
tailList
\<<
@given a list in input, leaves on level1 the first element
@ and on level 2 the rest of the list.
0 @tailEl
\->
@external input
listV
@local input
tailEl
\<<
listV OBJ\->
@list exploded
2 ROLL 'tailEl' STO
@pick the tail from the stack, save it
1 - \->LIST
@reducing the number of elements of 1 for the new list
@we have the remaining list on level 1
tailEl
@ we have the tail element on level 1, level 2 is the remaining list
\>>
\>>
getRandomListHelp
"input:
L3: number of elements
L2: min value
L1: max value
output:
L1: a list of random elements between min and max value
with a size of number of elements"
getRandomList
\<<
@0
\->
@input
numElements
minValue
maxValue
@local var
@counter
\<<
\<<
maxValue RAND * IP minValue +
\>>
'counter'
1 numElements 1
@ from 1 to numElements, increment of 1
SEQ
\>>
\>>
getRandomListFromValuesHelp
"input:
L2: number of elements
L1: list of usable values
output:
L1: a list of random elements picked from the list
of usable values, with possible repetitions.
"
getRandomListFromValues
\<<
0 @listUsableVsize
\->
@input
numElements
listUsableV
@local var
listUsableVsize
@counter
\<<
listUsableV SIZE 'listUsableVsize' STO
@not sure if sequence calls the program in input
@multiple times
\<<
listUsableV
listUsableVsize RAND * IP 1 +
GET
\>>
'counter'
1 numElements 1
@ from 1 to numElements, increment of 1
SEQ
\>>
\>>
rotateListTailHelp
"input:
L2: list
L1: number of rotations
(the last elment becomes the first, the first becomes the second)
output:
L1: rotated list
"
rotateListTail
\<<
0 @numElements
\->
@input
listV
numRotationsV
@local var
numElements
\<<
listV OBJ\-> 'numElements' STO
1 numRotationsV
START
numElements ROLLD
NEXT
numElements \->LIST
\>>
\>>
addElementInListHelp
"input:
L3: input list
L2: new element
L1: element position (if just append needed, please use '+' builtIN function)
output:
L1: list with element added in wanted position
"
addElementInList
\<<
0 @numElements
\->
@input
inputList
newEl
newElPos
@local var
numElements
\<<
inputList OBJ\->
@explode list
'numElements' STO
@ then we move it in the wanted position
@ assuming that we want to add -1 in position 2
@ 1 2 3 4 5 -1
@ we have to go 5 levels of the stack over.
@ so (num elements + 1) - position + 1
newEl
numElements 1 + newElPos - 1 + ROLLD
numElements 1 + \->LIST
\>>
\>>
moveElementInListHelp
"input:
L3: input list
L2: element position
L1: new element position (within list size)
output:
L1: list with element moved from original position to new
position.
"
moveElementInList
\<<
0 @numElements
\->
@input
inputList
elPos
newElPos
@local var
numElements
\<<
inputList OBJ\->
@explode list
'numElements' STO
@ moving on the top of the stack the wanted element
@ notice that the position in the list is "reversed"
@ compared to the position of the list exploded on the stack
@ like { 1 2 3 4 5 } position 2 will be on stack level 4.
@ L5: 1, L4: 2, L3: 3, L2: 4, L1:5
numElements elPos - 1 + ROLL
@ then we move it in the wanted position
@ assuming that we picked the position 2
@ for example position 1 or position 2
@ 1 3 4 5 2 , 2 is not an input of ROLLD (the input of rolld is the num of levels)
@ position 2 is now 'numElements - wanted position + 1' with ROLLD
@ aka 5 - 2 + 1 = 4
@ 1 (2) 3 4 5
@ So like before, just with the wanted position
numElements newElPos - 1 + ROLLD
numElements \->LIST
\>>
\>>
selectionSortListAscHelp
"input:
L1: list to order
output:
L1: ordered list with smallest elements in the front, biggest in the rear
"
selectionSortListAsc
@ time complexity O(n^2), space, in place or O(1) considering the amount of additional memory.
@ en.wikipedia.org/wiki/Selection_sort
@ the tricky part is not using additional list as helpers.
@ 15:15 19.04.2017 works, but slow. I guess more pure stack operations are needed.
@trying to use LIST functions
\<<
0 @numElements
0 @remainingUnsortEl
0 @maxPos
0 @maxV
10 @uFbool
\->
@input
inputList
@localVar
numElements
remainingUnsortEl
maxPos
maxV
uFbool
\<<
inputList SIZE 'numElements' STO
@now we find the maximum of the remaining elements
numElements 1
FOR counter
@inputList \<< MAX \>> STREAM
@ streams takes the first two elements of a list, run the program
@ then takes the remaining elements one by one and for each run the same
@ program. A smaller version of DOLIST/DOSUBS
@ stream is not so usable, we don't have the position of the max
uFbool CF
@reset, it means that a new max has to be searched
inputList
\<<
\->
nextValue
\<<
IF
NSUB counter \<=
THEN
IF
uFbool FC?
THEN
@if max was never set so far
@first time for a new max
nextValue 'maxV' STO
NSUB 'maxPos' STO
uFbool SF
ELSE
@we have a valid maxV already
IF
nextValue maxV >
THEN
nextValue 'maxV' STO
NSUB 'maxPos' STO
END
END
END
\>>
\>>
DOSUBS
@ here we have the max value and the postion
@ so we move the positions
inputList
maxPos
counter
moveElementInList
'inputList' STO
-1 STEP
inputList
\>>
\>>
selSortListAsc2
@ like selection sort but with Stack operations instead of list
@ operations.
\<<
"TODO"
@nice way to leave notes around.
\>>
listOPusages
DIR
@####################################################
@ Processing lists
@ www.hpmuseum.org/forum/thread-8209.html
c1tester
\<<
{ } @timeList
{ } @positionCheckedList
\->
timeList
positionCheckedList
\<<
1 100
START
100 {3 5} getRandomListFromValues
'c1vaV1' TEVAL
@collect the timing
OBJ\-> DROP
'timeList' SWAP STO+
'positionCheckedList' SWAP STO+
NEXT
timeList
positionCheckedList
\>>
\>>
c1vaV1
\<<
@ given a list in input of 3 and 5, length 100+
@ if those are not alterated, the list is invalid
@ returning possible different values for statistics
1 @lastPosChecked
3 @uf3
5 @uf5
10 @ufInvalid
\->
@inputs
inputL
@local
lastPosChecked
uf3
uf5
ufInvalid
\<<
@flags as booleans
uf3 CF
uf5 CF
ufInvalid CF
@set the first value.
@ with if then else
IF
inputL 1 GET 3 ==
THEN
uf3 SF
ELSE
uf5 SF
END
inputL
\<<
\->
listEl
\<<
IF
NSUB 1 >
@we already used the first element
ufInvalid FC?
@ list not invalid
AND
THEN
CASE
listEl 3 ==
uf5 FS?
AND
THEN
uf5 CF
uf3 SF
END
listEl 5 ==
uf3 FS?
AND
THEN
uf3 CF
uf5 SF
END
@def
ufInvalid SF
END
END
IF
ufInvalid FC?
THEN
'lastPosChecked' 1 STO+
END
\>>
\>>
DOSUBS
@inputL
@
@IF
@ ufInvalid FS?
@THEN
@ "invalid"
@END
lastPosChecked
\>>
\>>
@####################################################
testing
\<<
testSortComp2
\>>
testSortComp
@comparing builtin sort functions
@with added sort functions
@ built in sort avg: 0.5 seconds for 50 elements
@ selectionSortResultList avg: 42.5 seconds for 50 elements. Not really fast
\<<
0 @sampleList
{} @sortResList
{} @selectionSortResultList
\->
@input
@local var
sampleList
sortResList
selectionSortResultList
\<<
50 1 100 getRandomList
'sampleList' STO
1 10
START
\<< sampleList SORT \>>
TEVAL
OBJ\->
@ break the tagged time
DROP
@drop the seconds
'sortResList' STO+
NEXT
1 10
START
\<< sampleList selectionSortListAsc \>>
TEVAL
OBJ\->
@ break the tagged time
DROP
@drop the seconds
'selectionSortResultList' STO+
NEXT
sortResList
selectionSortResultList
\>>
\>>
testSortComp2
@to test the sort of GoFerList library (see hpcalc.org)
@ avg result for a list of 50 random positive integers
@ 2.9 seconds
\<<
0 @sampleList
{} @goFerResList
\->
@input
@local var
sampleList
goFerResList
\<<
50 1 100 getRandomList
'sampleList' STO
1 10
START
\<<
sampleList
\<<
<
\>>
Sort
\>>
TEVAL
OBJ\->
@ break the tagged time
DROP
@drop the seconds
'goFerResList' STO+
NEXT
goFerResList
\>>
\>>
END
END
Another library often suggested in topics about list processing:
GoferList (one can find it on hpcalc too)
Check also
this post from DavidM.
Suggested search string:
site:hpmuseum.org list library OR function OR operation OR processing 50g
Search
Member List
Calendar
Help
/
(50g) (userRPL) additional operations with a list
