Shuffle list

[Thalassicus]

Create a weighted shuffle list class.

This is basically like shuffle in a music player, but each item has a weight. An item with 2 weight is twice as likely to be chosen as something with 1 weight. When an item is selected, its weight is set to 0 and distributed evenly among the weights of all other items in the list.

This is better than a completely random selection because everything will eventually get selected, and it's very unlikely an item will get selected twice in short succession. A normal shuffle can theoretically select the same item every time.

This will provide a better method of choosing Stories, among other things.

pseudocode:

class WeightedShuffleList
    local list = {}
    local size = 0
    function Add                (item, weight)
    function Remove             (item)
    function Next               ()
    function DistributeWeight   (item)
end

function WeightedShuffleList.Add(self, item)
    self.list[item] = 1
    self.size = self.size + 1
end

function WeightedShuffleList.Remove(self, item) 
    self.list[item] = self.list[item] - 1
    DistributeWeight(item)

    self.list[item] = nil
    self.size = self.size - 1   
end

function WeightedShuffleList.Next(self)
    local item = Game.GetRandomWeighted(self.list)
    DistributeWeight(item)  
    return item
end

function WeightedShuffleList.DistributeWeight(self, item)
    -- split weight of chosen item among all other elements in the list
    local addWeight = self.list[item] / self.size
    self.list[item] = 0

    for otherItem, weight in pairs(self.list) do
        if item ~= otherItem then
            self.list[otherItem] = self.list[otherItem] + addWeight
        end
    end
end