1

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.

Improve this question

3 Answers 3

Reset to default
1

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.

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

9 Comments

But do the arrays stay the same position after ? I'll update question to clarify what I mean. As in the answer must be [a1 a2 a3 a4], they cannot be shuffled.
Oh and can you please explain the code, would like to learn what's happening.
Answer edited to include explaining comments and requested order; does it make sense now?
Are you sure this is right? if you change nIncsRemaining to 2 the output is [3 3 3 2]. If I understood your question correctly you want the 2nd index of a to have the lowest priority, so the output should be [3 2 3 3].
@wakjah can you check this out ? Changing the value of nIncsremaining will not give out the right solution
|
1

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
Improve this answer

2 Comments

Can you please provide more info about your code ? Would like to learn what's going on in that loop
@NLed Added in some comments.
1

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.