c# - 在给定的用户列表中分布

Question

我有一个要求，我有一个实体列表和可以分配给该实体的用户

E1 can be distributed by U1 or U2

E2 must be distributed by U5

E3 can be distributed by U2 or U3 or U4

我有 50K 个实体，每个实体可能有 1 个或多个用户。如果是 1 位用户，其明文和实体将仅分配给该用户。在多个用户的情况下，它可以分配给他们中的任何一个。

我们希望对其进行分配，使每个用户获得等量的实体。并且存在最小的可能/不可避免的偏态分布，而且每个用户可能已经拥有一些实体:U1 有 2K 实体，U2 已经有 3K 实体，所以分布也应该考虑这个事实。

编辑 1

我们已经尝试了一种解决方案，即根据当时分配给用户的分配顺序并一次分配一个实体，但会产生偏斜的结果，因为我们得到的用户较早分配较少但分配较多稍后或反之亦然...

E1 to E25 "must be handled by any of" U1 & U2

E26 to E50 "must be handled by any of" U2 & U3

如果我们按顺序进行，最后:U1 得到 12(从 E1-E25)，U2 得到 19(从 E1-E25 得到 13，从 E26-E50 得到 6)和 U3 得到 19(从 E26-E50)。所以一共分配了50个。美好的。但看到有偏差的结果

EDIT2

为什么我们每个实体有不同的用户？有多种产品要分发。一些用户处理多个产品，一些用户处理单个产品，但仍然需要对所有用户进行负载均衡。

Answer 1

我分几步完成了

1. 将所有实体分配给一个用户
2. 按顺序分配剩余的实体
3. 平衡用户之间的实体
4. 通过分发任何差异解决剩余问题

