Divide an array into two arrays

SystemVerilog
1

I want to divide an array containing some elements into 2 arrays such that such of the elements of both arrays are equal.

For ex: arr = {2,3,4,5};
This can be split into arr1 = {2,5}; arr2 = {3,4};

[Edit]
There can be situations where the sums won’t match in a set of numbers.
Ex: '{1,2,4}. In such case numbers should be split such a way that difference between sums of both arrays are minimal. ( {1,2} and {4} )

2

This can be easily done with a for-loop. You need to give us a more precise definition of deciding which elements go into each array. And what happens when there are an odd number of elements?

3

Hi Dave,

I cracked this problem.

One way we can do is by writing constraints for the requirement and let System Verilog take care of the rest.

constraints

  1. sum constraint to ensure sum of 2 arrays are same
  2. unique constraint to ensure that the arrays don’t share any common elements.
  3. inside constraint for mentioning arrays do pick up values from the first array.

I think these constraints are sufficient for the problem statement.
By this method we can solve the case of odd number of elements. But we can’t guarantee we end up with equal number of elements. Thats fine.

Is there a better approach to this?

FYI, there’s no specific rule on which “integer value” goes into which array. It just has to satisfy the sum problem.

4

Definitely a whole lot more information but still not enough. Can can the first array have duplicate values? Is it constraint to having values that can be divided into equal sums? Are you expecting the first array to be random as well?

5

If we are randomizing the initial array to be random, then we will miss some interesting scenarios where the initial array itself can’t be divided equally. I will explain one situation down.
And there’s no duplicate elements in the first array.

For time being these are the constraints I used.

typedef int array [];
  int init_array [5] = '{1,2,3,4,10};

  rand array arr1, arr2;

  constraint SIZE {arr1.size() + arr2.size() == $size(init_array);}
  constraint SUM { arr1.sum() == arr2.sum(); }
  constraint UNIQ { unique {arr1,arr2};}
  constraint IN { foreach(arr1[i]) { arr1[i] inside {init_array};} foreach(arr2[i]) {arr2[i] inside {init_array};}}

This will give result arr1 = {1,2,3,4} and arr2 ={10}

https://edaplayground.com/x/g3JM

But let’s think about an array situation {1,2,4}. Here there no possible combination that we can split array equally and constraints fail. One way to deal with it is distribute evenly, like {1,2} and {4}. How can we modify the constraint for this?

6

Again, what do you mean by “distribute evenly”?

Is this topic just a hypothetical exercise, or do you have a real application behind this? Knowing that real application might help with addressing this as there are a few ways you could accomplish this.

7

Yes. This is a hypothetical situation to check the possibility of constraints to solve such issues.

This is a special case of this problem. The problem statement is to distribute elements in such a way that sum of both new arrays are same. But this can’t be possible all the time.
Example: Initial array {1,2,3,7}. We can’t split the elements in equal sets. But it’s possible to split the elements in such a way that the sums of the new arrays are close. Like {1,2,3} (sum = 6) and {7} (sum =7). Another example {1,2,3,4,5} → {1,2,4} and {3,5}. How can we get such distribution when we can’t split the elements into array of equal sum.