如何在MiniZinc中折叠数组?

huangapple go评论91阅读模式
英文:

How can I fold an array in MiniZinc?

问题

MiniZinc教程中定义密码算术的加数值的方式如下所示参考:

constraint           1000 * S + 100 * E + 10 * N + D
                   + 1000 * M + 100 * O + 10 * R + E
       = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

这对于一个示例可能没问题,但如果我想解决更多的密码算术问题,并且编写这样的求和看起来相当繁琐。是否有一种方法可以使用变量列表来计算总和,比如通过类似折叠的方式?在Haskell中,我会这样写:

ghci> foldl (\x y -> 10 * x + y) 0 [1, 3, 4, 1, 5]
13415

我查看了文档,但迄今为止没有找到相关的内容。

英文:

The way that value of summands of cryptarithms are defined in MiniZinc tutorial look like follows:

constraint           1000 * S + 100 * E + 10 * N + D
                   + 1000 * M + 100 * O + 10 * R + E
       = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

This is probably OK for one example, but if I want to solve more cryptarithms, and writing sums like this looks rather tedious. Is there a way to compute the sum using a list of variables, say, via something like a fold? In Haskell, I would write this:

ghci> foldl (\x y -> 10 * x + y) 0 [1, 3, 4, 1, 5]
13415

I've looked in the docs and haven't found anything relevant so far

答案1

得分: 1

这是我倾向于用于连接数组中的数字(a)以形成给定(且固定)基数(base)的函数:

% n = to_num_base(a, base)
function var int: to_num_base(array[int] of var int: a, int: base) =
          let { int: len = card(index_set(a));
                var int: n = sum(i in index_set(a)) (
                   pow(base, len-i) * a[i] 
                 );
         } in n
;

% base 10
function var int: to_num(array[int] of var int: a) = to_num_base(a, 10);

这是一个简单的测试模型(http://hakank.org/minizinc/to_num.mzn):

include "globals.mzn"; 

int: m = 10;

var 1..pow(10,m)-1: n;
array[1..m] of var 0..9: x;

solve satisfy;

constraint
   n = to_num(x) /\
   all_different(x) /\
   x[3] = 4 /\
   n >= 50000 /\
   n mod 2 = 0
;

output [
  "x: ", show(x), "\n",
  "n: ", show(n), "\n"
];

对于这个特定的问题,有22320个解决方案。以下是其中一些:

x: [1, 3, 4, 6, 9, 8, 5, 2, 7, 0]
n: 1346985270
----------
x: [1, 3, 4, 7, 9, 8, 5, 2, 6, 0]
n: 1347985260
----------
x: [1, 3, 4, 6, 9, 7, 5, 2, 8, 0]
n: 1346975280
----------
x: [1, 3, 4, 8, 9, 7, 5, 2, 6, 0]
n: 1348975260
----------
...
x: [0, 7, 4, 1, 9, 3, 6, 8, 5, 2]
n: 741936852
----------
x: [0, 8, 4, 1, 9, 3, 6, 5, 7, 2]
n: 841936572
----------
x: [0, 8, 4, 1, 9, 5, 6, 3, 7, 2]
n: 841956372
----------
...
英文:

Here is the function I tend to use for connecting digits in an array (a) to a number (n) for a given (and fixed) base (base):

% n = to_num_base(a, base)
function var int: to_num_base(array[int] of var int: a, int: base) =
          let { int: len = card(index_set(a));
                var int: n = sum(i in index_set(a)) (
                   pow(base, len-i) * a[i] 
                 );
         } in n
;

% base 10
function var int: to_num(array[int] of var int: a) = to_num_base(a, 10);

Here's a simple test model (http://hakank.org/minizinc/to_num.mzn ):

include "globals.mzn"; 

int: m = 10;

var 1..pow(10,m)-1: n;
array[1..m] of var 0..9: x;

solve satisfy;

constraint
   n = to_num(x) /\
   all_different(x) /\
   x[3] = 4 /\
   n >= 50000 /\
   n mod 2 = 0
;

output [
  "x: ", show(x), "\n",
  "n: ", show(n), "\n"
];

For this specific problem, there are 22320 solutions. Here are some of them:

x: [1, 3, 4, 6, 9, 8, 5, 2, 7, 0]
n: 1346985270
----------
x: [1, 3, 4, 7, 9, 8, 5, 2, 6, 0]
n: 1347985260
----------
x: [1, 3, 4, 6, 9, 7, 5, 2, 8, 0]
n: 1346975280
----------
x: [1, 3, 4, 8, 9, 7, 5, 2, 6, 0]
n: 1348975260
----------
...
x: [0, 7, 4, 1, 9, 3, 6, 8, 5, 2]
n: 741936852
----------
x: [0, 8, 4, 1, 9, 3, 6, 5, 7, 2]
n: 841936572
----------
x: [0, 8, 4, 1, 9, 5, 6, 3, 7, 2]
n: 841956372
----------
...

huangapple
  • 本文由 发表于 2023年5月24日 21:04:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/76323870.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定