Page 1 of 2 12>
Topic Options
#163383 - 2006-06-17 12:34 AM Find In Array
Gargoyle Offline
MM club member
*****

Registered: 2004-03-09
Posts: 1597
Loc: Valley of the Sun (Arizona, US...
Hope that I explain this sufficiently.

I have an array with 55 elements. Each of these elements contain a number. The numbers could be anything from 0 to infinity. Some #'s could be duplicated.

Out of the 55 elements I would like to select the 5 smallest values, and am having problems with the logic to do so. Would prefer to store the 5 smallest elements in another array for easy reference if possible.


Dont need exact code, but some pointers.
Thanks
_________________________
Today is the tomorrow you worried about yesterday.

Top
#163384 - 2006-06-17 01:08 AM Re: Find In Array
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11625
Loc: CA
Could you post a small sampling of this data in question please.

or if it really is that easy since it's in an array just feed it to QS (Quick Sort) UDF and it will sort the smallest ones for you in the beginning.

Top
#163385 - 2006-06-17 01:30 AM Re: Find In Array
Gargoyle Offline
MM club member
*****

Registered: 2004-03-09
Posts: 1597
Loc: Valley of the Sun (Arizona, US...
A sample...
Element # 1 = 79
Element # 2 = 90
Element # 3 = 85
Element # 4 = 91
Element # 5 = 98
Element # 6 = 95
Element # 7 = 82
Element # 8 = 83
Element # 9 = 97
Element # 10 = 93
Element # 11 = 78
Element # 12 = 87
Element # 13 = 85
Element # 14 = 88
Element # 15 = 95
Element # 16 = 96
Element # 17 = 89
Element # 18 = 80
Element # 19 = 92
Element # 20 = 91
Element # 21 = 75
Element # 22 = 90
Element # 23 = 80
Element # 24 = 83
Element # 25 = 78
Element # 26 = 100
Element # 27 = 93
Element # 28 = 84
Element # 29 = 83
Element # 30 = 88
Element # 31 = 85
Element # 32 = 91
Element # 33 = 79
Element # 34 = 91
Element # 35 = 100
Element # 36 = 83
Element # 37 = 90
Element # 38 = 83
Element # 39 = 92
Element # 40 = 96
Element # 41 = 97
Element # 42 = 99
Element # 43 = 93
Element # 44 = 89
Element # 45 = 98
Element # 46 = 82
Element # 47 = 75
Element # 48 = 94
Element # 49 = 89
Element # 50 = 47
Element # 51 = 33
Element # 52 = 33
Element # 53 = 27
Element # 54 = 14
Element # 55 = 7
_________________________
Today is the tomorrow you worried about yesterday.

Top
#163386 - 2006-06-17 01:59 AM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Code:
$previousstate = SetOption( "NoVarsInStrings", "ON" )

dim $A[9]
$A[0] = 1
$A[1] = 7
$A[2] = 3
$A[3] = 4
$A[4] = 5
$A[5] = 5
$A[6] = 7
$A[7] = 2
$A[8] = 1
$A[9] = 1

$sorted = qs($A)

for each $x in $sorted
? $x
next
?
for each $x in GetFirstFiveUnique($A)
? $x
next

function GetFirstFiveUnique($Array)
dim $i, $x, $y, $sorted, $Result[0]

$sorted = qs($Array)
$x = 0
for $i=0 to ubound($sorted)

if $i=0
$Result[0] = $sorted[0]
$x = 1 + $x
endif
if $i > 0
if $Result[$x-1] <> $sorted[$i]
Redim Preserve $Result[$x]
$Result[$x] = $sorted[$i]
$x = 1 + $x
endif
endif
if $x = 5
$i = 1 + ubound($Array)
endif
next
$GetFirstFiveUnique = $Result

endfunction


function qs($a)
DIM $b[32],$c[32],$d,$e,$f,$g,$h,$i,$j,$k,$l
$b[0]=0
$c[0]=UBOUND($a)
$d=0
While $d >=0
$e=$b[$d]
$f=$c[$d]
While $e < $f
$h=$e+($f-$e)/2
$k=$a[$e]
$A[$e]=$A[$h]
$A[$h]=$k
$i=$e+1
$j=$f
$l=0
Do
While ($i<$j) AND $A[$e] > $A[$i]
$i=$i+1
Loop
While ($j>=$i) AND $A[$j] > $A[$e]
$j=$j-1
Loop
IF $i>=$j
$l=1
ELSE
$k=$A[$i]
$A[$i]=$A[$j]
$A[$j]=$k
$j=$j-1
$i=$i+1
ENDIF
Until $l=1
$k=$a[$e]
$a[$e]=$a[$j]
$a[$j]=$k
$g=$j
If $g-$e <= $f - $g
If $g+1 < $f
$b[$d]=$g+1
$c[$d]=$f
$d=$d+1
Endif
$f=$g-1
Else
If $g-1 > $e
$b[$d]=$e
$c[$d]=$g-1
$d=$d+1
Endif
$e=$g+1
Endif
Loop
$d=$d-1
Loop
$qs=$a
Endfunction



Edited by Howard Bullock (2006-06-17 02:13 AM)
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163387 - 2006-06-17 02:48 AM Re: Find In Array
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11625
Loc: CA
Quote:

Dont need exact code, but some pointers.






Now look what you've gone and done Howard. LOL


Top
#163388 - 2006-06-17 03:44 AM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
That seemed like the easiest pointer I could provide...
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163389 - 2006-06-17 08:25 AM Re: Find In Array
Gargoyle Offline
MM club member
*****

Registered: 2004-03-09
Posts: 1597
Loc: Valley of the Sun (Arizona, US...
Upon further reflection of this, I realize what I need is the Element #'s and not the data in the element. Just need to anaylyze the data and grab the corresponding Element #.

I am sure with a lot of contemplation, I will eventually be able to convert the premise of what Howard did to get what I need.
_________________________
Today is the tomorrow you worried about yesterday.

Top
#163390 - 2006-06-17 08:41 AM Re: Find In Array
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4557
Loc: USA
I think $i all you need then... just change Howards code to collect $i values into an array.
Top
#163391 - 2006-06-17 02:43 PM Re: Find In Array
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
hmm...
not think hoby's code will work.
one has to drop the sorting altogether.
_________________________
!

download KiXnet

Top
#163392 - 2006-06-17 03:31 PM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Yes... If he needs the element numbers of the original array, the sorting will be a problem. Also, if that is the case, he would need to specify how to handle the duplicates values. Should all of them be reported etc.
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163393 - 2006-06-17 03:33 PM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
What analysis are you doing? What is the real issue that needs to be solved?
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163394 - 2006-06-17 04:10 PM Re: Find In Array
Les Offline
KiX Master
*****

Registered: 2001-06-11
Posts: 12734
Loc: fortfrances.on.ca
You could copy to a temp array and sort the temp array just to get the 5 target values. Once you have the targets, AScan() them in the original array to get the index.

Either that or convert to an array of arrays, saving the index into antoher dimension so that sort will preserve it.
_________________________
Give a man a fish and he will be back for more. Slap him with a fish and he will go away forever.

Top
#163395 - 2006-06-17 04:24 PM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
this seems to work...

Code:
$previousstate = SetOption( "NoVarsInStrings", "ON" )

dim $A[9]
$A[0] = 1
$A[1] = 7
$A[2] = 3
$A[3] = 4
$A[4] = 5
$A[5] = 5
$A[6] = 7
$A[7] = 2
$A[8] = 1
$A[9] = 1

$sorted = qs($A)

for each $x in $sorted
? $x
next
?
$UniqueArray = GetFirstFiveUnique($A)
for each $x in $UniqueArray
? $x
next


$answer = FindIndexes($A, $UniqueArray)
for $x=0 to ubound($answer,1)
? "Value of " + $answer[$x,0]
? "Is at these indexes: "
for each $index in $answer[$x,1]
" " + $index
next
?
next


function GetFirstFiveUnique($Array)
dim $i, $x, $y, $sorted, $Result[0]

$sorted = qs($Array)
$x = 0
for $i=0 to ubound($sorted)
if $i=0
$Result[0] = $sorted[0]
$x = 1 + $x
endif
if $i > 0
if $Result[$x-1] <> $sorted[$i]
Redim Preserve $Result[$x]
$Result[$x] = $sorted[$i]
$x = 1 + $x
endif
endif
if $x = 5
$i = 1 + ubound($Array)
endif
next
$GetFirstFiveUnique = $Result

endfunction


function FindIndexes ($OrigArray, $ArrayOfFive)
dim $results[4,1], $x, $y, $z

for $z=0 to ubound($ArrayOfFive)

dim $ElementIndex[0]
$y=0
for $x=0 to ubound($OrigArray)
if $ArrayOfFive[$z] = $OrigArray[$x]
Redim Preserve $ElementIndex[$y]
$ElementIndex[$y] = $x
$y = 1 + $y
endif
next
$results[$z, 0] = $ArrayOfFive[$z]
$results[$z, 1] = $ElementIndex
$FindIndexes = $results
next
endfunction


function qs($a)
DIM $b[32],$c[32],$d,$e,$f,$g,$h,$i,$j,$k,$l
$b[0]=0
$c[0]=UBOUND($a)
$d=0
While $d >=0
$e=$b[$d]
$f=$c[$d]
While $e < $f
$h=$e+($f-$e)/2
$k=$a[$e]
$A[$e]=$A[$h]
$A[$h]=$k
$i=$e+1
$j=$f
$l=0
Do
While ($i<$j) AND $A[$e] > $A[$i]
$i=$i+1
Loop
While ($j>=$i) AND $A[$j] > $A[$e]
$j=$j-1
Loop
IF $i>=$j
$l=1
ELSE
$k=$A[$i]
$A[$i]=$A[$j]
$A[$j]=$k
$j=$j-1
$i=$i+1
ENDIF
Until $l=1
$k=$a[$e]
$a[$e]=$a[$j]
$a[$j]=$k
$g=$j
If $g-$e <= $f - $g
If $g+1 < $f
$b[$d]=$g+1
$c[$d]=$f
$d=$d+1
Endif
$f=$g-1
Else
If $g-1 > $e
$b[$d]=$e
$c[$d]=$g-1
$d=$d+1
Endif
$e=$g+1
Endif
Loop
$d=$d-1
Loop
$qs=$a
Endfunction

_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163396 - 2006-06-17 05:46 PM Re: Find In Array
Gargoyle Offline
MM club member
*****

Registered: 2004-03-09
Posts: 1597
Loc: Valley of the Sun (Arizona, US...
The issue that I am trying to solve is to find the 5 smallest values (and yes duplicates are fine). Then present to the user the Element # as it is directly linked with other data.

Howard I will work with your code and report back probably on Monday.
_________________________
Today is the tomorrow you worried about yesterday.

Top
#163397 - 2006-06-17 06:14 PM Re: Find In Array
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
what about something like:
Code:

function indexes_of_smallest_values($array, $howMany)
dim $helper[0],$output[$howMany], $sc
for $=0 to ubound($array)
$val = $array[$]
if $val>ubound($helper)
redim preserve $helper[$val]
endif
$helper[$val] = $helper[$val] + " " + $
next
for $=0 to ubound($helper)
for each $index in split($helper[$])
if len($index)
$output[$sc] = $index
$sc = $sc + 1
endif
if $sc>$howMany
exit 0
endif
next
next
$index_of_smallest_values = $output
endfunction



it does not support negative numbers, but surely is shorter than the sorting scripts posted before...


Edited by Jooel (2006-06-20 06:47 AM)
_________________________
!

download KiXnet

Top
#163398 - 2006-06-18 03:27 PM Re: Find In Array
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11165
Loc: Boston, MA, USA
To find the five smallest values, sort the array in ascending order, e.g. via QuickSort, and use indexes 0-4 to retrieve the five smallest values.
_________________________
There are two types of vessels, submarines and targets.

Top
#163399 - 2006-06-18 04:47 PM Re: Find In Array
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
jens, sorry but you clearly didn't read the issue.
_________________________
!

download KiXnet

Top
#163400 - 2006-06-19 11:14 PM Re: Find In Array
Gargoyle Offline
MM club member
*****

Registered: 2004-03-09
Posts: 1597
Loc: Valley of the Sun (Arizona, US...
Jooel,
In looking over your snippet, I assume that I need to assign $array, to whatever my array is, and that $output is the array that now holds the indexes of the of smallest values.
_________________________
Today is the tomorrow you worried about yesterday.

Top
#163401 - 2006-06-20 04:06 AM Re: Find In Array
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Have you executed my latest code?

Code:
c:\data\scripts>..\kix\kix.450\kix32 test.kix

1
1
1
2
3
4
5
5
7
7

1
2
3
4
5

Value of 1
Is at these indexes: 0 8 9

Value of 2
Is at these indexes: 7

Value of 3
Is at these indexes: 2

Value of 4
Is at these indexes: 3

Value of 5
Is at these indexes: 4 5

c:\data\scripts>

_________________________
Home page: http://www.kixhelp.com/hb/

Top
#163402 - 2006-06-20 06:45 AM Re: Find In Array
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
gargoyle, yes you assume right...
_________________________
!

download KiXnet

Top
Page 1 of 2 12>


Moderator:  Jochen, Allen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Arend_, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 323 anonymous users online.
Newest Members
Audio, Hoschi, Comet, rrosell, PatrickPinto
17880 Registered Users

Generated in 0.072 seconds in which 0.024 seconds were spent on a total of 13 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org