Search the minimum number of swaps to order an array in minizinc

Question

I'm following a course in constraint programming and the professor assigned me this job: Let us consider a n element vector of numbers v = [v_1, ... , v_n], where v_i ∈ N. For i, j ∈ {1, ... , n} a swap(i, j) move has the effect of swapping the values v[i] and v[j]. The problem is that of finding the plan of minimum length that sorts the vector.

int: n = 5;

array[1..n] of int: A = [2, 3, 4, 5, 1];

array[1..n, 1..n] of var int: A_prime;
array[1..n, 1..2] of var 1..n: swaps;
array[1..n, 1..n, 1..n] of var 0..1: lt;
array[1..n] of var int: sums;

var int: steps;

predicate swap(array[1..n, 1..n] of var int: A_prime, var int: i, var int: j, int: k) = 
  let {var int: temp = A_prime[k-1, i]}
  in A_prime[k, i] = A_prime[k-1, j]
  /\ A_prime[k, j] = temp
;


constraint steps > 0 /\ steps <= n;

constraint forall(i in 1..n)
(
  A_prime[1, i] = A[i]
);

constraint forall(i, j in 1..n where i < j)
(
  if A[i] <= A[j] then
    lt[1, i, j] = 1
  else
    lt[1, i, j] = 0
  endif
);

constraint forall(i in 1..n)
(
  forall(j, k in 1..n where j >= k)
  (
    lt[i, j, k] = 0
  )  
);

constraint forall(i in 1..steps)
(
  swaps[i, 1] < swaps[i, 2]
);

constraint forall(i, j in 1..steps where i < j)
(
  (swaps[i, 1] != swaps[j, 1] /\ swaps[i, 2] == swaps[j, 2]) \/
  (swaps[i, 1] == swaps[j, 1] /\ swaps[i, 2] != swaps[j, 2]) \/
  (swaps[i, 1] != swaps[j, 1] /\ swaps[i, 2] != swaps[j, 2])
);

constraint forall(i in 2..steps)
(
  swap(A_prime, swaps[i-1, 1], swaps[i-1, 2], i)
);

constraint forall(i in 2..steps)
(
  forall(j in 1..n where j != swaps[i-1, 1] /\ j != swaps[i-1, 2])
  (
    A_prime[i, j] = A_prime[i-1, j]
  )
);

constraint forall(i in 2..steps)
(
  forall(j, k in 1..n where j < k)
  (
    if A_prime[i, j] <= A_prime[i, k] then
      lt[i, j, k] = 1
    else
      lt[i, j, k] = 0
    endif
  )
);

constraint forall(i in 1..steps-1)
(
  lt[i, swaps[i, 1], swaps[i, 2]] == 0
);

constraint forall(i in 1..steps)
(
  sums[i] = sum(j, k in 1..n where j < k)(lt[i, j, k])
);

constraint forall(i, j in 1..steps where i < j)
(
  sums[i] < sums[j]
);

constraint sums[steps] == ceil((n*(n-1))/2);

constraint forall(i in steps+1..n, j in 1..n)
(
  A_prime[i, j] = 1
);

constraint forall(i in steps+1..n)
(
  sums[i] = 0
);

constraint forall(i in steps+1..n)
(
  swaps[i, 1] = 1 /\ swaps[i, 2] = 1 
);

solve minimize steps;

Here's the solution I came up with. Let me break it down: Firstly, I generate all possible swaps for an n-element vector, then filter only those that arrange v[i] and v[j]. After each swap, I store the resulting array in the A_prime matrix, in the row corresponding to the step in which the swap is made. To determine the only useful swaps, I compute the lt matrix, an upper triangular 3D matrix, where lt[i, j] equals 0 if A_prime[k, i] is less than or equal to A_prime[k, j], and 1 otherwise. I consider the array ordered if the sum of elements in the final lt matrix equals (n*(n-1))/2.

The problem is that this solution is slow; it struggles even with arrays of just 5 elements. I attempted to assign default values to unused variables, like the lower triangular part of the lt matrices, to reduce the number of solutions, but it doesn't seem effective.

Do you have any hint to make this code perform faster? Thanks in advance!

