Алгоритм распределения элементов по массивам

1. zannv 85 14.04.21 23:16 Сейчас в теме +3.35 $m
Нужен алгоритм распределения произвольного количества элементов по массивам.

Например, есть 3 элемента: 0, 1, 2.
Нужно найти все варианты распределения по массивам

Варианты могут быть следующие:

Вариант 1:
Массив 1(0 ,1, 2)

Вариант 2:
Массив 1(0, 1)
Массив 2(2)

Вариант 3:
Массив 1(0, 2)
Массив 2(1)

Вариант 4:
Массив 1(1, 2)
Массив 2(0)

Вариант 5:
Массив 1(0)
Массив 2(1)
Массив 3(2).

Количество элементов может быть любым. Необходимо найти все варианты, но порядок как внутри массива, так и порядок массивов не важен. То есть вариант, в котором есть Массив 1(0) и Массив 2(2, 1), будет являться дублем варианта 4.

На выходе ожидается:

один МассивРезультат, каждый элемент которого это МассивВариант, каждый элемент которого это МассивВарианта (или список значений, не так важно), каждый элемент которого это Элемент.
По теме из базы знаний
Вознаграждение за ответ
Показать полностью
Найденные решения
22. zannv 85 16.04.21 11:04 Сейчас в теме
Всем спасибо, решение найдено. Получился универсальный алгоритм с нефиксированным количеством элементов. Безусловно, чем больше элементов, тем значительно дольше идет процесс. Но он идет, и на выходе получается нужный массив вариантов. Внутри алгоритма использовалась функция https://infostart.ru/1c/articles/365025/ как вспомогательная.
Остальные ответы
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
6. -AI- 15.04.21 06:35 Сейчас в теме
(5) так это задача не для программирования, а обычная комбинаторика.

Необходимо найти все варианты
логичнее должно звучать "найти количество" всех возможных вариантов.
7. zannv 85 15.04.21 08:44 Сейчас в теме
(6) мне на выходе не нужно количество, мне нужен массив с массивами
10. -AI- 15.04.21 09:13 Сейчас в теме
(7) и что в этих масивах должно быть? ещё массивы?
11. zannv 85 15.04.21 09:36 Сейчас в теме
(10)По примеру на выходе вижу примерно так:

МассивРезультат:

МассивРезультат[0] - Вариант 1

МассивРезультат[0][0] - Массив 1
МассивРезультат[0][0][0] - 0
МассивРезультат[0][0][1] - 1
МассивРезультат[0][0][2] - 2

МассивРезультат[1] - Вариант 2

МассивРезультат[1][0] - Массив 1
МассивРезультат[1][0][0] - 0
МассивРезультат[1][0][1] - 1
МассивРезультат[1][1] - Массив 2
МассивРезультат[1][1][0] - 2
и т.д.

Причем вместо массива элементов, например, "МассивРезультат[0][0] - Массив 1", может быть список значений, это не так важно
2. МихаилМ 15.04.21 01:21 Сейчас в теме
чем вариант https://forum.infostart.ru/forum9/topic260345/
не подошел. вы написали точто нужно
4. zannv 85 15.04.21 04:28 Сейчас в теме
(2) там стояла другая задача
3. МихаилМ 15.04.21 01:26 Сейчас в теме
а теперь пусть элементов будет 25.
черт с ним быстродейтвием на несколькот часов , а озу сколько потребуется ?
лучше опишите конечную задачу.
5. zannv 85 15.04.21 04:32 Сейчас в теме
(3) Элементов может быть и больше. Зачем мне описывать конечную задачу, если мне нужно решить подзадачу, которую я и описала?)
19. vv2 16.04.21 10:23 Сейчас в теме
(5) Потому что, случается так, что исходная задача решается другими методами проще и быстрее.
20. ishelper 16.04.21 10:33 Сейчас в теме
(17)
Где и как вы будете такое хранить?
"Я не буду думать об этом сегодня, я подумаю об этом завтра" (с)
(19)
случается так, что исходная задача решается другими методами проще и быстрее.
Абсолютно бесполезно доказывать женщине, что ее хотелка - ошибочна. :)
21. zannv 85 16.04.21 10:46 Сейчас в теме
(20) Давайте не будем опускаться до сексизма) Во-первых, "хотелка" вовсе не моя, а пользователя. Соответственно, где и как будет "такое" храниться не моя и не ваша проблема. Стояла задача (осознанная) написать алгоритм, а не оправдать неспособность это сделать доказательствами нецелесообразности метода.
8. user1278383 3 15.04.21 09:12 Сейчас в теме
Элементы начального массива уникальны?
9. zannv 85 15.04.21 09:13 Сейчас в теме
12. comptr 30 15.04.21 09:55 Сейчас в теме
Нужно перебрать все возможные варианты разбития исходного количество элементов на группы, а потом для каждой группы применить алгоритм поиска сочетаний, как в https://infostart.ru/public/240261.

Пусть у нас N элементов.
Тогда группы будут (буду обозначать их количеством элементов):

N

1, N-1
2, N-2
...
N-1, 1

