c# - 在帐户上公平分配工作 - 分配算法

Question

我正在从事一个使用多个帐户发布到多个网站的项目。每个帐户都可以发布到特定网站。如下面的“Dict”所示。问题是我试图在账户上公平地分配发布工作，并在拥有超过 1 个工作的账户之间拉开距离。

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

public class Program
{
    public struct Job
    {
        public string Site { get; set; }
        public string Account { get; set; }
    }


    private  static readonly Dictionary<string, List<string>> Dict = new Dictionary<string, List<string>>();
    private  static List<string> _accounts;


    public static void Main()
    {
        var sites = new List<string>{"Site-A", "Site-B", "Site-C", "Site-D", "Site-E"};
         _accounts = new List<string>{"Account-A", "Account-B", "Account-C", "Account-D", "Account-E"};

        // Permissions dictionary. specify accounts that has a permessions to  publish on a particular Site
        Dict.Add("Site-A", new List<string>{"Account-A", "Account-C"});
        Dict.Add("Site-B", new List<string>{"Account-A", "Account-E"});
        Dict.Add("Site-C", new List<string>{"Account-C", "Account-D"});
        Dict.Add("Site-D", new List<string>{"Account-A"});
        Dict.Add("Site-E", new List<string>{"Account-A"});

            var jobs = new List<Job>();
            foreach (var site in sites)
            {
                var job = new Job();

                // Get an account that has a permissions to publish on 'site'
                // checking against the permissions dictionary Dict
                var account = GetAccountCanPost(Dict, site, _accounts);

                job.Site = site;
                job.Account = account;

                jobs.Add(job);
            }


            var jobsCountForEachAccountDict = CalculateJobsCountForEachAccounts(jobs);

            //////#### Now.. We need to re Order Jobs and swipe it here before send it to processing ####.....//////

            foreach (var job in jobs)
            {
                Console.WriteLine(job.Account + " publish on " + job.Site);
            }

    }

     public static Dictionary<string, int> CalculateJobsCountForEachAccounts(List<Job> jobs)
        {
            var dict = new Dictionary<string, int>();

            foreach (var job in jobs)
            {
                if (dict.ContainsKey(job.Account))
                    dict[job.Account]++;
                else
                    dict.Add(job.Account, 1);
            }

            return dict;
        }


     public static string GetAccountCanPost(Dictionary<string, List<string>> dict, string targetSite, List<string> accounts)
        {
            var accountIdsAssoc = GetAccountsIdsAssociatedWithCommunity(dict, targetSite);

            var selectedId = PickRandom(accountIdsAssoc, new Random());
            var account = accounts.FirstOrDefault(s => s == selectedId);

            return account;
        }

     private static List<string> GetAccountsIdsAssociatedWithCommunity(Dictionary<string, List<string>> communitiesAccountsAssociationsDict, string communityId)
        {
            if (communitiesAccountsAssociationsDict.ContainsKey(communityId))
                return communitiesAccountsAssociationsDict[communityId];

            return null;
        }

         private static T PickRandom<T>(IList<T> list, Random random)
        {
            var index = random.Next(0, list.Count);
            return list[(int) index];
        }

}

创建工作时类似于这样:(在重新调整工作分配之前)

> Account-A Publish on Site-A 
> Account-E Publish on Site-B
> Account-D Publish on Site-C
> Account-A Publish on Site-D
> Account-A Publish on Site-E

上面创建的发布作业没有公平地分配给帐户，因为您可以看到“Account-A”分配了 3 个作业，而其他帐户可以发布到“Dict”中定义的“站点”，所以它应该看起来像这样的东西:

> Account-C Publish on Site-A
> Account-E Publish on Site-B
> Account-A Publish on Site-D
> Account-D Publish on Site-C
> Account-A Publish on Site-E

在上面的输出中，作业在账户上公平分配，而且拥有超过 1 个作业的账户之间存在距离

工作距离的例子:

    > Account-A Publish on Site-A 
    > Account-E Publish on Site-B
    > Account-D Publish on Site-C
    > Account-A Publish on Site-D
    > Account-A Publish on Site-E

作业 4 和 5 正在由帐户 A 处理。一个帐户不应按顺序处理两个作业，因此它可以与另一个作​​业交换。

如能提供帮助，将不胜感激。我需要一种算法来进行作业分配以获得类似的输出。性能并不重要。

谢谢你..

Answer 1

它可以改进，但这将满足您的需要:

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

namespace ConsoleApp1
{
    public struct Job
    {
        public string Site { get; set; }
        public string Account { get; set; }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            Dictionary<string, List<string>> permissionsDict = new Dictionary<string, List<string>>();
            permissionsDict.Add("Site-A", new List<string> { "Account-A", "Account-C" });
            permissionsDict.Add("Site-B", new List<string> { "Account-A", "Account-E" });
            permissionsDict.Add("Site-C", new List<string> { "Account-C", "Account-D" });
            permissionsDict.Add("Site-D", new List<string> { "Account-A" });
            permissionsDict.Add("Site-E", new List<string> { "Account-A" });

            // get responsibilities rate for each account

            Dictionary<string, int> responsibilitiesRate = GetResponsibilitiesRate(permissionsDict);

            List<Job> jobs = new List<Job>();

            // building jobs list

            foreach (var permission in permissionsDict)
            {
                var job = new Job();
                job.Site = permission.Key;

                // for the current site, see what account has lower responsibility rate
                int minResponsibilities = permission.Value.Min(x => responsibilitiesRate[x]);
                string account = permission.Value.First(x => responsibilitiesRate[x] == minResponsibilities);
                responsibilitiesRate[account]++;

                job.Account = account;
                jobs.Add(job);
            }

            // order jobs making sure distance between accounts has more than 1 job

            jobs = RandomOrderResponsibilities(jobs);

            foreach (var job in jobs)
            {
                Console.WriteLine(job.Account + " publish on " + job.Site);
            }

            Console.ReadLine();
        }

        private static Dictionary<string, int> GetResponsibilitiesRate(Dictionary<string, List<string>> dict)
        {
            Dictionary<string, int> responsibilitiesCount = new Dictionary<string, int>();

            foreach (var kvp in dict)
            {
                foreach (var account in kvp.Value)
                {
                    if (responsibilitiesCount.ContainsKey(account))
                    {
                        responsibilitiesCount[account]++;
                    }
                    else
                    {
                        responsibilitiesCount.Add(account, 1);
                    }
                }
            }

            return responsibilitiesCount.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
        }

        private static List<Job> RandomOrderResponsibilities(List<Job> jobs)
        {
            bool couldComplete = true;
            var maxIterations = 1000;
            var iterationCount = 0;

            do
            {
                // shuffle
                jobs = jobs.OrderBy(a => Guid.NewGuid()).ToList();

                for (int i = 1; i < jobs.Count; i++)
                {
                    if (jobs[i].Account == jobs[i - 1].Account)
                    {
                        couldComplete = false;

                        for (int j = i + 1; j < jobs.Count; j++)
                        {
                            if (jobs[j].Account != jobs[i].Account)
                            {
                                // swipe
                                var temp = jobs[i];
                                jobs[i] = jobs[j];
                                jobs[j] = temp;
                                couldComplete = true;
                                break;
                            }
                        }
                    }
                }

                iterationCount++;
            } while (!couldComplete && iterationCount < maxIterations);

            return jobs;
        }
    }
}

输出(随机解):

Account-A publish on Site-D
Account-C publish on Site-A
Account-A publish on Site-E
Account-D publish on Site-C
Account-E publish on Site-B