Need help distributing units equally - AKA dividing an array of integers into multiple parts with almost-equal sums

Status
Not open for further replies.

Uncle

Warcraft Moderator
Level 71
Joined
Aug 10, 2018
Messages
7,609
I'm trying to come up with a function that will take a table (array) filled with units and split that into X parts where each part is as close to equal in unit-power as possible.

In other words, I have 4 footman, 3 rifleman, and 2 knights. Knights > Rifleman > Footman. I want to split those among X players as equally as possible.

The end results of dividing those units among 4 players would look something along the lines of this:
player 1 gets: 2 footman, 1 rifleman
player 2 gets: 1 knight
player 3 gets: 2 footman, 2 rifleman
player 4 gets: 1 knight

The order doesn't matter as long as things are close to equal.

Here's some function I found online that I modified to work how I wanted:
Lua:
-- this takes a table filled with units and divides those units among two new tables
-- it also maintains a balance of "power" so that both unit tables are similar in strength
function DivideTableIntoTwo(tbl)
    local u -- unit
    local id -- unit-type id
    local set1 = {} -- first table
    local set2 = {} -- second table
    local sum1 = 0 -- sum of set1 power
    local sum2 = 0 -- sum of set2 power
    local total = #tbl

    for i=1,total do
        u = tbl[i]
        id = GetUnitTypeId(u)
        if sum1 < sum2 then
            table.insert(set1, u)
            sum1 = sum1 + UnitData[id].power
        else
            table.insert(set2, u)
            sum2 = sum2 + UnitData[id].power
        end
        tbl[i] = nil
    end

    return set1, set2
end
It returns two tables, set1 and set2, which each contain an "equal" power level of units which I can then distribute to the players.

UnitData[id].power is a stat I've given each Unit-Type in the game that determines their worth. A Knight would have much higher power than a Footman for example.

Unfortunately, this method among other things I've tried produces less than desirable results where one player ends up receiving way more power worth of units than everyone else.

I was hoping for a function that could manage splitting the table to 2, 3, or 4 players at a time with a bit more accuracy. It could look something like this:
Lua:
function DistributeUnits(unitTable, numberOfPlayers)
 
    if numberOfPlayers == 2 then
        -- do some fancy math
        return tbl1, tbl2
    end

    if numberOfPlayers == 3 then
        -- do some fancy math
        return tbl1, tbl2, tbl3
    end

    if numberOfPlayers == 4 then
        -- do some fancy math
        return tbl1, tbl2, tbl3, tbl4
    end

end
Any help would be greatly appreciated!
 
Last edited:

LeP

LeP

Level 13
Joined
Feb 13, 2008
Messages
544
This seems to be the fair subset sum problem which is really hard to solve optimally. So you have two options: either accept slightly less than optimal solutions or if you have only a handful of options to try every possible combination.
I have not studied this problem but my first hunch would be the naive way of simply sorting the players by accumulated values so far and assigned a new unit to the lowest rated player.
 

Uncle

