c# - 多个列表的排列

Question

我需要将 worker 安排到特定类次的工作岗位。 worker 们对他们希望从事的工作设定了优先顺序。工作时间最少的 worker 优先获得工作机会。只有一名 worker 可以从事某项特定工作。

我尝试通过创建锯齿状数组来解决这个问题。该数组按工作时间最少的 worker 排序。每个子数组都是一个特定的 worker 偏好列表。数组中的数字就是职位代码。然后我生成排列，直到得到有效的解决方案。

例如，下面是 28 名 worker 的列表以及每个 worker 的工作偏好。

int[][] preference = {
    new int[] {1,2,3,4,5,6,7,8,11,12,13,14,15},
    new int[] {2,4,5,6,7,8,11,12,13,14,15},
    new int[] {1,3,6,7,8,9,10,14,15,18,19,22,23,24,26,27,29,30,32,34,35,25,36},
    new int[] {4,5,12,13},
    new int[] {9,10,11,14,15,1,2,6},
    new int[] {9,10,11,14,2,6,18,19,27,29,30,31,32,35},
    new int[] {11,12,13,14,2,4,5,6},
    new int[] {12,13,4,5},
    new int[] {9,10,11,13,14,15,1,2,6,7,8,18,19,21,22,23,24,26,27,28,29,30,31,32,34,35,16,17,33,36},
    new int[] {1,2,9,10,11,14,15,18,19,30,31,32,35,37,33},
    new int[] {4,13,18,19,35},
    new int[] {18,19,35},
    new int[] {21,22,23,24,18,19},
    new int[] {22,23,24,25,18,19,16,17},
    new int[] {18,19,23,24,35},
    new int[] {18,19,23,24,35},
    new int[] {27,26,28,29,30,32,34,35,36},
    new int[] {27,26,30,32,34,35,36},
    new int[] {28,29,30,31,32,33,35},
    new int[] {28,29,30,31,32,33,26,35,36},
    new int[] {26,29,30,31,32,34,35,36},
    new int[] {28,29,31,32,33,26,35,36},
    new int[] {27,28,29,30,31,32,35,33,1,2,3,9,10,11,14,18,19,6,15},
    new int[] {34,35,36,26,27,31,32},
    new int[] {31,32,34,35,2,11,14,18,19,23,24,6,15,16,17,20},
    new int[] {37,29,30,31,32,35,33,36,2,9,10,11,14,18,19,23,24,6,15,16,17},
    new int[] {18,19,35},
    new int[] {18,19,35},
};

preference[0] 包含第一个工作人员首选项列表。 prererence[1] 包含第二个 worker 偏好列表，依此类推。在此示例中，第一个工作人员选择了工作 1,2,3,4,5,6,7,8,11,12,13,14,15。 正确的解决方案是:1,2,3,4,9,10,11,12,14,15,13,​​18,21,22,23,24,27,26,28,29,30 ,31,32,34,6,37,19,35。

我遇到的问题是性能。我尝试使用递归和非递归循环进行迭代，但性能很糟糕。我的想法是必须有一种不同的方法来解决问题，或者已经有一个我可以购买的库可以解决这个问题。预先感谢您的帮助。

Answer 1

当你有

1. 您的员工按照“谁先挑选”进行排序
2. 偏好按偏好降序排序，
3. 每个 worker 只能分配一项任务

然后我认为作业分配算法应该可以使用两个游标和已分配作业列表以类似 O(n2 log(n))) 的方式执行。

是否还有您未说明的其他解决方案优化要求？:例如

1. 您需要找到一种解决方案，让尽可能少的 worker 分配到他们根本不喜欢的工作。或
2. 所有已分配职位的偏好等级总和应是数学上可能的最低值。

如果是这样，算法将会更加复杂。

如果您所说的“有效解决方案”是指所有 worker 都从他们的偏好列表中获得工作的任何工作分配，那么我会质疑您的算法作为现实世界轮类工作答案的适用性分配问题。您经常会找不到解决方案。