Подсчитайте количество различных элементов в массиве

Я новичок в программировании с ограничениями и в Minizinc. Я искал решение этой несложной задачи, но ничего не нашел.

Я хочу подсчитать количество различных элементов, которые появляются в массиве: это объявление моего массива:

array[1..n,1..n] of var 1..n: countLeft;

Я пытаюсь сделать вот так:

constraint 
   forall(j in 1..n) (
        length(array2set([countLeft[i,j]|i in 1..stopCountLeft[j]]) )==left_vision[j]
        );

Но, по-видимому, мой массив имеет тип: array [int] of var opt int и не принимается функцией array2set.

Любые идеи?


arrays set constraints count minizinc
person Aldebert Lucie    schedule 06.10.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете использовать разные подходы, но подход, аналогичный тому, что вы пробуете, состоит в том, чтобы разделить подсчет различных элементов в массиве на два этапа:

  1. Подсчет появления значений в домене.
  2. Подсчет количества раз, когда вхождение больше нуля.

Мы можем использовать глобальное ограничение global_cardinality для подсчета вхождений, а затем использовать ограничение простого подсчета для его результата.

include "global_cardinality_fn";

array[1..n] of var int: occurrences = global_cardinality(YOURARRAY, [i | i in 1..n]);

var int: num_diff = count(o in occurrences) (o > 0);

Обратите внимание, однако, что это может быть не лучший код для вашей модели. Некоторые решатели global_cardinality могут работать недостаточно хорошо. Аналогично, если ваш stopCountLeft содержит переменные, это означает, что вы создаете массив необязательных переменных, и global_cardinality может не быть определен для необязательных переменных.

Вместо этого мы можем написать график импликации. Идея все та же, но вместо подсчета количества появившихся значений мы просто используем логическое значение, чтобы сигнализировать, используется ли это значение.

array[1..n] of var bool: occurs;

constraint forall(i,j in 1..n) (YOURARRAY[i] = j -> occurs[j]);

var int: num_diff = count(occurs);

Обратите внимание, что проблема с этим подходом заключается в экспоненциальном количестве последствий, размещенных в цикле forall. Однако я подозреваю, что с небольшими последствиями он будет работать достаточно хорошо.

person Dekker1    schedule 06.10.2020

arrow_upward
2
arrow_downward

В MiniZinc 2.5.0 можно сделать что-то вроде этого:

array[int, int] of int: a = 
  [| 1, 1,
   | 2, 3, 
   | 3, 4 |];

set of int: Rows = index_set_1of2(a);
set of int: Cols = index_set_2of2(a);

int: values = card({ a[r, c] | r in Rows, c in Cols });

output ["\(values) values in "] ++ 
       [if c == 1 then "\n" else "" endif ++ 
        "\(a[r, c]) " | r in Rows, c in Cols];
person Axel Kemper    schedule 07.10.2020