2

背景

在我学校的 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 等）都很熟悉，并且伪代码和流程图也可以使用。

4

3 回答 3

4

理论上，该解决方案可以适用于无限数量的列以及列中无限且变化的行数。

  1. 在填充列时将多主题行拆分为单独的行。
  2. 将列放在一个数组中，并以包含英语的列在前对其进行排序。
  3. 在任何列中仍然有英语的情况下迭代以下内容（我们将一一删除）：
    1. 总是取第一列。它包含英语。
    2. 选择它的英文作为本次迭代中所有组合的第一个元素。
    3. 递归地从其他列构造所有组合，注意消除重复。可行的，如果你绕过你当前的组合。
    4. 从此列中删除英文并再次对列进行排序（根据它们是否有英文）。

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

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

于 2013-04-05T09:43:04.313 回答
1

出于所有实际目的，包含两个主题的行本质上是两行。因此，表中的第 1 列实际上包含 5 行，而不是 4 行。

我要做的第一件事。如果给定这样的数据集。是将两个主题行展平。像这样的东西（伪代码）：

// Assuming:
grid = [
    [ economics, hindi/psychology, maths, english ] ,
    [
      // the rest is as per your table ...
    ],
]

foreach list grid {
    tmp = []
    while (list not empty) {
        item = list.pop()
        tmp.push(item.split('/'))
    }
    list = tmp
}

然后只需迭代每一列并丢弃不包含英文或包含重复项的结果：

result = []

foreach item1 grid[0] {
  foreach item2 grid[1] {
    foreach item3 grid[2] {
      foreach item4 grid[3] {

        tmp = [item1,item2,item3,item4]

        if (not tmp.contains_duplicate && tmp.contains(english)) {
            result.push(tmp)
        } 
      }
    }
  }
}

嵌套的 for 循环基本上是您遍历所有组合的方式。您可以添加任何要过滤掉不需要的结果的条件。

于 2013-04-05T09:11:04.017 回答
1

我将从处理具有多个值的单元格开始。我们可以将第一列转换为以下列表：

Economics
Hindi
Psychology
Maths
English

由于您只能在每一列中选择一个类，这不会引入任何问题，并且可以针对每一列进行。

现在，处理英语有点不同。我将把不同的列称为句点。您知道学生必须在第 1 期、第 4 期或第 5 期学习英语。

因此，在第 1 列中列出所有选择了英语的组合。接下来，在第 4 列中列出所有选择了英语的组合。然后在第 5 列中列出所有选择了英语的组合。

您需要决定学生是否可以在多个栏中选择英语。如果是这样，您将需要单独处理这些，因此您不会重复计算，如下所示：

  • 仅在第 1 列中与英语组合
  • 仅在第 4 栏中与英语组合
  • 仅在第 5 栏中与英语组合
  • 仅在第 1,4 列中与英语组合
  • 仅在第 1,5 列中与英语组合
  • 仅在第 4,5 列中与英语组合
  • 仅在第 1、4、5 列中与英语组合

它确实有点复杂，但这样你就不会多算，并且能够列出所有组合。

于 2013-04-05T09:13:49.537 回答