3

问题

给定一个 MiniZinc 字符串数组：

int: numStats;
set of int: Stats = 1..numStats;
array[Stats] of string: statNames;

... 从 MiniZinc 数据文件加载数据：

numStats = 3;
statNames = ["HEALTH", "ARMOR", "MANA"];

如何查找数组中特定字符串的索引？例如，该 ARMOR 位于位置 2。

上下文

我需要针对其统计数据的某些限制找到最佳的项目选择。此信息存储在一个 2D 数组中，声明如下：

int: numItems;
set of int: Items = 1..numItems;
array[Items, Stats] of float: itemStats;

因此，为了对通过所选项目获得的最小 ARMOR 数量进行约束，我需要知道 ARMOR 在内部数组中的索引为 2。

由于数据文件是由外部程序生成的，并且统计数据的数量和顺序是动态的，因此我无法对约束中的索引进行硬编码。

一种解决方案（在我的情况下不起作用）

MiniZinc教程使用了一个有趣的技巧来实现类似的效果：

set of int: Colors = 1..3;
int: red = 1;
int: yellow = 2;
int: blue = 3;
array[Colors] of string: name = ["red", "yellow", "blue"];

var Colors: x;
constraint x != red;
output [ name[fix(x)] ];

不幸的是，由于 MiniZinc 数据文件中不允许变量声明，所以这个技巧在我的情况下不起作用。

4

4 回答 4

5

您可以编写自己的自定义函数来获取字符串数组中字符串的索引：

function int: getIndexOfString(string: str, 
                               array[int] of string: string_array) = 
   sum(  [ if str = string_array[i] 
              then i
           else 0 endif  
          | i in index_set(string_array) ]
   );

在这个函数中，我创建了一个整数数组，其中位置处的整数i要么等于strifstring_array[i]=str的 索引，要么等于其他的索引0。例如，对于您的示例字符串数组["HEALTH", "ARMOR", "MANA"]和 str ARMOR，生成的 int 数组将为[0,2,0].

这就是为什么我可以简单地对 int 数组求和以获得字符串的索引。如果字符串不出现，则返回值为0，这很好，因为 MiniZinc 中的索引默认以 1 开头。

以下是第一个示例调用上述函数的方法：

int: numStats;
set of int: Stats = 1..numStats;
array[Stats] of string: statNames;

numStats = 3;
statNames = ["HEALTH", "ARMOR", "MANA"];

var int: indexOfArmor;

constraint 
   indexOfArmor = getIndexOfString("ARMOR",statNames);  

solve satisfy;

但是请注意，上面的功能是有限的并且有一些缺陷。首先，如果您在数组中多次出现该字符串，那么您将收到一个无效索引（出现的所有索引的总和str）。此外，如果您为字符串数组（例如(2..6)）设置了自己的索引，那么您将需要调整该函数。

于 2017-06-30T12:53:58.337 回答
2

Andrea Rendl-Pitrey提出的另一种方法如下：

array[int] of string: statNames = array1d(10..12, ["HEALTH", "ARMOR", "MANA"]);

var int: indexOfArmor =
    sum([i | i in index_set(statNames) where statNames[i] = "ARMOR"]);

solve satisfy;  

output [
   "indexOfArmor=", show(indexOfArmor), "\n",
];

输出：

~$ mzn2fzn example.mzn ; flatzinc example.fzn
indexOfArmor = 11;
----------

注意：可以var从 的声明中删除indexOfArmor，因为可以静态计算索引。我把它放在这里只是为了输出目的。

更好的解决方案是声明一个新的predicate：

predicate index_of_str_in_array(var int: idx, 
                                string: str,
                                array[int] of string: arr) =
    assert(
        not exists(i in index_set(arr), j in index_set(arr))
                  (i != j /\ arr[i] = str /\ arr[j] = str), 
        "input string occurs at multiple locations",
    assert(
        exists(i in index_set(arr))
              (arr[i] = str),
        "input string does not occur in the input array",

        exists(i in index_set(arr))
              (arr[i] = str /\ i = idx)
    ));

它强制执行以下两个条件：

  • str至少发生一次arr
  • str不会出现多次arr

例如

predicate index_of_str_in_array(var int: idx,
                                string: str,
                                array[int] of string: arr) =
            ...

array[10..13] of string: statNames =
                 array1d(10..13, ["HEALTH", "ARMOR", "MANA", "ATTACK"]);

var int: indexOfArmor;

constraint index_of_str_in_array(indexOfArmor, "ARMOR", statNames);

solve satisfy;  

output [
   "indexOfArmor=", show(indexOfArmor), "\n",
];

输出

~$ mzn2fzn example.mzn ; flatzinc example.fzn
indexOfArmor = 11;
----------

如果statNames按照以下方式更改

array[10..13] of string: statNames =
                 array1d(10..13, ["HEALTH", "ARMOR", "MANA", "ARMOR"]);

然后 mzn2fzn检测到断言违规：

~$ mzn2fzn example.mzn ; flatzinc example.fzn
MiniZinc: evaluation error: 
  example.mzn:24:
  in call 'index_of_str_in_array'
  example.mzn:4:
  in call 'assert'
  Assertion failed: input string occurs at multiple locations
flatzinc:
  example.fzn: cannot open input file: No such file

通过搜索未出现在数组中的字符串的索引可以获得类似的结果。如果没有必要，当然可以去除这种情况。

免责声明：旧版本的mzn2fzn似乎不检查声明index-set的变量是否与分配给它的array of strings变量匹配。此规则在较新版本上强制执行，因为它也适用于其他数据类型。index-setarray of strings literal

于 2017-10-27T22:48:28.310 回答
1

根据Stackoverflow 上的另一篇文章，在 MiniZinc 中无法将字符串转换为整数，只能反过来。您需要首先用其他语言预处理您的数据并将其转换为整数。但是，在 MiniZinc 中完成后，您可以将这些整数转换为字符串。

但是，如果您愿意，您可以加载 MiniZinc 文件而不是数据文件。使用包含语法来包含任何 .mzn 文件。

于 2016-03-02T23:58:11.680 回答
1

另一个更简洁的选择是编写一个使用递归辅助函数的函数：

% main function
function int: index_of(string: elem, array[int] of string: elements) =
      let {
        int: index = length(elements);
      } in    % calls the helper function with the last index
        get_index(elem, elements, index)
; 

% recursive helper function    
function int: get_index(string: elem, array[int] of string: elements, int: index) = 
    if index == 0 
        then -1  % the element was not found (base case of recursion)
    elseif elements[index] == elem 
        then index % the element was found
    else 
        get_index(elem, elements, index - 1) % continue searching
    endif  
;

辅助函数从最后一个元素开始递归地遍历数组，当它找到该元素时，它返回索引。如果在数组中未找到该元素，则-1返回。或者，您也可以按照Patrick Trentin的建议，通过替换then -1为then assert(false, "unknown element: " + elem).

调用此函数的示例：

set of int: Customers =  1..5;
array[Customers] of string: ids = ["a-1", "a-2", "a-3", "a-4", "a-5"];

var int: index = index_of("a-3", ids); 
var int: unknown_index = index_of("x-3", ids);

将在哪里index分配3和unknown_index将在哪里-1。

于 2018-11-30T14:20:35.057 回答