Вот один из способов сделать это, который похож на код, который вы уже пробовали. Идея такова:
- Определите «идеальное значение», разделив сумму элементов на количество частей (
resultCount), которые мы хотим разделить на - Создать
result массив с resultCount индексами - Создайте счетчик
resultIndex, чтобы отслеживать, какой индекс в нашем массиве result мы добавим текущий item к - В
foreach l oop, пройдитесь по массиву, добавляя каждый элемент либо к текущему индексу в массиве result, либо, если это приведет к sh нам по сравнению с idealValue, сначала увеличьте наш индекс.
Например:
public static int[] Split(int[] input, int resultCount)
{
if (input == null) throw new ArgumentNullException(nameof(input));
if (resultCount > input.Length || resultCount < 1)
throw new ArgumentOutOfRangeException(nameof(resultCount));
var idealValue = input.Sum() / resultCount;
var result = new int[resultCount];
var resultIndex = 0;
foreach (var item in input)
{
// Move to the next index in our result array if the
// next sum puts us over our expected average amount
if (result[resultIndex] > 0 &&
result[resultIndex] + item > idealValue &&
resultIndex < result.Length - 1)
resultIndex++;
result[resultIndex] += item;
}
return result;
}
Проблема в том, что если все элементы больше нашего "идеального значения", то последний индекс в нашем result массив будет слишком большим, так как туда все помещается. Чтобы решить эту проблему, нам, вероятно, потребуется дважды пройтись по массиву: сначала, чтобы узнать, каково значение каждого элемента, а второй раз, чтобы заполнить результат идеальными суммами.
Рассмотрим ввод:
new [] { 1, 1, 1, 1, 1, 1, 1, 1, 10 }, 3 // Split the array into 3 parts
В приведенном выше примере sum / parts = 18, поэтому idealValue = 6, но на самом деле мы получили бы результат, который выглядел бы так: { 6, 2, 10 } вместо { 4, 4, 10 }, что распределяется более равномерно.
Один из способов решить эту проблему - удалить «выбросы» (те элементы, значение которых больше идеального), а затем пересчитать новое «идеальное» значение. Это приближает нас к идеалу:
public static int[] Split(int[] input, int resultCount)
{
if (input == null) throw new ArgumentNullException(nameof(input));
if (resultCount > input.Length || resultCount < 1)
throw new ArgumentOutOfRangeException(nameof(resultCount));
var idealValue = input.Sum() / resultCount;
var result = new int[resultCount];
var resultIndex = 0;
// Recalculate idealValue by removing items over the ideal
var itemsUnder = input.Where(item => item <= idealValue).ToList();
idealValue = itemsUnder.Sum() / (resultCount - (input.Length - itemsUnder.Count));
foreach (var item in input)
{
// Move to the next index in our result array if the
// next sum puts us over our expected average amount
if (result[resultIndex] > 0 &&
result[resultIndex] + item > idealValue &&
resultIndex < result.Length - 1)
resultIndex++;
result[resultIndex] += item;
}
return result;
}
Теперь с вводом:
new [] { 1, 1, 1, 1, 1, 1, 1, 1, 10 }, 3 // Split the array into 3 parts
Сначала мы вычисляем idealValue = 6, затем игнорируем 10 и берем отдохните и разделите на (3 - 1), чтобы получить новый idealValue = 4, и мы получим результат, который выглядит как { 4, 4, 10 }, который распределен более равномерно.
Это по-прежнему не помогает в ситуациях, когда мы получаем множество меньших чисел, которые суммируются в последнем индексе (поскольку их больше некуда поместить).
Например, если у нас есть ввод например, {80, 99, 60, 200, 50, 70, 90}, мы сначала вычислим idealValue = 216 (и поскольку ни один из элементов не больше этой суммы, она не изменится при втором пересчете). Но затем, когда мы запускаем его через нашу первую итерацию, мы получаем набор результатов: {179, 60, 410}. Обратите внимание, что все меньшие значения ближе к концу были сброшены в последнюю позицию.
Один из способов решения этой проблемы - это пересчитать idealValue снова после того, как мы сгенерируйте наш первый набор результатов. Мы хотим сделать это только в том случае, если результаты необходимо пересчитать, проверив, имеют ли элементы, которые меньше idealValue, достаточно большую разницу между ними, чтобы мы могли исправить:
public static int[] Split(int[] input, int resultCount)
{
if (input == null) throw new ArgumentNullException(nameof(input));
if (resultCount > input.Length || resultCount < 1)
throw new ArgumentOutOfRangeException(nameof(resultCount));
var idealValue = input.Sum() / resultCount;
var result = new int[resultCount];
var resultIndex = 0;
// Recalculate idealValue by removing items over the ideal
var itemsUnder = input.Where(item => item <= idealValue).ToList();
idealValue = itemsUnder.Sum() / (resultCount - (input.Length - itemsUnder.Count));
foreach (var item in input)
{
// Move to the next index in our result array if the
// next sum puts us over our expected average amount
if (result[resultIndex] > 0 &&
result[resultIndex] + item > idealValue &&
resultIndex < result.Length - 1)
resultIndex++;
result[resultIndex] += item;
}
// Try to determine if the calculated results can be averaged better
var resultsOver = result.Where(item => item > idealValue).ToList();
var resultsUnder = result.Except(resultsOver).ToList();
if (resultsUnder.Max() - resultsUnder.Min() > resultsUnder.Count)
{
// Recalculate idealValue again based on the final results
// by getting the sum of the difference of the items that are over
// and dividing it by the total number of items
idealValue += resultsOver.Select(item => item - idealValue).Sum() / result.Length;
// Reset our results
result = new int[resultCount];
resultIndex = 0;
foreach (var item in input)
{
// Move to the next index in our result array if the
// next sum puts us over our expected average amount
if (result[resultIndex] > 0 &&
result[resultIndex] + item > idealValue &&
resultIndex < result.Length - 1)
resultIndex++;
result[resultIndex] += item;
}
}
return result;
}
Итак, теперь, когда мы используем ввод {80, 99, 60, 200, 50, 70, 90}, после вычисления первого набора результатов ({179, 60, 410}) мы повторно вычисляем idealValue, беря сумму, на которую закончились элементы, получая среднее значение и добавляя его к нашему idealValue, например: 410 - 216 = 194, 194 / 3 = 64, idealValue = 216 + 64 = 280. Затем мы сбрасываем результаты и снова запускаем его, получая в итоге:
{239, 250, 160}