Update: Gah, I didn't notice that you seem to only have 4 elements in the list. The answer here is for the general case, and will be overkill for a 4-element problem. Go with looping.
Well, personally I would use a Heap data structure, where each element is the value of each element + its position in the original list.
You need to hunt down a good Heap implementation for C# though. You can use mine, but it is part of a larger class library so it might be a bit of a rubber ball to pull into your project. The code is here: My Mercurial Repository.
I'll be showing examples below on how my implementation would work.
If you don't know how a heap works, it is basically a data structure that looks a bit like an array, but also a bit like a tree, where the nodes of the tree is stored in the array. There's a bit of code involved that "intelligently" moves items around. The beauty of it is that it is super easy to get the highest or lowest item (that is, one of them, not both from the same heap), since it will always be the first element in the array.
So what I would do is this:
- Create a heap containing value+position for all elements, sorted so that the highest value is the first one
- Create a heap containing value+position for all elements, sorted so that the lowest value is the first one
Then, if the sum < 0, grab the first element of the heap (value + position), increase the value in the original list by 1, then replace the first element of the heap with (value+1),position. Replacing the first element of the heap has the effect of removing it, and then readding it, potentially moving it to a different position than the first one if it is no longer the highest/lowest value. For instance, let's say you have the following list:
list: 1, 2, 3
The heap now looks like this:
heap: (1, 0), (2, 1), (3, 2) <-- second value is position, 0-based
ie. you build it up like this:
position: 0, 1, 2
list: 1, 2, 3
| | +-------+
| | |
+-+ +--+ |
| | |
<-+> <-+> <-+>
heap: (1, 0), (2, 1), (3, 2)
Now, if the sum is too low, you grab the first element of the lo-heap, which is (1, 0), increase the value at position 0 in the original list by 1, then replace the first element of the heap (which is still (1, 0)) with a new element containing the new value, at the same position.
After the replace, the list and heap now looks like this:
list: 2, 2, 3
heap: (2, 0), (2, 1), (3, 1)
Let's say the sum is still to low, so you repeat. Now, when re-adding (3, 0) instead of (2, 0), it will be pushed a bit back into the heap, so it looks like this:
list: 3, 2, 3
heap: (2, 1), (3, 0), (3, 1)
Now, the 2-value is now the lowest one, and thus the first element of the heap. Note that these operations does not reorder the entire heap, only the portions necessary. As such, a heap is ideal for algorithms like this since they are cheap to keep sorted when doing modifications.
So let's see some code. I'm assuming you have an array of values like this:
int[] values = new int[] { ... };
Thus, with my heap implementation, the following would do what you want:
using System;
using System.Collections.Generic;
using System.Linq;
using LVK.DataStructures.Collections;
namespace SO3045604
{
class LowestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return x.Item1.CompareTo(y.Item1);
}
}
class HighestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return -x.Item1.CompareTo(y.Item1);
}
}
class Program
{
static void Main(string[] args)
{
int[] values = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var valuesWithPositions = values
.Select((value, index) => Tuple.Create(value, index));
var loHeap = new Heap<Tuple<int, int>>(
new LowestComparer(),
valuesWithPositions);
var hiHeap = new Heap<Tuple<int, int>>(
new HighestComparer(),
valuesWithPositions);
int sum = values.Aggregate((a, b) => a + b);
while (sum < 75)
{
var lowest = loHeap[0];
values[lowest.Item2]++;
loHeap.ReplaceAt(0,
Tuple.Create(lowest.Item1 + 1, lowest.Item2));
sum++;
}
while (sum > 55)
{
var highest = hiHeap[0];
values[highest.Item2]--;
hiHeap.ReplaceAt(0,
Tuple.Create(highest.Item1 - 1, highest.Item2));
sum--;
}
// at this point, the sum of the values in the array is now 55
// and the items have been modified as per your algorithm
}
}
}