URL:
<http://gna.org/bugs/?21706>
Summary: helper.shuffle uses incorrect shuffling algorithm
Project: Battle for Wesnoth
Submitted by: elvish_pillager
Submitted on: Fri 21 Feb 2014 10:08:35 PM UTC
Category: Bug
Severity: 2 - Minor
Priority: 5 - Normal
Item Group: None of the others
Status: None
Privacy: Public
Assigned to: None
Originator Email:
Open/Closed: Open
Discussion Lock: Any
Release: 1.11.9+dev
Operating System: Debian Linux
_______________________________________________________
Details:
helper.shuffle uses an incorrect implementation of the Fischer-Yates in-place
shuffle, which produces slightly biased results. It swaps each element with a
random other element from the whole list, when the algorithm calls for
swapping the element with a random earlier (or same) element. In the shuffling
of {1,2,3}, for instance, helper.shuffle produces half the possible results at
a 4:5 ratio to the other half.
To fix, replace the line
local random = math.random( 1, length )
with
local random = math.random( 1, index )
(and delete the line "local length = #t", as it's now unused.)
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm
_______________________________________________________
Reply to this item at:
<http://gna.org/bugs/?21706>
_______________________________________________
Message sent via/by Gna!
http://gna.org/
_______________________________________________
Wesnoth-bugs mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-bugs
