Индекс строкового значения в массиве MiniZinc

Вопрос

Имеется массив строк MiniZinc:

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

... с данными, загруженными из файла данных MiniZinc:

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

Как можно найти индекс конкретной строки в массиве? Например, этот ARMOR находится в позиции 2.

Контекст

Мне нужно найти оптимальный выбор предметов с учетом некоторых ограничений их характеристик. Эта информация хранится в двумерном массиве, объявленном следующим образом:

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 ответа

Вы можете написать свою собственную пользовательскую функцию, чтобы получить индекс строки в массиве строк:

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 либо равен индексу str если string_array[i]=str а также 0 иначе. Например, для вашего образца массива строк ["HEALTH", "ARMOR", "MANA"] и ул 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)), то вам нужно будет адаптировать функцию.

Источник

Другой, более чистый вариант - написать функцию, которая использует рекурсивную вспомогательную функцию:

% 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,

Источник

Альтернативный подход, предложенный 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-set из array of strings literal это присваивается ему. Это правило применяется в более новых версиях, так же как и для других типов данных.

Источник

Согласно этому другому посту о Stackru, в MiniZinc нет способа конвертировать строки в целые числа, только наоборот. Сначала вам нужно предварительно обработать данные на другом языке и превратить их в целые числа. Однако вы можете превратить эти целые числа в строку, как только закончите в MiniZinc.

Однако вы можете загрузить файлы MiniZinc вместо файлов данных, если хотите. Используйте синтаксис include для включения любого файла.mzn.

Источник
Другие вопросы по тегам