1с разделить массив на равные части

Обновлено: 07.07.2024

Мне необходимо разбить массив на несколько с сохранением всех данных. К примеру в массиве ArrayList содержится 1103 значения, как можно его разбить на 10 массивов с сохранением всех значений?

В PHP для этого используется функция array_chunk.

Как с этим обстоят дела в шарпе?

5,382 3 3 золотых знака 44 44 серебряных знака 86 86 бронзовых знаков 3,445 3 3 золотых знака 28 28 серебряных знаков 56 56 бронзовых знаков Почему же ArrayList , 21-й век на дворе, используйте List<T> же. @Jofsey, странный сайт лимитирует комментарии. Для того, чтобы сделать полностью ленивый алгоритм, работающий за один проход, придется руками реализовать ДКА аналогичный тому, что компилятор генерирует для вызовов yield. Не самое интересное занятие, но можете попробовать сделать и выложить результат сюда. @VladD, если при изменение понадобится абстракция, я ее введу. Про инваринаты вам сначала надо указать на что вы их накладываете и в чем они состоят. Для этого вам придется многое в этой задаче додумать. Я гаданием предпочитаю не заниматься. Достаточно, что конкретно ToChunks корректен. @STDray: (1) неужели инвариант не очевиден? последовательность элементов кусков совпадает с исходной последовательностью хотя бы в случае, если она неизменна. (2) в production-коде у вас не выйдет так просто менять сигнатуры методов, если, конечно, над проектом работает больше 1 человека. кроме того, не отлавливаемое компилятором изменение мутабельных списков — источник wtf ("мне передали List<T> в подпрограмму, какого я не должен менять его?") и багов. (не думать — не всегда наилучшая стратегия, потом может быть слишком поздно.) Если кто решит менять куски, значит такого инварианта на соответствие исходной коллекции нет. При том неважно, будет ли мутирован список или порождена новая коллекция. Конечно у меня выйдет менять сигнатуры, иначе зачем нам типизированные языки. Если человеку передали список, он волен его менять. Все правильно.

Ну, по всякому можно.

Если нужны везде "материализованные" массивы, добавьте .ToList() :


202k 25 25 золотых знаков 273 273 серебряных знака 501 501 бронзовый знак @STDray: (сорри, лимит комментариев) Это всё понятно, я собственно о другом. Сам по себе паттерн "обрабатываем куски коллекций последовательно" нужен достаточно редко, если вообще нужен (мне не был нужен ни разу), агрегировать можно точно так же по одному элементу. (Зачем разделение на куски ТС, он не уточнял.) Поэтому дополнительное усиление семантики кажется мне немотивированным. --- Говоря о структурах данных, если уж возвращать материализованные данные, то IEnumerable<IReadOnlyCollection<T>> по понятным причинам. @VladD, если у вас есть какие-то критерии нужности, лучше их указать сразу. И понятные причины тоже надо указать, поскольку я уже написал, что важно знать с какой именно коллекцией имеем дело. Если кратко, я руководствуюсь принципом: минимальные требования на входе, максимальные - на выходе.

В дополнение к предыдущему ответу.

Ленивые вычисления, конечно, хорошо, но не стоит забывать про эффективность и повторное использование. Имеет смысл реализовать функцию, которая разобьет коллекцию на куски заданного размера за один проход.

Если требуется именно разбить коллекцию на N кусков, то стоит удостовериться, что сложность получения количества элементов в исходной коллекции будет O(1). Потом вычислить размер куска и вызвать функцию, описанную выше.

Описать как методы расширения и использовать для соответствующих коллекций. (Пример)

ЗЫ: От использования ArrayList и других нетипизированных коллекций лучше отказаться.

ЗЗЫ: По мотивам возникшего флуда. Реализация, позволяющего выбрать тип чанков

В любом случае, есть выражение "преждевременная оптимизация - корень всех бед", тоже самое касается и абстракций в ООП.

Как разделить массив на две равные части, суммы элементов которых наиболее близки к равенству.

Как разделить массив по на две части, я знаю. Но не могу придумать, как сделать? чтобы суммы элементов этих двух частей были равны. Прошу подсказать алгоритм.

Для тех, кто просил уточнить условие: массив делится на две равные части, количество элементов первой части = количеству элементов второй. Также сумма элементов первой части равна или наиболее близка к равенству второй части.