Axel Kemper · Accepted Answer · 2024-04-20 10:32:04Z

1

I cannot tell what exactly is going on in your model. But the following alternative solution might inspire you.

As you've noticed, the run-time explodes for growing values of n.
Google OR Tools 9.2 as back-end solver finds a first solution for n=10 in a couple of seconds. But it takes much longer to confirm this as minimum.

%  array elements can be arbitrary integers
%  not necessarily distinct
array[int] of int: A = [2, 3, 4, 5, 1];

%  the following avoids separate adjustment of 'n'
%  for changing contents of 'A'
int: n = max(index_set(A));

set of int: elements = 1..n;
set of int: steps = 1..n;

%  evaluate set of occurring numbers
%  to delimit the choices for the solver
set of int: Domain = array2set(A);

%  array of 1..n permutations
array[steps, elements] of var Domain: AP;

%  number of steps to minimize
%  may be zero if A is sorted beforehand
var 0..n: Steps;

%  first permutation is the original array A
%  copy A to avoid case distinctions
constraint forall(e in elements) ( AP[1, e] == A[e] );
 
%  adjacent permutations have a pairwise distance of one swap
%  for each step, a pair of indices must exist which describes the swap
constraint forall(s in steps where (s > 1))
( exists([
     %  count matching elements; all positions have to match
     n == (
            %  count swapped positions separately
            (AP[s - 1, i] == AP[s, j]) + 
            (AP[s - 1, j] == AP[s, i]) +
            %  add the non-swapped positions
            sum([AP[s - 1, e] == AP[s, e] 
                 | e in elements where (e != i) /\ (e != j)])
          )
     | i, j in elements where j > i
   ])
);

%  after Steps, the resulting permutation must be sorted
constraint forall([ AP[1 + Steps, e] >= AP[1 + Steps, e - 1] 
                   | e in elements where e > 1 ] );

solve minimize Steps;

Resulting output:

AP = 
[| 2, 3, 4, 5, 1
 | 5, 3, 4, 2, 1
 | 5, 4, 3, 2, 1
 | 5, 2, 3, 4, 1
 | 1, 2, 3, 4, 5
 |];
Steps = 4;
_objective = 4;

edited Apr 20, 2024 at 10:32

answered Apr 19, 2024 at 12:46

Axel Kemper

11.5k2 gold badges35 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Alberto Sambrotta Over a year ago

I'll try to explain better what's going on in my code. I'm treating the problem as a planning problem. My decisional variable is steps (the number of swaps performed), which has to be minimized. In the code i generate, in the swaps matrix, steps distinct swaps which I can do in an n-element vector. Then I perform those swaps. Each new vector after a swap is performed is saved in the A_prime matrix. I also use a sums vectors, which tells me how many element are ordered in each row of the A_prime matrix.

Axel Kemper Over a year ago

Yes. That is the same for my model. Notice that I am using fewer decision variables and restricted value domains. This should help to shorten the run-time. Eample: you could restrict steps to 0..n without using a constraint, just by defining the proper type.

Alberto Sambrotta Over a year ago

To compute that, at each step k, I compare each pair of elements in the vector i, j with i < j and I store in the lt 3D matrix (in position lt[k, i, j]) 1 if A_prime[k, i] <= A_prime[k, j], 0 otherwise. So at each step I have an upper triangular matrix (because of i < j), so I have to make (n*(n-1))/2 comparisons. Because of the said condition I expect at the step "steps" sums[steps] = (n*(n-1))/2, which means that each element is ordered. Since I do not use the lower triangular matrices of lt i set them to be equal to zero.

Alberto Sambrotta Over a year ago

Also for each step greater than "steps" I set the swaps and A_prime matrices and the sums vector to a default value. I hope that it is more clear explained like that.

Alberto Sambrotta Over a year ago

That's also what I thought, like I can eliminate the lt 3D matrix by creating a constraint that say that the elements chosen to be swapped must be unordered. In this way I don't need lt anymore. I tried this approach but it was even slower.

|

Collectives™ on Stack Overflow

Search the minimum number of swaps to order an array in minizinc

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related