原始代码

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

    public class Entity
    {
        public string Type { get; set; }
    }

    public class User
    {
        public User()
        {
            EntitiesCount = new Dictionary<string, int>();
        }
        public string userId { get; set; }
        public Dictionary<string, int> EntitiesCount { get; set; }
        public int TotalEntities { get; set; }
        public bool Ignored { get; set; }

    }

    class Program
    {
        static void Main(string[] args)
        {

            for (var myLoop = 0; myLoop < 100; myLoop++)
            {
                //Create users
                var userList = new List<User> {
                    new User { userId = "U0" } ,
                    new User { userId = "U1" } ,
                    new User { userId = "U2" } ,
                    new User { userId = "U3" } ,
                    new User { userId = "U4" } 
                };
                userList = userList.OrderBy(u => u.userId).ToList();
                //Assign Users to Entities
                var entityUsers = new Dictionary<string, List<User>>() { 
                    { "E0", 
                      new List<User> { 
                          userList[0] ,
                          userList[1] 
                      } 
                    } ,
                    { "E1", 
                      new List<User> { 
                          userList[4]
                      } 
                    } ,
                    { "E2", 
                      new List<User> { 
                          userList[1],
                          userList[2],
                          userList[3] 
                      } 
                    } 
                };


                //var entityUsers = new Dictionary<string, List<User>>() { 
                //        { "E0", 
                //          new List<User> { 
                //              userList[0] ,
                //              userList[1] 
                //          } 
                //        } ,
                //        { "E1", 
                //          new List<User> { 
                //              userList[1],
                //              userList[2],
                //          } 
                //        } ,
                //    };

                //Load Entities, you can change the number of entities generated her
                var entities = GenerateEntities(entityUsers.Count(), 50000);

                //Group the Entities by their type and display total number
                var lookupEntities = entities.ToLookup(e => e.Type);
                foreach (var lookupEntity in lookupEntities)
                {
                    Console.WriteLine(lookupEntity.Key + " has " + lookupEntity.Count());
                }


                // Users are ignored if there is a one to one mapping
                var ignoreUsers = 0;

                //Entities are ignored if they are only handled by one user
                var ignoreEntities = 0;

                foreach (var entityUser in entityUsers)
                {
                    foreach (var user in entityUser.Value)
                    {
                        user.EntitiesCount.Add(entityUser.Key, 0);
                    }
                }

                //Assign entities where only one user available
                foreach (var entityUser in entityUsers.Where(a => a.Value.Count == 1))
                {

                    Console.WriteLine("Assigning all " + entityUser.Key + " to " + entityUser.Value[0].userId + " - " + lookupEntities[entityUser.Key].Count());

                    entityUser.Value[0].TotalEntities += lookupEntities[entityUser.Key].Count();
                    entityUser.Value[0].EntitiesCount[entityUser.Key] = lookupEntities[entityUser.Key].Count();

                    //Ignore these entities because they cannot changed
                    ignoreEntities += entityUser.Value[0].TotalEntities;

                    if (entityUsers.Count(e => e.Value.Contains(entityUser.Value[0])) == 1)
                    {
                        //The user is only assigned to this one entity so ignore user in balancing
                        ignoreUsers++;
                        entityUser.Value[0].Ignored = true;
                    }
                }



                //Assign entities where more than one user available
                foreach (var entityUser in entityUsers.Where(a => a.Value.Count > 1))
                {
                    var numberOfEntities = lookupEntities[entityUser.Key].Count();
                    for (var i = 0; i < numberOfEntities; i++)
                    {
                        var user = entityUser.Value.OrderBy(u => u.TotalEntities).First();
                        if (!user.EntitiesCount.ContainsKey(entityUser.Key))
                            user.EntitiesCount.Add(entityUser.Key, 0);
                        user.EntitiesCount[entityUser.Key]++;
                        user.TotalEntities++;
                    }

                }

                var averagePerUser = 0;
                var busyUsers = userList.Count(a => a.TotalEntities != 0);

                //Check to see if there is only one users assigned to each entity
                if (busyUsers != ignoreUsers)
                {
                    //Calculate the expected average per user 

                    var totalEntities = entities.Count;
                    averagePerUser = (totalEntities - ignoreEntities) / (busyUsers - ignoreUsers);

                    Console.WriteLine();
                    Console.WriteLine("Total Entities: " + totalEntities);
                    Console.WriteLine("Average Entities: " + averagePerUser);
                    Console.WriteLine();

                    OutputAllocation(userList, averagePerUser);
                    var orderedUserList = userList.OrderByDescending(u => u.TotalEntities).ToList();
                    //Loop through the users and compare to the remaining users
                    for (var i = 0; i < orderedUserList.Count - 1; i++)
                    {
                        for (var j = i + 1; j < userList.Count; j++)
                        {
                            BalanceUsers(userList[i], userList[j], entityUsers, averagePerUser);
                        }
                    }

                    ////Loop through the list in reverse order ?
                    //for (var i = userList.Count - 1; i >= 0; i--)
                    //{
                    //    for (var j = i - 1; j >= 0; j--)
                    //    {
                    //        BalanceUsers(userList[i], userList[j], entityUsers, averagePerUser);
                    //    }
                    //}
                }

                OutputAllocation(userList, averagePerUser);

                Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
                Console.WriteLine();

                //Even out remaining difference across entity Type
                foreach (var entityUser in entityUsers.Where(a => a.Value.Count > 1))
                {
                    if (entityUser.Value.Any(u => (u.TotalEntities - averagePerUser > 0)))
                    {
                        var users = entityUser.Value.Where(u => (u.TotalEntities - averagePerUser != 0) && u.EntitiesCount[entityUser.Key] > 0);

                        var difference = 0;
                        foreach (var user in users)
                        {
                            difference += user.TotalEntities - averagePerUser;
                            user.TotalEntities -= difference;
                            user.EntitiesCount[entityUser.Key] -= difference;
                        }

                        List<User> fixUsers = null;
                        if (difference < 0)
                        {
                            fixUsers = entityUser.Value.Where(u => (u.EntitiesCount[entityUser.Key] > 0)).ToList();
                        }
                        else
                        {
                            fixUsers = entityUser.Value;
                        }
                        var change = difference / fixUsers.Count();
                        var userCount = fixUsers.Count();
                        foreach (var fixUser in fixUsers)
                        {
                            fixUser.TotalEntities += change;
                            fixUser.EntitiesCount[entityUser.Key] += change;
                            difference -= change;
                            userCount--;
                            //Correct change so that nothing gets lost
                            if (userCount != 0)
                                change = difference / userCount;
                            else
                                change = difference;

                        }
                    }
                }

                OutputAllocation(userList, averagePerUser);

                Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
                Console.WriteLine();

                foreach (var lookupEntity in lookupEntities)
                {
                    Console.Write(lookupEntity.Key + " - " + lookupEntity.Count());
                    Console.Write(" Allocation: ");
                    foreach (User user in entityUsers[lookupEntity.Key])
                    {
                        Debug.Assert(user.EntitiesCount[lookupEntity.Key] >= 0);
                        Console.Write(user.userId + " = " + user.EntitiesCount[lookupEntity.Key] + "; ");
                    }
                    Console.WriteLine();
                }

            }
            Console.ReadLine();
        }

        private static void OutputAllocation(List<User> userList, int averagePerUser)
        {
            //Display allocation after initial assignment
            foreach (var user in userList)
            {
                var difference = user.TotalEntities - averagePerUser;
                if (user.Ignored)
                    Console.WriteLine("Assignment  " + user.userId + " has " + user.TotalEntities);
                else
                    Console.WriteLine("Assignment  " + user.userId + " has " + user.TotalEntities + " difference " + difference);
            }
            Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
            Console.WriteLine();
        }


        /// <summary>
        /// Compares two users and balances them out
        /// </summary>
        private static void BalanceUsers(User firstUser, User secondUser, Dictionary<string, List<User>> entityUsers, int averagePerWorker)
        {
            //Get the difference betweent the current users and the average worker
            var firstUserDiff = firstUser.TotalEntities - averagePerWorker;
            var secondUserDiff = secondUser.TotalEntities - averagePerWorker;


            //Get all the entities which the two users share
            var sharedEntityTypes = entityUsers.Where(x => x.Value.Contains(firstUser) && x.Value.Contains(secondUser)).Select(e => e.Key);

            foreach (var entityType in sharedEntityTypes)
            {
                var difference = firstUserDiff;

                if (firstUser.EntitiesCount.Count() > secondUser.EntitiesCount.Count())
                {
                    difference = -1 * secondUserDiff;
                }
                else if (firstUser.EntitiesCount.Count() == secondUser.EntitiesCount.Count())
                {
                    difference = firstUserDiff - secondUserDiff;
                }
                else
                {
                    difference = firstUserDiff;
                }

                difference = firstUserDiff;

                var maxAllowed = 0;
                if (difference > 0)
                {
                    maxAllowed = firstUser.EntitiesCount[entityType] > difference ? difference : firstUser.EntitiesCount[entityType];
                }
                else
                {
                    maxAllowed = secondUser.EntitiesCount[entityType] > Math.Abs(difference) ? difference : -1 * secondUser.EntitiesCount[entityType];
                }

                firstUser.EntitiesCount[entityType] -= maxAllowed;
                firstUser.TotalEntities -= maxAllowed;

                secondUser.EntitiesCount[entityType] += maxAllowed;
                secondUser.TotalEntities += maxAllowed;

                firstUserDiff = firstUser.TotalEntities - averagePerWorker;
                secondUserDiff = secondUser.TotalEntities - averagePerWorker;
            }
        }



        private static List<Entity> GenerateEntities(int maxEntityTypes, int totalEntities)
        {
            var entityTypes = new List<string>();
            for (var i = 0; i < maxEntityTypes; i++)
            {
                entityTypes.Add("E" + i);
            }
            var entities = new List<Entity>();
            Random random = new Random();
            for (var i = 0; i < totalEntities; i++)
            {
                //Randomly allocate user
                entities.Add(new Entity { Type = entityTypes[random.Next(maxEntityTypes)] });

                //Used to get even distribution
                //entities.Add(new Entity { Type = entityTypes[i%maxEntityTypes] });

                //Used to get specific ratio
                //var type = "";
                //switch (i % 3)
                //{
                //    case 0:
                //        type = "E0";
                //        break;
                //    case 1:
                //    case 2:
                //        type = "E1";
                //        break;
                //}

                //entities.Add(new Entity { Type = type });
            }
            return entities;


        }
    }

