algorithm - 寻找所有可能和独特的组合

Question

我想用 Scala 解决简单的资源分配问题。
我现在拥有的是能够执行此任务的任务和资源列表:

val t1 = List(1, 2)
val t2 = List(2, 3, 4)
val t3 = List(0)
val t4 = List(1, 4)

其中 t 只是任务，列表代表资源 ID。假设我可以像这样组合任务 ID 和资源 ID:

val a1 = List((1, 1), (1, 2))
val a2 = List((2, 2), (2, 3), (2, 4))
val a3 = List((3, 0))
val a4 = List((4, 1), (4, 4))

其中 a 代表特定任务的分配。

所以下一步是收集所有作业并将它们平放在一个列表中:

val assignments = List((1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 0), (4, 1), (4, 4))

我想要的是所有可能的组合，其中包含每个任务 ID 都不同的分配列表。

val result1 = List((1, 1), (2, 3), (3, 0), (4, 4))
val result2 = List((1, 2), (2, 2), (3, 0), (4, 1))
...

我该怎么做？

Answer 1

任务数是否固定为4个？如果是这样，这很简单:

val t1 = List(1, 2)
val t2 = List(2, 3, 4)
val t3 = List(0)
val t4 = List(1, 4)

val as = for {
  a1 ← t1
  a2 ← t2
  a3 ← t3
  a4 ← t4
} yield List((1,a1), (2, a2), (3, a3), (4, a4))

as foreach println

输出是:

List((1,1), (2,2), (3,0), (4,1))
List((1,1), (2,2), (3,0), (4,4))
List((1,1), (2,3), (3,0), (4,1))
List((1,1), (2,3), (3,0), (4,4))
List((1,1), (2,4), (3,0), (4,1))
List((1,1), (2,4), (3,0), (4,4))
List((1,2), (2,2), (3,0), (4,1))
List((1,2), (2,2), (3,0), (4,4))
List((1,2), (2,3), (3,0), (4,1))
List((1,2), (2,3), (3,0), (4,4))
List((1,2), (2,4), (3,0), (4,1))
List((1,2), (2,4), (3,0), (4,4))