Warcraft Moderator
Level 71
Joined
Aug 10, 2018
Messages
7,609
Here's another solution I was using that's similar to your naive way of doing this:
Lua:
function DistributeUnits(senderPN)
 
    -- This sorts the units being distributed so that greatest priority units are first in line
    table.sort(UnitsBeingSent, ComparePriorityValue)
    -- This randomizes the order in which the opponents receive units
    TableShuffle(SendOpponents[senderPN])
 
    local opponentCount = #SendOpponents[senderPN] -- SendOpponents is a table containing the player's opposition
    local u -- unit
    local unitTypeId -- unit-type id
    local value -- power value
    local enemyPlayer -- current player receiving units
    local enemyIndex = 1
    local failedAttempts = 0
    local playerValue = __jarray(0) -- the player's accumulated value
    local limit = R2I(GetSendLimit() / opponentCount) -- This is how much value worth of units a player can have (sum of values / # of opponents)
    if limit < SendHighestPriority then limit = SendHighestPriority end -- SendHighestPriority is the highest priority value being sent
    local total = #UnitsBeingSent
    local leftoverCount = total
    local i = 0
 
    while i < total do
        i = i + 1
        u = UnitsBeingSent[i]
        unitTypeId = GetUnitTypeId(u)
 
        -- Some units are Aura types which get distributed during the leftover process
        if UnitData[unitTypeId].isAuraType == false then

            -- We're cycling through enemy players using a table of players
            enemyPlayer = SendOpponents[senderPN][enemyIndex]
            if enemyIndex < opponentCount then
                enemyIndex = enemyIndex + 1
            else
                enemyIndex = 1
            end

            -- Let's get the current units "priority" which determines it's value
            value = UnitData[unitTypeId].priority
 
            -- Make sure the enemy player hasn't reached their limit already
            if playerValue[enemyPlayer] + value <= limit then
                -- Send the unit to the enemy player's region
                playerValue[enemyPlayer] = playerValue[enemyPlayer] + value
                SetUnitPosition(u, SendPointsX[enemyPlayer], SendPointsY[enemyPlayer])
                failedAttempts = 0
                leftoverCount = leftoverCount - 1
                UnitsBeingSent[i] = nil
            else
                -- Attempt to send this unit to someone else
                failedAttempts = failedAttempts + 1
                if failedAttempts < opponentCount then
                    -- Try this unit again
                    i = i - 1
                else
                    -- Unit failed for everyone & added to leftovers, move on to the next unit
                    failedAttempts = 0
                end
            end
        end
    end

    -- Leftover process:
    -- Deal with leftover units that failed to get sent in the previous While loop (if any)
    -- Also, Aura-type units are sent during this time and are the first to be sent
    if leftoverCount > 0 then
        i = 0
        enemyIndex = 1

         -- A table containing enemy players ordered from least to greatest value (priority)
        local lowestEnemyPlayers = GetLowestValuePlayers(senderPN, playerValue)
 
        while leftoverCount > 0 do
            i = i + 1
            if UnitsBeingSent[i] ~= nil then
                u = UnitsBeingSent[i]
                enemyPlayer = lowestEnemyPlayers[enemyIndex]
                if enemyIndex < opponentCount then
                    enemyIndex = enemyIndex + 1
                else
                    enemyIndex = 1
                end
                SetUnitPosition(u, SendPointsX[enemyPlayer], SendPointsY[enemyPlayer])
                SetUnitColor(u, PLAYER_COLOR_GREEN)
                leftoverCount = leftoverCount - 1
                UnitsBeingSent[i] = nil
            end
        end
    end
    -- All units have been distributed and the UnitsBeingSent table has been emptied
end
Notes:
  • The system is designed so that one player fills the UnitsBeingSent table with their units (senderPN is equal to their Player Number) and then those units are distributed among that player's opponents "equally".
  • Auta-type units are special case units that are distributed after the non-Aura units. The goal there was to try and give players 1 of each Aura unit, so if 4 Devotion Aura units are sent out and there's 4 opponents, each player is guaranteed to receive 1. That works for the most part.
  • I'm calling a unit's value it's "priority" in this example.
So I'm looping over the non-Aura units that are contained within the UnitsBeingSent table. I also cycle over the enemy players that will receive these units using the SendOpponents table. If a player hasn't reached their value limit (playerValue) they're given the unit, otherwise, the While loop repeats the current cycle and attempts to give that unit to the next player in line. If no player is able to afford the unit then it's skipped and the While loop moves on to the next unit. The skipped units are dealt with later on in the "leftover process" where value is not taken into consideration. I suppose this is where a good chunk of the imbalance happens, now that I think about it these leftover units should still be divided based on accumulated value (playerValue)-Auras excluded.

@LeP
You wouldn't happen to have an efficient function for sorting players based on their accumulated values (playerValues)? The one I'm using now seems awful. That's probably what I'll work on next.
 
Last edited:

LeP

LeP

Level 13
Joined
Feb 13, 2008
Messages
544
You wouldn't happen to have an efficient function for sorting players based on their accumulated values (playerValues)? The one I'm using now seems awful. That's probably what I'll work on next.
One common way is to use a priority queue often implemented via a heap. Personally i'm a fan of pairing heaps but that might be more suited in other programming languages than lua.
 

Uncle

Warcraft Moderator
Level 71
Joined
Aug 10, 2018
Messages
7,609
After testing this new function I'm seeing some pretty positive results:
Lua:
function DistributeUnits(senderPN)
 
    table.sort(UnitsBeingSent, CompareLumberCost) -- sort the tables from highest lumberCost to lowest
    table.sort(UnitsBeingSentAura, CompareLumberCost)
    local total = #UnitsBeingSentAura
    local u -- unit
    local playerValue = __jarray(0) -- the player's accumulated value
    local enemyPlayer -- current player receiving a unit
 
    -- Deal with Aura units
    if total > 0 then
        local enemyIndex = 1
        local opponentCount = #SendOpponents[senderPN]
        TableShuffle(SendOpponents[senderPN]) -- randomize the order of opponents
        for i=1,total do
            u = UnitsBeingSentAura[i]
 
            enemyPlayer = SendOpponents[senderPN][enemyIndex]
            if enemyIndex < opponentCount then
                enemyIndex = enemyIndex + 1
            else
                enemyIndex = 1
            end
 
            playerValue[enemyPlayer] = playerValue[enemyPlayer] + UnitData[GetUnitTypeId(u)].lumberCost
 
            SetUnitPosition(u, SendPointsX[enemyPlayer], SendPointsY[enemyPlayer])
            SetUnitColor(u, PLAYER_COLOR_BLUE) -- delete later
            UnitsBeingSentAura[i] = nil
        end
    end

    -- Deal with non-Aura units
    total = #UnitsBeingSent
    if total > 0 then
        for i=1,total do
            u = UnitsBeingSent[i]
 
            enemyPlayer = GetLowestValuePlayer(senderPN, playerValue)

            playerValue[enemyPlayer] = playerValue[enemyPlayer] + UnitData[GetUnitTypeId(u)].lumberCost
 
            SetUnitPosition(u, SendPointsX[enemyPlayer], SendPointsY[enemyPlayer])
            UnitsBeingSent[i] = nil
        end
    end
end
Lua:
function GetLowestValuePlayer(senderPN, playerValue) -- Gets the enemy player with the lowest accumulated value
    local player
    local lowestPlayer
    local lowestValue = 999999999
    for i=1,#SendOpponents[senderPN] do
        player = SendOpponents[senderPN][i]
        if playerValue[player] <= lowestValue then
            lowestValue = playerValue[player]
            lowestPlayer = player
        end
    end
    return lowestPlayer
end
First I distribute the Aura units in order from highest lumber cost to lowest lumber cost (just another representation of worth). This produces the desired results of each player receiving at least 1 of each Aura unit-type (if there's enough to go around).

Then I distribute the non-Aura units, sending the current cycle's unit to the player with the lowest accumulated value.

I had originally wanted players to receive 1 of each unit-type if able but that overcomplicated things way too much. This design is much better.
 
Last edited:
Level 1
Joined
Jun 21, 2019
Messages
4
1) get total sum
2) split it by number of teams
3) find combinations with closest sums to results of 2.
Probably way to go
 
Status
Not open for further replies.
Top