编辑 1:我对上面的代码做了一些修改。

1. 现在创建实体列表后，程序会向实体添加一个随机潜在用户列表，这应该更符合您的真实场景
2. 程序现在遍历所有实体，并根据该实体的允许用户中拥有最少实体的用户将它们分配给用户
3. 然后程序将反复尝试平衡用户之间的实体，直到没有任何变化

代码随后进行检查，以确保分配给实体的用户确实在规定的用户中。

有时最终结果分配与理想情况有 1 或 2 个实体不同，但所有实体都已分配。

代码:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;


public class Entity
{
    public Entity()
    {
        _users = new List<User>();
    }
    public string Type { get; set; }

    public List<User> _users;
    public List<User> Users
    {
        get
        {
            //You can add your rules for users here 
            return _users;
        }
    }
    public User AssignedUser { get; set; }

}

public class User
{
    public User()
    {
        Entities = new Dictionary<string, Entity>();
    }
    public string userId { get; set; }
    public Dictionary<string, Entity> Entities { get; set; }
    public int TotalEntities { get; set; }
    public bool Ignored { get; set; }

}

class Program
{
    static void Main(string[] args)
    {
        //Load Entities, you can change the number of entities generated here
        int numEntityToGenerate = 50001;
        //Create users
        var userList = new List<User> {
                            new User { userId = "U0" } ,
                            new User { userId = "U1" } ,
                            new User { userId = "U2" } ,
                            new User { userId = "U3" } ,
                            new User { userId = "U4" } 
                        };
        userList = userList.OrderBy(u => u.userId).ToList();

        var entities = GenerateEntities(userList, numEntityToGenerate);

        foreach (var entity in entities)
        {
            foreach (var user in entity.Users)
            {
                user.Entities.Add(entity.Type, null);
            }
        }

        foreach (var entity in entities)
        {
            Console.Write(".");
            var user = entity.Users.OrderBy(u => u.TotalEntities).First();
            if (!user.Entities.ContainsKey(entity.Type))
                user.Entities.Add(entity.Type, null);
            user.Entities[entity.Type] = entity;
            user.TotalEntities++;
            entity.AssignedUser = user;
        }

        var averagePerUser = 0;
        var busyUsers = userList.Count(a => a.TotalEntities != 0);


        //Calculate the expected average per user 
        var totalEntities = entities.Count;
        averagePerUser = (totalEntities) / (busyUsers);

        Console.WriteLine();
        Console.WriteLine("Total Entities: " + totalEntities);
        Console.WriteLine("Average Entities: " + averagePerUser);
        Console.WriteLine("Busy Users: " + busyUsers);
        Console.WriteLine();

        List<int> oldDifference = null;
        List<int> newDifference = null;

        do
        {
            oldDifference = GetDifferenceList(userList, averagePerUser);
            OutputAllocation(userList, averagePerUser);
            var orderedUserList = userList.OrderByDescending(u => u.TotalEntities).ToList();
            //Loop through the users and compare to the remaining users
            for (var i = 0; i < orderedUserList.Count - 1; i++)
            {
                for (var j = i + 1; j < userList.Count; j++)
                {
                    BalanceUsers(userList[i], userList[j], entities, averagePerUser);
                }
            }
            newDifference = GetDifferenceList(userList, averagePerUser);
        } while (!Enumerable.SequenceEqual(oldDifference.OrderBy(t => t), newDifference.OrderBy(t => t)));


        Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
        Console.WriteLine();

        OutputAllocation(userList, averagePerUser);

        Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
        Console.WriteLine();


        //Check data quality
        foreach (var entity in entities)
        {
            //Check to see if assigned user is valid
            Debug.Assert(entity.Users.Contains(entity.AssignedUser));
        }
        Console.ReadLine();
    }

