Shuffle an array

[Gotjek]

I often need to shuffle an array, so I made this function.
I hope it to be useful if you need this too.

Code: Select all

Shuffle_Array(array_in) {
    ; Shuffle an array. Supports array of objects.

    If (Type(array_in) != "Array")
        Throw TypeError("Parameter should be of Array type." , -1, array_in)

    array_clone := array_in.Clone()  ; Let original array untouched.
    array_out := []

    Loop array_clone.Length {
        rand_index := Random(1, array_clone.Length)
        rand_item := array_clone[rand_index]
        array_clone.RemoveAt(rand_index)
        array_out.Push(rand_item)
    }

    Return array_out
}

Edit : updated to preserve the passed array (thanks @Descolada and @Chunjee).

[Descolada]

A few suggestions:
1) Your implementation destroys the original array, perhaps that could be preserved?

Code: Select all

arr := [1,2,3,4,5]
rarr := _Shuffle_Array(arr)
OutputDebug(arr[1]) ; throws error

2) Unset items throw an error (though I am unsure if this should at all be a valid array to be sorted): OutputDebug(_Shuffle_Array([1,,5])[1])
3) I believe the time complexity could be improved as well: check out the Fisher-Yates shuffle algorithm. I am not exactly sure what your algorithms' time complexity is (I think O(n log n)?), but Fisher-Yates is O(n).

[Chunjee]

shuffle is very important to my style of programming! Thank you!


Some optimizations as mentioned above;

Spoiler

Code: Select all

fn_shuffle([1,2,3,4,5])
; => [2, 4, 5, 3, 1]


fn_shuffle(param_array) {
	if (type(param_array) != "Array") {
		throw typeError("Parameter should be of Array type." , -1, param_array)
	}

	; prepare
	l_array := param_array.clone()

	; create
	l_index := l_array.length
	loop l_index - 1 {
		randomIndex := random(1, l_index)
		l_tempVar := l_array[l_index]
		l_array[l_index] := l_array[randomIndex]
		l_array[randomIndex] := l_tempVar
		l_index--
	}
	return l_array
}

[Gotjek]

@Descolada :
1) It was not a good behavior, thanks for pointing that out. I think I could have messed some scripts with that.
2) I don't know either !
3) My level is unfortunately not high enough to understand this well nor code this... I tried to understand this concept with the pencil and paper example : https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method. Isn't it what my script does, picking an item one by one ?

@Chunjee :
These functions are in AHK v2 : https://lexikos.github.io/v2/docs/commands/Type.htm
I'm sorry, I'm trying to switch all my scripts to v2 without looking back.
I am not even able to correctly understand code in v1 anymore . Did you implement Fisher-Yates shuffle algorithm too ?

[Chunjee]

Yes, I'm very sorry; I entered the v2 section unknowingly.

Updated my post