sorting - Minizinc アレイソーティング

Question

このような配列宣言があるとしましょう

array[1..5] of int: temp = [1,0,5,0,3];

temp と同じように見えるが 0 がない新しい配列を開始する方法はありますか? 結果は次のようになります

[1,5,3]

または、配列の先頭または末尾に 0 が来るように配列を並べ替えます。

[0,0,1,5,3]

また

[1,5,3,0,0]

ありがとう

Answer 1

を使用MiniZinc 2すると、次のように実行できます。

array[1..5] of int: temp = [1,0,5,0,3];
%  calculate upper bound of temp index
int: i_max = max(index_set(temp));
%  use array comprehension to count non-zero elements
int: temp_non_zero = sum([1 | i in 1..i_max where temp[i] != 0]);
%  copy non-zero elements to new array
array[1..temp_non_zero] of int: temp2 = [temp[i] | i in 1..i_max where temp[i] != 0];
%  calculate upper bound for temp2 index
int: i2_max = max(index_set(temp2));

solve satisfy;

%  show our variables
output 
["\ni_max=" ++ show(i_max)] 
++ ["\ni2_max=" ++ show(i2_max)] 
++ ["\n" ++ show(temp2[i]) | i in 1..i2_max] 
;

Answer 2

別の方法:

2 つの配列間の 1:1 マッピングは、一意のインデックス値 (= 配列位置) の配列として確立されます。次に、これらのインデックスがソートされます。要素がゼロを指している場合、比較では要素の重みが高くなります。したがって、非ゼロ要素の順序を変更せずに、ゼロ値を後方にシフトします。

int: n = 5;
int: INF = 99999;    %  infinity
array[1..n] of var 0..5: s;
array[1..n] of var 1..n: map;
array[1..n] of var 0..5: s2;

solve satisfy;

%  set s[]
constraint
   s = [1,0,5,0,3]
;
%  1:1 mapping between s[] and s2[]
constraint 
  forall (i in 1..n) (
    exists(j in 1..n) (
      map[j] = i
    )
  )
;
constraint
   forall(i in 1..n) (
      s2[i] = s[map[i]]
   )
;
%  sort the map and move zero values to the back
constraint
   forall(i in 1..n-1) (
     (if s2[i] != 0 then map[i] else INF endif) <= 
     (if s2[i+1] != 0 then map[i+1] else INF endif)
   )
;

output 
[ 
  "s: \(s)\n",
  "map: \(map)\n",
  "s2: \(s2)\n",
]
;    

出力：

s: [1, 0, 5, 0, 3]
map: [1, 3, 5, 4, 2]
s2: [1, 5, 3, 0, 0]