    private static List<int> GetDifferenceList(List<User> userList, int averagePerUser)
    {
        var differences = new List<int>();

        foreach (var user in userList)
        {
            var difference = user.TotalEntities - averagePerUser;
            if (user.TotalEntities != 0)
                differences.Add(difference);
        }
        return differences;

    }

    private static void OutputAllocation(List<User> userList, int averagePerUser)
    {
        //Display allocation after initial assignment
        foreach (var user in userList)
        {
            var difference = user.TotalEntities - averagePerUser;
            if (user.TotalEntities == 0)
                Console.WriteLine("Assignment  " + user.userId + " has " + user.TotalEntities);
            else
                Console.WriteLine("Assignment  " + user.userId + " has " + user.TotalEntities + " difference " + difference);
        }
        Console.WriteLine("Total assigned: " + userList.Sum(u => u.TotalEntities));
        Console.WriteLine();
    }


    /// <summary>
    /// Compares two users and balances them out
    /// </summary>
    private static void BalanceUsers(User firstUser, User secondUser, List<Entity> entities, int averagePerWorker)
    {
        //Get the difference betweent the current users and the average worker
        var firstUserDiff = firstUser.TotalEntities - averagePerWorker;
        var secondUserDiff = secondUser.TotalEntities - averagePerWorker;


        if ((firstUserDiff != 0 && secondUserDiff != 0) && Math.Abs(firstUserDiff - secondUserDiff) > 1)
        {
            //Get all the entities which the two users share
            var sharedEntity = entities.Where(x => x.Users.Contains(firstUser) && x.Users.Contains(secondUser));

            foreach (var entity in sharedEntity)
            {
                //Find out the direction the change needs to occur
                if (firstUserDiff >= secondUserDiff)
                {
                    //Removing from firstUser so find out if it has the entity
                    if (firstUser.Entities[entity.Type] != null)
                    {
                        firstUser.Entities[entity.Type] = null;
                        firstUser.TotalEntities--;

                        secondUser.Entities[entity.Type] = entity;
                        secondUser.TotalEntities++;

                        entity.AssignedUser = secondUser;
                    }
                }
                else
                {
                    //Removing from secondUser so find out if it has the entity
                    if (secondUser.Entities[entity.Type] != null)
                    {
                        firstUser.Entities[entity.Type] = entity;
                        firstUser.TotalEntities++;

                        secondUser.Entities[entity.Type] = null;
                        secondUser.TotalEntities--;

                        entity.AssignedUser = firstUser;
                    }
                }

                firstUserDiff = firstUser.TotalEntities - averagePerWorker;
                secondUserDiff = secondUser.TotalEntities - averagePerWorker;

                //Check to see if the two users have been balanced or if the difference is only one
                //IF that is the case break the for loop
                if ((firstUserDiff != 0 && secondUserDiff != 0) && (firstUserDiff == secondUserDiff) && Math.Abs(firstUserDiff - secondUserDiff) <= 1)
                    break;
            }
        }
    }