49.5k 72 72 золотых знака 250 250 серебряных знаков 480 480 бронзовых знаков 1,079 8 8 золотых знаков 24 24 серебряных знака 59 59 бронзовых знаков А что делать, если у вас не могут быть равны части, как не дели? Можно перемещать элементы? входящий массив должен быть четным. Перемещать можно Вам нужен сам алгоритм или как это сделать на определенном языке?
  • Вы переформулировали так называемую Partition Problem . Это известная Weakly NP-Complete задача, для которой существует псевдополиномиальный алгоритм и примерный полиномиальный алгоритм.


  • Если вас устроит примерное решение, то используйте O(N log N) жадный алгоритм

(Для тех, кто сидит в комментариях :)

  • Условие деления массива на части одинаковой длины не влияет на NP -полноту задачи (она все еще NPC ). Доказательство этого факта с точки зрения теории алгоритмов может звучать примерно так:

  • Сведем общую задачу Partition Problem (PP) к задаче с двумя равными частями Equally Sized Partition Problem (ESPP) , то есть покажем, что ESPP включает в качестве частного случая задачу PP .

  • Рассмотрим последовательность элементов длиной 2k , из которых k являются нулями. Теперь, решив эту задачу с помощью алгоритма ESPP , мы получим две последовательности длины k , разница сумм которых минимальна. Поскольку нулевые элементы не меняют суммы, то мы можем "перегнать" их из одной последовательности в другую, соответственно, сводя задачу к PP .

  • Раз мы доказали, что задача NPC , то полиномиального алгоритма решения этой задачи не существует. Можете воспользоваться псевдополиномиальным алгоритмом из википедии, адаптировав его для себя или любым жадным алгоритмом из тех, что предложен ниже.
23.3k 1 1 золотой знак 35 35 серебряных знаков 55 55 бронзовых знаков Но ведь просят, чтобы A и B были равного размера. Этот алгоритм так не работает. авп, не просят, я тоже считал вариант с равными половинками.. да и кстати, если разница не делится на 2, но массив не поделится на равные части.. @avp, я думаю, что ТС, говоря о равности, имел в виду не равные по размеру массивы, а всё же равные по сумме значений. Но тут бы неплохо, чтоб сам автор уточнил. @Deonis почему-то я подумал тоже о равности и в размере массивов. В заголовке вопроса написано две равные части, суммы элементов которых наиболее близки к равности

В продолжение к моим коментариям

В заголовке темы, вы указываете, что если не абсолютно равны, то максимально приближены к равенству. Тогда, на PHP я сделал следующим образом:

  1. Посчитал сумму значений массива и разделил её на два
  2. Отсортировал массив по убыванию значений
  3. Перебираем отсортированный масси

сумма_массива1 = 0;

сумма_массива2 = 0;

если (суммамассива1 <= суммамассива2 || суммамассива2 >= полобщей_суммы)

> вдругомслучае

>

Конечно далеко не уверен, что работает корректно, но несколько раз протестил и вроде бы как все нормально сделало.

33.5k 1 1 золотой знак 28 28 серебряных знаков 47 47 бронзовых знаков Что-то я тоже сомневаюсь) По-моему это задаче о рюкзаке, где стоимость каждого элемента 1, вес - элемент. А вместимость половина суммы массива. Как только находим решение стоимостью n/2 (где n - количество элементов в массиве) останавливаемся и восстанавливаем массив. Хотя может мне просто поспать надо (тоже не уверен) :) Ну, если плюсуют вариант, который предложил @Котик_хочет_кушать, то всё-таки алгоритм выбран правильный, т.к. практически идентичный Тоже (как и у @Котик) не то. Алгоритм не обеспечивает равного размера частей. В этом-то (одно из условий вопроса) и загвоздка.

Как вариант можно предложить генетический алгоритм.

FitnessFunction понятно сумма (чем ближе к половине суммы всех элементов массива, тем круче)

Хромосома состоит из n/2 ген (ген - элемент массива).

Поиграться количеством популяции, посмотреть сколько примерно будет нужно для более менее адекватного результата. Ну и подумать как скрещивать (можно наверно сортировать гены в родителях и циклически скрещивать)

Опять же результат будет примерным (для улучшения можно несколько раз прогнать алгоритм и выбрать лучший результат)

@rasmisha - Извините, что стер свой прошлый коммент под моим ответом, просто размышлял над доказательством того, что это - NPC задача. - Не уверен, кстати, что ff, у которой метрика хорошести пропорциональна отклонению от полусуммы - это хороший выбор. Хотя не очень силен в генетических алгоритмах. @Котик на счет ff вполне может быть. Просто решил поделиться вариантом, который пришел в голову и показался одним из способов найти приближенный ответ. @Котик кстати, первая идея (не знаю насколько она правильна) как раз совпадает с вашей (по-крайней мере судя по ссылкам приведенным Вами), но не уверен опять же, что правильно распределил вес/стоимость/вместимость.

