[MATH-1019] "shuffle" method broken (in class "o.a.c.m.random.RandomDataGenerator")

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 3.3
• Assignee: Unassigned
• Reporter: Gilles Sadowski
• Created: 08/Aug/13 22:43
• Updated: 19/May/14 15:13
• Resolved: 10/Aug/13 00:26

Description

The method does not abide by its contract: elements before the "end" index are included in the shuffle.

/**
 * Uses a 2-cycle permutation shuffle to randomly re-order the last elements 
 * of list.
 *
 * @param list list to be shuffled
 * @param end element past which shuffling begins
 */
private void shuffle(int[] list, int end) {
    int target = 0;
    for (int i = list.length - 1; i >= end; i--) {
        if (i == 0) { // XXX "0" should be "end"
            target = 0; // XXX "0" should be "end"
        } else {
            // NumberIsTooLargeException cannot occur
            target = nextInt(0, i); // XXX "0" should be "end"
        }
        int temp = list[target];
        list[target] = list[i];
        list[i] = temp;
    }
}

I'm going to introduce the above corrections in the new implementation to be located in "MathArrays" (cf. issue MATH-1010).

Issue Links

• relates to: MATH-1020 "nextPermutation" method broken (in class "o.a.c.m.random.RandomDataGenerator")
• relates to: MATH-1010 Shuffling an array