algorithm - 来自非统一表的所有可能组合，每列只有一个值

Question

背景

在我学校的 11 年级，我们需要从预定义科目列表中选修 4 门科目和英语。今天，我们得到了一个网格，可以帮助我们进行组合，这样你只能从每一列中选择一个主题。

网格

|    Economics     |   Maths  | Psychology/Politcal Science |                     English                      |     Geography    |
| Hindi/Psychology |  History |          Sociology          |                       Art                        | Elective English |
|      Maths       |  Account |          Commerce           |                    Economics                     |      English     |
|     English      |  Physics |          Chemistry          | Biology/Computer Applications/Mecahnical drawing |       Maths      |

问题

我正在尝试编写一个程序来列出该表中所有可能的合法组合。规则是:

• 英语必须存在
• 总共必须只有五门科目(英语+4)
• 两个主题不能来自同一列
• 最后五门科目不得重复(请注意，选修英语和英语是不同的科目)

现在，如果它是一个普通的 4 x 5 矩阵，这将是一个非常简单的任务。但是，[第 1 行第 3 列]、[第 2 行第 1 列] 和 [第 4 行第 4 列] 包含多个主题，您仍然只能从中选择一个。因此，与任何这些单元格的任何组合都可以分割为更多组合。

我在想出一个算法时遇到了麻烦。我不是要免费代码，而是帮助算法。我熟悉大多数主要语言(Java、JavaScript、PHP 等)，而且伪代码和流程图也能正常工作。

Answer 1

理论上，此解决方案适用于无限数量的列和列中无限多变的行。

1. 在填充列时将多主题行拆分为单独的行。
2. 将列放在一个数组中，并以包含英文的列在前对其进行排序。
3. 在任何列中仍有英文的情况下重复以下内容(我们将逐一删除):
   1. 始终占据第一列。它包含英文。
   2. 选择它的英语作为本次迭代中所有组合的第一个元素。
   3. 递归地构建其他列的所有组合，注意消除重复项。可行，如果您放弃当前的组合。
   4. 从该列中删除英文并再次对列进行排序(基于是否有英文)。

这应该会为您提供所有以英语开头并消除所有重复项的组合。

编辑:我实现了上面的解决方案，它似乎有效。在这里检查 - https://github.com/zupper/so-answers/tree/master/RaghavCombos