Суть такая. Сортируем изначальный массив. Заполняем оба выходных массива одновременно по одному числу в каждый. В массив с меньшей суммой добавляем бОльшее число, в массив в с бОльшей суммой добавляем элемент, при добавлении которого бОльший массив так и останется с бОльшей суммой (начинаем проверять с наименьшего элемента, если так и остался с большей, значит добавляется первый элемент и т.д.).

UPD Проблема жадности проявляется на этапе когда выбираются максимальные элементы. Когда выбирается максимальный и один из минимальных элементов, жадность не влияет на выбор. Соответственно эту неопределенность предлагаю ветвить. Находим все множества решений исходя и того, что максимальные элементы могут принадлежать как первому-второму массиву, так и второму-первому. А затем выбираем наиболее подходящее с точки зрения минимальности разности сумм. В худшем случае будет брутфорс, жаль.

Как можно разделить массив на три части так, чтобы сумма чисел в каждом массиве не превышала сумму в остальных (В тех случаях, когда это возможно), при этом размеры массивов могут быть неодинаковыми.


183k 13 13 золотых знаков 103 103 серебряных знака 208 208 бронзовых знаков


да, но это будет достаточно долго. Есть какие нибудь другие варианты?

Никаких граничных условий нет, значит и так сойдёт, зачем ещё то заморачиваться?

@KGYT, это просто будет невозможно. Как будет выполняться (x < y && x < z) && (y < z && y < x) && ( z < y && z < x)

Сумма всех элементов, деленная на 2 - s. Подгонять три части, начиная с самых больших элементов, так, чтобы сумма каждой части была меньше s. Сначала самые большие - пока можно - в одну. Потом остальные - в другую часть. Потом в третью. Оставшуюся мелочь распихивать по всем трем, как получится. Понятно, что не более чем эвристика.

Сумма всех элементов, деленная на 2 - s . Подгонять три части, начиная с самых больших элементов, так, чтобы сумма каждой части была меньше s . Сначала самые большие - пока можно - в одну. Потом остальные - в другую часть. Потом в третью. Оставшуюся мелочь распихивать по всем трем, как получится. Понятно, что не более чем эвристика. Но, похоже, работает - попробуйте этот код:


183k 13 13 золотых знаков 103 103 серебряных знака 208 208 бронзовых знаков

Можно было тупо распихивать самые большие элементы в самый незаполненный массив с темже результатом, а не заморачиваться так. Ну и такая проверка не заденет граничных случаев с вероятностью более 99.9999%, да ещё и отрицательных чисел напихает.

Заморачиваться? А вы напишите свой ответ, а мы посмотрим. Еще одна неуместная критика для самоутверждения.

Разделение массива и сортировка каждой части методом пузырька
Помогите решить пример: Имеется массив целых чисел большого размера. Требуется разделить этот.

Разделение массива на две равные части
Заполняю массив размером 20 рандомными числами от 0 до 200. Надо разделить этот массив на две.

Разделение текста на равные части
Как сделать программу, которая будет разделать текст на равные части? Например у нас текстовый.


Разделение текста в TextBox на равные части
Нужна программа которая разделяет текст в textbox на равные части.И каждая часть заменяется другим.

Нужно решение в общем виде, т.к. массив может быть другим, а также размер каждой части может быть другим. Байт, это был самый тривиальный ответ.
И все-таки с теми данными, которые я написал, есть какие-нибудь мысли?

Решение

Необходимо разбить его на три массива каждый длиной 3, не используя циклы.
В итоге должен получиться двумерный массив:
C++

Деление массива на равные части (JS)
Как можно в JS поделить массив на равные интервалы? Например, на 4 равных интервала. for.

Деление массива на равные части
Здравствуйте! Есть задание: &quot;написать функцию, которая проверяет возможно ли поделить массива на.

Разбить массив на две равные части (или приблизительно равные)
Задали задание. Нужно разбить одномерный массив на две почти равные части(если на равные не.


Разделение элементов массива в разные части экрана
Извиняюсь, что пишу уже вторую задачу за сегодня, но с этой задачкой я сижу уже битый час и не могу.

Задача про деление массива на три равные по сумме части,не включая точки деления
Добрый день!Выкладываю описание задания на английском языке.В принципе алгоритм для меня ясен,но он.

Разделение на части
Привет. Как можно реализовать разделение текста на части. Пример: < Часть1 < .

Читайте также: