From b596210c09374f53d4349990945a07520c092f55 Mon Sep 17 00:00:00 2001
From: Todor Balabanov <todor.balabanov@gmail.com>
Date: Wed, 1 May 2019 15:04:27 +0300
Subject: Fisher-Yates shuffling algorithm achieves much better randomization.

Change-Id: I6d204a7ba0fa19f4c318d1c70f5a0344e0640d6d
Reviewed-on: https://gerrit.libreoffice.org/71620
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
---
 .../net/adaptivebox/global/RandomGenerator.java    | 46 +++++++++-------------
 1 file changed, 19 insertions(+), 27 deletions(-)

(limited to 'nlpsolver')

diff --git a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/global/RandomGenerator.java b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/global/RandomGenerator.java
index d7fafc9b9046..18ced86335dc 100644
--- a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/global/RandomGenerator.java
+++ b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/global/RandomGenerator.java
@@ -59,37 +59,29 @@ public class RandomGenerator {
     }
 
     public static int[] randomSelection(int maxNum, int times) {
-        if (times <= 0)
-            return new int[0];
-        int realTimes = Math.min(maxNum, times);
-        boolean[] flags = new boolean[maxNum];
-        boolean isBelowHalf = times < maxNum * 0.5;
-        int virtualTimes = realTimes;
-        if (!isBelowHalf) {
-            virtualTimes = maxNum - realTimes;
+        if (maxNum < 0) {
+            maxNum = 0;
         }
-        int i = 0;
-        int upper = maxNum - 1;
-        int[] indices = new int[realTimes];
 
-        while (i < virtualTimes) {
-            indices[i] = intRangeRandom(0, upper);
-            if (!flags[indices[i]]) {
-                flags[indices[i]] = true;
-                i++;
-            }
+        if (times < 0) {
+            times = 0;
         }
-        if (!isBelowHalf) {
-            int j = 0;
-            for (i = 0; i < maxNum; i++) {
-                if (flags[i] == isBelowHalf) {
-                    indices[j] = i;
-                    j++;
-                    if (j == realTimes)
-                        break;
-                }
-            }
+
+        int[] all = new int[maxNum];
+        for (int i = 0; i < all.length; i++) {
+            all[i] = i;
         }
+
+        /* https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle */
+        int[] indices = new int[Math.min(maxNum, times)];
+        for (int i = 0, j, value; i < indices.length; i++) {
+            j = intRangeRandom(i, all.length - 1);
+
+            value = all[j];
+            all[j] = all[i];
+            indices[i] = all[i] = value;
+        }
+
         return indices;
     }
 }
-- 
cgit