Bug 158976 - The "SF_Array.Shuffle" function does not place the end of the array at the end of the array
Summary: The "SF_Array.Shuffle" function does not place the end of the array at the en...
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: BASIC (show other bugs)
Version:
(earliest affected)
7.1.2.2 release
Hardware: All All
: medium normal
Assignee: Jean-Pierre Ledure
URL:
Whiteboard: target:24.8.0 target:24.2.1 target:7.6.5
Keywords:
Depends on:
Blocks:
 
Reported: 2024-01-02 14:44 UTC by nobu
Modified: 2024-01-24 14:35 UTC (History)
3 users (show)

See Also:
Crash report or crash signature:


Attachments
sample file (30.07 KB, application/vnd.oasis.opendocument.spreadsheet)
2024-01-02 14:45 UTC, nobu
Details

Note You need to log in before you can comment on or make changes to this bug.
Description nobu 2024-01-02 14:44:52 UTC
Description:
The "SF_Array.Shuffle" function of Scriptforge library does not place the end of the array at the end of the array.

Steps to Reproduce:
1. enter the "SF_Array.Shuffle" sample code in the Basic IDE.
https://help.libreoffice.org/latest/ja/text/sbasic/shared/03/sf_array.html?&DbPAR=BASIC&System=WIN#Shuffle

Dim a As Variant
a = SF_Array.Shuffle(Array(1, 2, 3, 4))
    ' Array "a" is now in random order, f.i. (2, 3, 1, 4)

2. execute the code

Or
Press the Run button of the calc file that contains the attached sample code. 


Actual Results:
3. the last "a(3)" in array "a" will never be "4"

Expected Results:
3. there is approximately a 25% chance that the value of "a(3)" will be "4"


Reproducible: Always


User Profile Reset: No

Additional Info:
Basic Code (SF_Array.Shuffle)

lMin = LBound(Array_1D)
lCurrentIndex = UBound(array_1D)
'	Initialize the output array
ReDim vShuffle(lMin To lCurrentIndex)
For i = lMin To lCurrentIndex
	vShuffle(i) = Array_1D(i)
Next i
'	Now ... shuffle !
Do While lCurrentIndex > lMin
	lRandomIndex = Int(Rnd * (lCurrentIndex - lMin)) + lMin
	vSwapValue = vShuffle(lCurrentIndex)
	vShuffle(lCurrentIndex) = vShuffle(lRandomIndex)
	vShuffle(lRandomIndex) = vSwapValue
	lCurrentIndex = lCurrentIndex - 1
Loop

---
The first swap in the "Do While loop" establishes that the last value in the array is not the last in the array.


---
Version: 24.8.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: 90b12c9bad55e8f50b75a6d7b68caa27d82cc2b9
CPU threads: 4; OS: Windows 10.0 Build 10240; UI render: Skia/Raster; VCL: win
Locale: ja-JP (ja_JP); UI: ja-JP
Calc: CL threaded
Comment 1 nobu 2024-01-02 14:45:52 UTC
Created attachment 191699 [details]
sample file
Comment 2 Xisco Faulí 2024-01-02 15:25:33 UTC
Hi Rafael,
Since this issue concerns ScriptForge I thought you might be interested
Comment 3 Rafael Lima 2024-01-12 12:28:56 UTC
I can reproduce the error. Running the following script returns zero.

Sub TestSuffle
  GlobalScope.BasicLibraries.LoadLibrary("ScriptForge")
  Dim cont4 As Integer
  ' Try 1000 times
  For i = 1 To 1000
    arr = SF_Array.Shuffle(Array(1, 2, 3, 4))
    If arr(3) = 4 Then
      cont4 = cont4 + 1
    End If
  Next i
  MsgBox cont4
End Sub

The script above should return some number around 250.

@JPL can you please take a look?
Comment 4 Rafael Lima 2024-01-12 12:35:51 UTC
I guess the problem is that the line

lRandomIndex = Int(Rnd * (lCurrentIndex - lMin)) + lMin

Will always force the value in the last position to be moved away to another position. It can never fall in its own position, because lRandomIndex can never be the last position.

For instance, in an array with 4 elements (0 to 3), even if Rnd is very large, it will never be 1. So:

Int(0.99999 * (3 - 0) + 0

Will be equal to at most 2... it can never be 3.
Comment 5 Jean-Pierre Ledure 2024-01-12 15:58:00 UTC
I confirm the bug.
Indeed, the algorithm makes that NO ITEM (not only the last one) in the array will stay on its own place.
This was tested with next code, a variant of Rafael's one:

Sub TestSuffle
  GlobalScope.BasicLibraries.LoadLibrary("ScriptForge")
  Dim cont(3) As Integer
  ' Try 1000 times
  For i = 1 To 1000
    arr = SF_Array.Shuffle(Array(1, 2, 3, 4))
    For j = 0 To 3
    	If arr(j) = j + 1 Then cont(j) = cont(j) + 1
    Next j
  Next i
  MsgBox cont(0) & "," & cont(1) & "," & cont(2) & "," & cont(3)
End Sub

This can be corrected by replacing line
     lRandomIndex = Int(Rnd * (lCurrentIndex - lMin)) + lMin
by
     lRandomIndex = Int(Rnd * (lCurrentIndex - lMin + 1)) + lMin

The TestSuffix() gives then 4 * numbers close to 250, e.g.:
     263,235,238,257
totalling more or less 1000: the number of unmoved items indeed can be 0, 1, 2, 3 or 4 by cycle.

I will post a patch.
Thanks for reporting the bug.
Comment 6 Commit Notification 2024-01-13 10:21:03 UTC
Jean-Pierre Ledure committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/ca9168b8ad842c86b2168e12bb98087b9f8139bd

ScriptForge (SF_Array) fix tdf#158976 Shuffle()

It will be available in 24.8.0.

The patch should be included in the daily builds available at
https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
https://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 7 Xisco Faulí 2024-01-15 13:29:36 UTC
Verified in

Version: 24.8.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: 96493091a80fb01c33ea9153b737fdc554de61f0
CPU threads: 8; OS: Linux 6.1; UI render: default; VCL: gtk3
Locale: es-ES (es_ES.UTF-8); UI: en-US
Calc: threaded

@Jean-Pierre Ledure, thanks for fixing this issue. Should this issue be closed as RESOLVED FIXED ?
Comment 8 Commit Notification 2024-01-15 13:30:29 UTC
Jean-Pierre Ledure committed a patch related to this issue.
It has been pushed to "libreoffice-24-2":

https://git.libreoffice.org/core/commit/4651a5eb1b913d61d015c8fe2d713110bd2c5c50

ScriptForge (SF_Array) fix tdf#158976 Shuffle()

It will be available in 24.2.1.

The patch should be included in the daily builds available at
https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
https://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 9 Commit Notification 2024-01-16 08:40:42 UTC
Jean-Pierre Ledure committed a patch related to this issue.
It has been pushed to "libreoffice-7-6":

https://git.libreoffice.org/core/commit/67a2cba41b6caeabac031f1ae35b6c465037b0fd

ScriptForge (SF_Array) fix tdf#158976 Shuffle()

It will be available in 7.6.5.

The patch should be included in the daily builds available at
https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
https://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 10 Rafael Lima 2024-01-24 14:35:50 UTC
I can confirm that the issue is fixed in:

Version: 24.8.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: 52188252bb5d44e15266b84b771599a453438ba6
CPU threads: 12; OS: Linux 6.5; UI render: default; VCL: kf5 (cairo+wayland)
Locale: pt-BR (pt_BR.UTF-8); UI: en-US
Calc: CL threaded