How to loop over a list "inwards"?

Question

I have a list with objects that have a weight-property. I'm trying to rearrange the objects in the list, so that the weights are distributed evenly over the 2 halves (halves being left & right. So for example, if the list is 4 items long, indexes 0 and 1 are the left half and indexes 2 and 3 are the left half).

I'm trying to jump from (list of 4 items) index 0 -> 3 -> 1 -> 2, or maybe even 0 -> 3 -> 2 -> 1, which ever distributes the weights more evenly.

I tried messing around but haven't been able to come up with something working. (It should also work for lists with an odd number of items.)

bool left = true;
List<Column> orderedColumns = _columns.OrderByDescending(x => x._totalWeight).ToList();
for (int i = 0; i < _columns.Count; i++)
{
    Column columnToPlace = orderedColumns[0];
    int index = i;
    if (!left)
    {
        index = _columns.Count - i;
    }
    
    if (left && i > 0)
    {
        index--;
    }
    _columns[index] = columnToPlace;
    orderedColumns.RemoveAt(0);
    left = !left;
}

Seems you need `subset sum algorithm` - choose subset having weight close to overallweight/2. Might be solved with dynamic programming — MBo, Apr 29 '22 at 17:20
https://stackoverflow.com/questions/4355955/subset-sum-algorithm has several suggestions that would lend themselves to C# conversion — Caius Jard, Apr 29 '22 at 17:35
What if it is more evenly distributed with an unequal number of items in the left and right halves? If you have 1,2,3,9, left:1,2,3 right:9 is more even than left:2,3 right:1,9 ? — NetMage, Apr 29 '22 at 20:36

score 0 · Answer 1 · answered Apr 29 '22 at 21:12

This splits the weights (or objects) instead of providing the indexes, but you could do that with some modifications if that is what you need.

The idea is to sort the weights, then match the lightest weights with the heaviest weights. With an odd number of weights, you add that to the lightest side.

var sortedWeights = weights.OrderBy(w => w).ToList();
var wc = weights.Length;
var halfSubCount = wc/4;

var left = sortedWeights.Take(halfSubCount).Concat(sortedWeights.TakeLast(halfSubCount)).ToList();
var right = sortedWeights.Skip(halfSubCount).Take(halfSubCount).Concat(sortedWeights.TakeLast(halfSubCount*2).Take(halfSubCount)).ToList();

if (wc % 2 == 1) {
    var middleWeight = sortedWeights[wc / 2];

    if (left.Sum() <= right.Sum())
        left.Add(middleWeight);
    else
        right.Add(middleWeight);
}

How to loop over a list "inwards"?

1 Answers1