1, 1, N-2
1, 2, N-3
...
1, N-2, 1

2, 1 N-3
...
2, N-3, 1

и так далее, пока не дойдём до группы 1, 1, 1 ... 1 (N массивов по одному элементу)

-------

Можно попробовать пойти обратным путём:
Возьмём начальное разбиение на N массивов по одному элементу в каждом: 1, 1, 1, ... 1
Будем брать один элемент массива #1 и по очереди добавлять в каждый другой массив:
2, 1, 1, ... 1
1, 2, 1, ... 1
...
1, 1, 1, ... 2
Потом так же сделаем для элемента массива #2, потом #3 и так до N.

На следующем шаге из каждого варианта мы будем генерировать новый вариант по этому же принципу.

-------
В любом случае, количество вариантов будет расти по экспоненте.

Какое количество элементов планируется разбивать?
13. comptr 30 15.04.21 10:19 Сейчас в теме
(12) Для 4 элементов будет 47 вариантов: C(4,4) + C(4,1) * C(3,3) + C(4,2) * C(2,2) + C(4,1) * C(3,1) * C(2,2) + C(4,1) * C(3,1) * C(2,1) * C(1,1)

Для 5 уже 241: C(5,5) + C(5,2) * C(3,3) + C(5,1) * C(4,1) * C(3,3) + C(5,1) * C(4,2) * C(2,2) + C(5,1) * C(4,1) * C(3,1) * C(2,2) + C(5,1) * C(4,1) * C(3,1) * C(2,1) * C(1,1)

Конечно, это с повторами, когда (1, 2) и (2, 1) будут считаться разными вариантами.
14. SlavaKron 15.04.21 10:51 Сейчас в теме
(13)
Для 4 элементов будет 47 вариантов
Если порядок в массивах не важен и порядок самих массивов не важен, то для 4-х элементов получается 5 различных вариантов разбиения на массивы и всего 15 вариантов распределения:
1.	(1,2,3,4)

2.	(1,2,3) (4)
3.	(1,2,4) (3)
4.	(1,4,3) (2)
5.	(4,2,3) (1)

6.	(1,2) (3,4)
7.	(1,3) (2,4)
8.	(1,4) (2,3)

9.	(1,2) (3) (4)
10.	(1,3) (2) (4)
11.	(1,4) (3) (2)
12.	(2,3) (1) (4)
13.	(4,2) (3) (1)
14.	(4,3) (2) (1)

15.	(1) (2) (3) (4)
Показать
16. comptr 30 15.04.21 12:26 Сейчас в теме
(14) ну да, только нужно ещё тогда уметь определять "дубли".
15. zannv 85 15.04.21 11:15 Сейчас в теме
(12) Количество элементов не важно.
Оно может быть любым.
Ну на практике, скажем, до 100 элементов будет.
17. comptr 30 15.04.21 14:14 Сейчас в теме
(15) попробовал прикинуть количество вариантов в зависимости от числа элементов и сравнил это с 2^n
1: 1 -> 2^1 = 2
2: 2 -> 2^2 = 4
3: 5 -> 2^3 = 8
4: 15 -> 2^4 = 16
5: 67 -> 2^5 = 32
6: 297 -> 2^6 = 64

Допустим даже, что мы ограничимся 2^n.

Если взять, например, 40 элементов, то количество комбинаций будет 2^40, а это примерно 10^12. Каждая комбинация содержит 40 цифр = 40 байт. Значит в памяти это будет занимать 10^12 * 40 байт = 44 терабайта.
Где и как вы будете такое хранить?

Даже если написать алгоритм, который будет такое считать, как вы будете им пользоваться? Где хранить результат вычислений? Без дополнительных ограничений что-то дельное сделать вряд ли получится.
18. JohnGalt 57 16.04.21 10:16 Сейчас в теме
Как вариант, если хотя бы примерно известно количество элементов в массиве и количество массивов, то можно в цикле с фиксированным количеством итераций можно заполнить таблицу элементами массивов и свернуть.
22. zannv 85 16.04.21 11:04 Сейчас в теме
Всем спасибо, решение найдено. Получился универсальный алгоритм с нефиксированным количеством элементов. Безусловно, чем больше элементов, тем значительно дольше идет процесс. Но он идет, и на выходе получается нужный массив вариантов. Внутри алгоритма использовалась функция https://infostart.ru/1c/articles/365025/ как вспомогательная.
23. МихаилМ 17.04.21 13:22 Сейчас в теме
(0) расскажите об экономическом смысле задачи
Оставьте свое сообщение
Вакансии
Программист 1С
Казань
зарплата от 150 000 руб.
Полный день

Программист 1С:ERP
Москва
зарплата от 100 000 руб.
Полный день

Разработчик 1С
Москва
зарплата от 200 000 руб. до 300 000 руб.
Полный день

Программист 1С (удаленно)
Самара
зарплата от 230 000 руб. до 230 000 руб.
Полный день

Руководитель группы разработки 1С
Москва
зарплата от 250 000 руб. до 250 000 руб.
Полный день