c# - 以并行方式查找排列

Question

如何编写一个程序以并行方式查找序列的所有排列？

更准确地说，我正在编写一个程序来查找学生想要参加的类(class)的所有可能时间表。

假设一个学生想参加 CC101 和 CC102。

有 3 位教师在教授 CC101(CC101.A、CC101.B、...)和 2 位教师在教授 CC102。

组合将是

[CC101.A, CC102.A]
[CC101.A, CC102.B]
[CC101.B, CC102.A]
[...]
[CC101.C, CC102.B]

(当然，忽略那些类同时发生冲突/发生的情况)。

我目前处理这个问题的方式是使用一个递归函数，它基本上看起来像这样:

private List<Schedule> Schedules {get; set;}
public FindSchedules(Course[] courses)
{
   FindSchedules(new sched(), courses, 0);
   return this.Schedules;
}

private void FindSchedules(Schedule sched, Course[] courses, int courseIndex)
{
   if(i>= courses.length)
   {
      //class property
      this.Schedules.Add(sched.Clone());
   }
   foreach(var class in Courses[courseIndex].Classes)
   { 
     if(sched.ConflictsWith(class) continue;

     sched.Add(class);
     FindSchedules(sched, courses, courseIndex +1)
     sched.remove(class);
   }   
}

这实际上工作得很好，但对于具有大量类(class)的大量类(class)，它可以开始建立起来。 (# of Possible combinations are Courses[0].Classes.Count * Courses[1].Classes.Count * ...* Courses[N].Classes.Count)

我想知道是否有办法让它并行工作。我在想我也许可以做 Task.Run(()=>FindSchedules(sched.Clone(), courses, courseIndex +1));，但显然我不想让所有像这样的调用，只是其中的前几个，然后是它们的子调用是常规的递归调用。

有没有现成的算法策略？

谢谢!

Answer 1

以下是一些提出并行排列算法的论文的引用资料。

Parallel Generation of Permutations by Inversion Vectors

An optimal parallel algorithm for generating permutations in minimal change order

Parallel generation of permutations and combinations

Parallel Generation of Permutations