在给定的用户列表中分布

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 位用户，其明文和实体将仅分配给该用户。在多个用户的情况下，它可以分配给他们中的任何一个。

我们希望分配它，使每个用户获得等量的实体。并且有最小的 possible/unavoidable 偏态分布，而且每个用户可能已经拥有一些实体：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

我可能误解了你的问题，但是，根据我对你的描述的理解，问题似乎很简单。

关于创建新实体

Is that entity a "single user entity" ?
   Assign it to the given user
   : Assign it to the user that have the least number of entities. If you find users with the same number of instances, it doesn't matter, assign it to an arbitrary user.

重新分配现有实体

如果你想"redistribute"分配实体：

Take the number of entities you want to reallocate and divide it by the number of users and allocate them accordingly

Answer 2

你好，你能维护一个基于 CountOfEntities 排序的 TreeMap 吗？每次您在 TreeMap(0) 处将实体分配给用户时，都会增加 CountOfEntities。

Answer 3

我分几步完成了这个

只给一个用户分配所有实体
按顺序分配剩余的实体
平衡用户之间的实体
通过分发任何差异解决遗留问题

原码

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 个实体不同，但所有实体都已分配。

代码：

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;


    }
}

在给定的用户列表中分布

distribution among given list of user

c#

algorithm

distribution

c#-4.0

关于创建新实体

重新分配现有实体