CODEWITHSUNDEEP
arraysmatlabcompare
NLed
NLed

Reputation: 1865

Increment values in an array with constraints using Matlab?

Scenario :
If I have an array with 4 loads (a1 a2 a3 a4) 

a=[a1 a2 a3 a4] (locations of these loads must be fixed)
a=[1 2 3 3]

I would like to try and increase all values in the array to 3.
Note : the array a is not fixed, and can have any value from 0:3

Constraints :

  1. There is a priority array that cannot be violated
  2. Number of total increments is limited to 3

Given :

Priority array v=[1 3 2 1] -- (1 is highest priority, and 3 is lowest priority).
Note : the array v is not fixed, and can have any value from 0:3

Using this priority array : 

a(1,1)=highest priority  
a(1,4)=2nd highest priority  
a(1,3)=3rd priority  
a(1,2)=lowest priority

Implementation, my trial in pseudo code :

a=[1 2 3 3]
v=[1 3 2 1]
count=3

Check highest priority : a(1,1)
increment by 1
decrement count by 1
count = 2
still less than 3 ? if yes, then increment again until a(1,1)<= 3 AND count >=0
Change highest priority to 5 (so that min(v) will not pick it up)

ans : a=[3 2 3 3] ; v=[5 2 3 3] ; count = 1

Check highest priority : a(1,3)
value >= 3
Change highest priority to 5 (so that min(v) will not pick it up)
skip

ans : a=[3 2 3 3] ; v=[5 2 5 3] ; count = 1

Check highest priority : a(1,4)
value >=3 
Change highest priority to 5 (so that min(v) will not pick it up)
skip

ans : a=[3 2 3 3] ; v=[5 2 5 5] ; count = 1

Check highest priority : a(1,2)
increment by 1
decrement count by 1
count = 0
still less than 3 ? if yes, then increment again until a(1,1)<= 3 AND count >=0 
Change highest priority to 5 (so that min(v) will not pick it up)

ans = [a1 a2 a3 a4] = [3 3 3 3]

Note : if a priority value = [1 1 1 1] is reached, then a is prioritised from left to right (I haven't found a better way to do this)

I hope this makes sense, and that my pseudo code shows what I'm trying to implement. Ask me if something is not clear.

Upvotes: 1

Views: 1422

Answers (3)

erikced
erikced

Reputation: 732

Another version:

a = [1 2 3 3];
v = [1 3 2 1];
count = 3;
target = 3;

Sort a and v in priority order

[vSorted, order] = sort(v);
aSorted = a(order);

Find position that will cause count to equal 0

pos = find(cumsum(target - aSorted) >= count);

Update all values up until but not including pos, decrement count accordingly

count = count - sum(3 - aSorted(1:pos - 1));
vSorted(1:pos - 1) = 5;
aSorted(1:pos - 1) = target;

Update the value s at pos

aSorted(pos) = aSorted(pos) + count;
count = 0;
if aSorted(pos) == target
    vSorted(pos) = 5;
end

Restore sort order

 [~, invOrder] = sort(order);
 a = aSorted(invOrder);
 v = vSorted(invOrder);

If v is only used to determine the priority there is no need to update it. If count may still be non-zero after all values of a have reached target some extra handling of that case is required as that will cause pos = find(...); to return an empty array.

Upvotes: 1

JustinBlaber
JustinBlaber

Reputation: 4650

Here's what I came up with:

a = [1 2 3 3];
v = [1 3 2 1];

% Get priority vector - this converts v into the indices of a that are most important in descending order. This can also be preallocated for speed or stored in place if v is not important;
priority_vec = [];
for i = 0:3
   % Get indices
   priority_vec = horzcat(priority_vec,find(v == i));   
end

% Loop over priority_vec
count = 3; % count is the number of additions you can make
for i = 1:4 % Loop over the indices of priority vec
    priority_ind = priority_vec(i); % This is the current index of most importance
    while(a(priority_ind) < 3 && count ~= 0) % Continue to add one while count is greater than 0 and the value at the priority index is less than three             
        a(priority_ind) = a(priority_ind) + 1;
        count = count - 1;
    end    
end

Upvotes: 1

wakjah
wakjah

Reputation: 4551

You could do something like this

a = [1 2 3 3]; 
v = [1 3 2 1];

% Sort a in the order of priority v
[vSrt, indSrt] = sort(v);
a = a(indSrt);

nIncsRemaining = 3; % Total no. of increments allowed
target = 3; % Target value for each value in a

for curInd = 1:length(a)
    % Difference from target
    aDiff = target - a(curInd);
    % Do we need to increment this value of a?
    if aDiff > 0
        % Increment by a maximum of nIncsRemaining
        aDelta = min(aDiff, nIncsRemaining); 
        % Increment a and decrement no. of increments remaining by the
        % same amount
        a(curInd) = a(curInd) + aDelta; 
        nIncsRemaining = nIncsRemaining - aDelta; 
    end

    % Have we done as much as we're allowed?
    if nIncsRemaining == 0, break; end
end

The key step is the sorting of the priority array, and the sorting of a by the same indices. Then you can just loop through a, being confident that you're beginning with the highest priority.

If you require the same order as the input at output, then you can invert the sorting operation by doing

[~, indReSrt] = sort(indSrt);
a = a(indReSrt);

The array v was not modified in the first place, so you don't need to invert the sort on that array.

Upvotes: 1

Related Questions