查找具有独特条件的学习科目的所有不同组合

Question

这是一项大学任务。我知道如何找到数字，字母等的排列，但这是完全不同的。这是任务：

一名学生正在一所大学学习。所有的学习模块（科目）都是有选择的。所有需要被挑选。某些模块只能在挑选某些模块后才能选择。学生需要形成一个学习计划，其中的模块将形成一个清单。构成列表的模块取决于早先选择的模块。创建一个可以安排所有可能列表的程序。数据文件像这样排列（第一行是模块数量）：模块代码，模块名称，给定依赖的模块数量，从属模块代码;一个可能的列表（与模块代码及其名称的列表）的

9 
IF01 Programming 0 
IF02 Maths 1 IF01 
IF03 Data structures 2 IF01 IF02 
IF04 Digital logic 0 
IF05 Mathematical logistics 1 IF04 
IF06 Operations optimization 1 IF05 
IF07 Algorithm analysis 2 IF03 IF06 
IF08 Programming theory 1 IF03 
IF09 Operating systems 2 IF07 IF08 

结果文件例如：

IF01 Programming 
IF04 Digital logic 
IF02 Maths 
IF03 Data structures 
IF08 Programming theory 
IF05 Mathematical logistics 
IF06 Operations optimization 
IF07 Algorithm analysis 
IF09 Operating systems 

可以有更少或更多的模块。这些文件就是例子。该方案应该是一般化的。它表示还应该使用循环方法。

请帮忙。不知道如何形成条件。

Answer 1

一种方法是在代码中解释以下内容（我希望评论是明确的，但如果不是，请告诉我）。

原理是将模块形式化为包含其依赖的其他模块的对象。

然后每一步，尝试找到可能的模块并生成它们的排列。

当所有模块“消耗”时，我们有一个解决方案。

// Defines a module as having a name and a list of modules it depends on to be eligible 
class Module 
{ 
    public string Name { get; set; } 
    public List<Module> DependsOn { get; set; } 
} 

// Represents a solution as a list of modules 
class Solution 
{ 
    public List<Module> Modules { get; set; } 
} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // Defines the modules 
     var if01 = new Module() { Name = "IF01" }; 
     var if02 = new Module() { Name = "IF02" }; 
     var if03 = new Module() { Name = "IF03" }; 
     var if04 = new Module() { Name = "IF04" }; 
     var if05 = new Module() { Name = "IF05" }; 
     var if06 = new Module() { Name = "IF06" }; 
     var if07 = new Module() { Name = "IF07" }; 
     var if08 = new Module() { Name = "IF08" }; 
     var if09 = new Module() { Name = "IF09" }; 

     // Defines on which other modules each module depends on 
     if01.DependsOn = new List<Module>(); 
     if02.DependsOn = new List<Module>() { if01 }; 
     if03.DependsOn = new List<Module>() { if01, if02 }; 
     if04.DependsOn = new List<Module>(); 
     if05.DependsOn = new List<Module>() { if04 }; 
     if06.DependsOn = new List<Module>() { if05 }; 
     if07.DependsOn = new List<Module>() { if03, if06 }; 
     if08.DependsOn = new List<Module>() { if03 }; 
     if09.DependsOn = new List<Module>() { if07, if08 }; 

     // The list of all modules 
     var allModules = new List<Module>() { if01, if02, if03, if04, if05, if06, if07, if08, if09 }; 
     // The list of choosen modules at this step 
     var choosenModules = new List<Module>(); 

     // Writes each found solution 
     foreach (var solution in Calculate(choosenModules, allModules)) 
     { 
      solution.Modules.ForEach(m => Console.Write(m.Name + "/")); 
      Console.WriteLine(); 
     } 
    } 

    // Determinates if a module is eligible considering already choosed modules 
    static bool IsEligible(Module module, List<Module> alreadyChoosed) 
    { 
     // All modules this module depends on needs to be present in the allready choosen modules 
     return module.DependsOn.All(m => alreadyChoosed.Contains(m)); 
    } 

    static IEnumerable<Solution> Calculate(List<Module> choosenModules, List<Module> remainingModules) 
    { 
     if (remainingModules.Count > 0) 
     // If some modules remain, we need to continue 
     { 
      // Takes the list of all eligible modules at this step 
      var allEligibleModules = remainingModules.FindAll(m => IsEligible(m, choosenModules)); 

      // We explore the solutions 
      foreach (var newlyChoosen in allEligibleModules) 
      { 
       // Considering this newly choosen module... 
       choosenModules.Add(newlyChoosen); 
       // ... which is so no more in the remaining modules 
       remainingModules.Remove(newlyChoosen); 

       // And try to find all solutions starting with this newly choosen module 
       foreach (var solution in Calculate(choosenModules, remainingModules)) 
        yield return solution; 

       // As we have tested this module we push it back as unchoosed, so that the next possible will take its place in the solution 
       choosenModules.Remove(newlyChoosen); 
       remainingModules.Add(newlyChoosen); 
      } 
     } 
     else 
     // If no more remaining modules, we have a solution 
      yield return new Solution() { Modules = new List<Module>(choosenModules) }; 
    } 

Answer 2

这是一种使用递归获取置换的方法。不知道从哪里走得更远，希望至少有助于这一点。

class Program 
{ 
private static void Swap(ref char a, ref char b) 
{ 
    if (a == b) return; 

    a ^= b; 
    b ^= a; 
    a ^= b; 
} 

public static void GetPer(char[] list) 
{ 
    int x = list.Length - 1; 
    GetPer(list, 0, x); 
} 

private static void GetPer(char[] list, int k, int m) 
{ 
    if (k == m) 
    { 
     Console.Write(list); 
    } 
    else 
     for (int i = k; i <= m; i++) 
     { 
       Swap(ref list[k], ref list[i]); 
       GetPer(list, k + 1, m); 
       Swap(ref list[k], ref list[i]); 
     } 
} 

static void Main() 
{ 
    string str = "sagiv"; 
    char[] arr = str.ToCharArray(); 
    GetPer(arr); 
} 

}