    /// <summary>
    /// Generate a list of entities randomly adding a list of potential users to each entity
    /// </summary>
    /// <param name="userList">list of available users</param>
    /// <param name="totalEntities">Total number of entities required</param>
    /// <returns>A list of entities</returns>
    private static List<Entity> GenerateEntities(List<User> userList, int totalEntities)
    {
        var entities = new List<Entity>();
        Random random = new Random();
        for (var i = 0; i < totalEntities; i++)
        {
            var entity = new Entity { Type = "E" + (i + 1).ToString() };
            entities.Add(entity);

            //This code will either an entity to the last user or to a random list of users excluding the last one
            if (random.Next(12) == 0)
            {
                var user = userList[userList.Count() - 1];
                entity.Users.Add(user);
            }
            else
            {
                var numOfUsers = random.Next(2);

                for (var j = 0; j <= numOfUsers; j++)
                {
                    var user = userList[random.Next(userList.Count() - 1)];
                    if (!entity.Users.Contains(user))
                        entity.Users.Add(user);
                }
            }

            //if (i <= totalEntities / 2 )
            //{
            //    entity.Users.Add(userList[0]);
            //    entity.Users.Add(userList[1]);
            //}
            //else
            //{
            //    entity.Users.Add(userList[2]);
            //    entity.Users.Add(userList[1]);
            //}

        }
        return entities;


    }
}