适合从记录中提取 OneToMany 关系的约束编程

也许有人可以帮助我解决 Prolog 或任何约束编程语言的问题。想象一个项目表（学生与母亲一起做某事的学校项目）。每个项目都有一名或多名儿童参与。对于每个孩子，我们存储其姓名及其母亲的姓名。但对于每个项目，只有一个包含所有母亲的单元和一个包含所有孩子的单元。两个单元不一定以相同的方式排序。

Example:

+-----------+-----------+------------+
|           |           |            |
|   Project |   Parents |   Children |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   1       |   Jane;   |   Brian;   |
|           |   Claire  |   Stephen  |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   2       |   Claire; |   Emma;    |
|           |   Jane    |   William  |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   3       |   Jane;   |   William; |
|           |   Claire  |   James    |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   4       |   Jane;   |   Brian;   |
|           |   Sophia; |   James;   |
|           |   Claire  |   Isabella |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   4       |   Claire  |   Brian    |
|           |           |            |
+-----------+-----------+------------+
|           |           |            |
|   5       |   Jane    |   Emma     |
|           |           |            |
+-----------+-----------+------------+

我希望这个例子能够直观地说明问题。正如我所说，两个单元格仅包含由分隔符分隔的名称，但不一定以类似的方式排序。因此，对于技术应用，您可以将数据转换为：

+-------------+-----------+----------+
|   Project   |   Name    |   Role   |
+-------------+-----------+----------+
|   1         |   Jane    |   Mother |
+-------------+-----------+----------+
|   1         |   Claire  |   Mother |
+-------------+-----------+----------+
|   1         |   Brian   |   Child  |
+-------------+-----------+----------+
|   1         |   Stephen |   Child  |
+-------------+-----------+----------+
|   2         |   Jane    |   Mother |
+-------------+-----------+----------+
|   2         |   Claire  |   Mother |
+-------------+-----------+----------+
|   2         |   Emma    |   Child  |
+-------------+-----------+----------+
|   2         |   William |   Child  |
+-------------+-----------+----------+
|             |           |          |
|                                    |
|              And so on             |

每个项目的家长和孩子人数都是相等的。因此，对于每一笔交易，我们都有 n 个母亲和 n 个孩子，并且每个母亲恰好属于一个孩子。有了这些限制，就可以从只涉及一个孩子（即 4 和 5）的项目开始，通过逻辑推理将每位母亲分配给她的所有孩子。

Results:

简有艾玛、史蒂芬和詹姆斯；

克莱尔有布莱恩和威廉；

索菲亚有伊莎贝拉

我想知道如何使用约束编程来解决这个问题。此外，数据集可能是不确定的，我想知道是否可以隔离记录，当手动解决时（即，当手动完成母子分配时），会打破不确定性。

我不确定我是否理解问题的所有要求，但这是 MiniZinc 中的约束规划模型（http://www.minizinc.org/ http://www.minizinc.org/）。完整模型在这里：http://hakank.org/minizinc/one_to_many.mzn http://hakank.org/minizinc/one_to_many.mzn .

稍后注意：项目约束的第一个版本不正确。我已经删除了不正确的代码。请参阅原始答案的编辑历史记录。

enum mothers = {jane,claire,sophia};
enum children = {brian,stephen,emma,william,james,isabella};      

% decision variables

% who is the mother of this child?
array[children] of var mothers: x;


solve satisfy;

constraint
  % All mothers has at least one child
  forall(m in mothers) (
    exists(c in children) (
      x[c] = m
    )
  )
;

constraint
% NOTE: This is a more correct version of the project constraints.
% project 1
(
  ( x[brian] = jane /\ x[stephen] = claire) \/
  ( x[stephen] = jane /\ x[brian] = claire)
) 
/\
% project 2
(
  ( x[emma] = claire /\ x[william] = jane) \/
  ( x[william] = claire /\ x[emma] = jane) 
)
/\
% project 3
(
  ( x[william] = claire /\ x[james] = jane) \/
  ( x[james] = claire /\ x[william] = jane) 
)
/\
% project 4
( 
  ( x[brian] = jane /\ x[james] = sophia /\ x[isabella] = claire) \/
  ( x[james] = jane /\ x[brian] = sophia /\ x[isabella] = claire) \/
  ( x[james] = jane /\ x[isabella] = sophia /\ x[brian] = claire) \/
  ( x[brian] = jane /\ x[isabella] = sophia /\ x[james] = claire) \/
  ( x[isabella] = jane /\ x[brian] = sophia /\ x[james] = claire) \/
  ( x[isabella] = jane /\ x[james] = sophia /\ x[brian] = claire) 
)
/\

% project 4(sic!)
( x[brian] = claire) /\

% project 5
( x[emma] = jane)
;


output [
  "\(c): \(x[c])\n"
  | c in children
];

唯一的解决方案是

brian: claire
stephen: jane
emma: jane
william: claire
james: jane
isabella: sophia

Edit2：这是一个更通用的解决方案。看http://hakank.org/minizinc/one_to_many.mzn http://hakank.org/minizinc/one_to_many.mzn对于完整的模型。

include "globals.mzn"; 

enum mothers = {jane,claire,sophia};
enum children = {brian,stephen,emma,william,james,isabella};      

% decision variables
% who is the mother of this child?
array[children] of var mothers: x;

% combine all the combinations of mothers and children in a project
predicate check(array[int] of mothers: mm, array[int] of children: cc) =
  let {
    int: n = length(mm);
    array[1..n] of var 1..n: y;
  } in
  all_different(y) /\
  forall(i in 1..n) (
     x[cc[i]] = mm[y[i]]
  )
;    

solve satisfy;

constraint
% All mothers has at least one child.
forall(m in mothers) (
  exists(c in children) (
    x[c] = m
  )
)
;


constraint
% project 1    
check([jane,claire], [brian,stephen]) /\
% project 2
check([claire,jane],[emma,william]) /\
% project 3
check([claire,jane],[william,james]) /\
% project 4
check([claire,sophia,jane],[brian,james,isabella]) /\
% project 4(sic!)
check([claire],[brian]) /\
% project 5
check([jane],[emma])
;

output [
 "\(c): \(x[c])\n"
 | c in children
];

该模型使用以下谓词来确保考虑母亲与孩子的所有组合：

predicate check(array[int] of mothers: mm, array[int] of children: cc) =
   let {
     int: n = length(mm);
     array[1..n] of var 1..n: y;
  } in
  all_different(y) /\
  forall(i in 1..n) (
    x[cc[i]] = mm[y[i]]
  )
;    

它使用全局约束all_different(y)为了保证mm[y[i]]是其中一位母亲mm，然后将第 i 个孩子分配给该特定母亲。