МудроглюковGennadiy UsovБольшая просьба!
Не подскажите, где можно найти алгоритм поиска всех возможных сочетаний из К чисел, включая одно число.
Хотя с одним числом все ясно.
Данный алгоритм необходим для поиска сочетаний двоек вертикалей при определения решений на досках МхМ.
В дальнейшем необходимо будет ввести ограничения, например, цифра 4 не может быть с цифрой 7 в одном сочетании.

это обычно называют комбинаторной генерацией с, тоже обычным, отсечением неподходящих
вариантов на разных шагах генерации очередного варианта

Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?
Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5,6, далее 1,2,3,4,5,6,7,8,9, и т.д.
Для каждой нужно найти все сочетания. При этом:
В первой последовательности в одном сочетании не могут быть 1 и 2, во второй - 1 и 3, 2 и 4, 3 и 5, 4 и 6,
в третьей - 1 и 4, 2 и 5, 3 и 6, 4 и 7, 5 и 8, 6 и 9 и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность, длиной 3 х К.
Вот и все.

Мне предложили несколько вариантов алгоритмов определения сочетаний, так что глаза разбегаются. Буду изучать эти алгоритмы и сравнивать.
А пока попробую составить свой алгоритм, ведь остальные создают свои алгоритмы, о котором говорил в сообщении 21282517 .

Допустим, что есть последовательность чисел от 1 до М1.
Массив С (М1) предназначен для хранения одного сочетания.
Необходимо найти все сочетания этих чисел.

A = i, 1 <= i <= B, B = (2 в степени М1) – 1, А - переменная.

Переводим А в двоичный вид и каждую цифру двоичного вида числа А (0 или 1) помещаем в элементы массива С (М):
j = 1,
С( 1 ) = остаток от деления (А / 2), D = А / 2, D – переменная,
метка 1:
если мы хотим иметь в массиве С не единицы, а конкретные цифры, то С ( j ) = j,
если D = 0 то (массив С (М) сформирован, М = j, ищем новое значение А – переходим на метку 2).
j = j +1, С ( j ) = остаток от деления (С ( j - 1 ) / 2), D = С ( j - 1 ) / 2, возврат на метку 1.

метка 2:
Теперь можно для запоминания сочетания поместить его в двумерный массив:
С1 (I, j ) = С ( j ), 1 <= j <= М, С1 (В, М1 ) и
остальные ячейки строки заполнить нулями:С1 (I, j ) = 0, М < j <= М1,

Получается, что массив сочетаний состоит либо из 0 и 1, либо из 0 и конкретных цифр. Можно добавить процедуру, если нужно, которая убирает нули.
Вот и все сочетания.

Алгоритм 21283691 позволяет частично решить задачу 21283022 .
В задаче В чисел, причем В кратно 3. Разделим эти числа на три части, А = В/3, в первой части первые А чисел, во второй - средние А чисел, в третьей - последние А чисел.
Для первых А чисел количество сочетаний будет равно В1, где В1= 2 в степени А. Эти сочетания будут соответствовать числа от 0 до (В1 - 1). Здесь 0 необходим, поскольку будут циклы.
Теперь можно найти сочетания для чисел, которые составляют 1-ую и 3-ю части.
Для этой цели формируем массив В2 (В3), где В3 = В1 х В1.
Тогда В2 (i x В1 + j) = i x В3 + j, 0 <= i <= В1, 0 <= j <= В1.
Чтобы определить сочетания, надо элементы массива В2 (В3) разложить на составляющие согласно алгоритму 21283691

unregestered https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать
Это к чему?

unregestered https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать
при чем здесь лицензии, или просто что-то надо сказать, типа, скучно

Gennadiy UsovВ задаче В чисел, причем В кратно 3. Разделим эти числа на три части, А = В/3,

Может оказаться, что при достаточно больших значений В, например, для доски 1000х1000 это значение более 20, количество сочетаний может превышать размер ячейки на компьютере. Поэтому лучше использовать массивы сочетаний более мелких массивов, а уже их них составлять большие массивы способом, аналогичным алгоритму 21283691 .

Александр Бердышев Если сочетаний n, то 2^n - 1

0001
0010
0011
0100
0101
0110
0111
1111
1001
1010
1011
1100
1101
1110
1111

Строишь такую матрицу из 0 и 1.
Потом цикл от i = 1 до n
i - строка.
Где единицы - берёшь символ, где 0 - не берёшь символ.

Есть еще вариант представления сочетаний с использованием этой ЗАМЕЧАТЕЛЬНОЙ картинки:
На картинке 15 сочетаний. Добавляем к ним вначале 16-е сочетание - 0000.
Пусть эти сочетания находятся в матрице большого размера, и сочетания в этой матрице имеют координаты: колонки (1,2,3,4) и строчки (1,2,...16).
Тогда матрица 4х16 копируется и добавляется к начальной матрице. Получаем матрицу 4х32.
Теперь добавляем к добавленной матрице 5-ю колонку с 1, и новая добавленная матрица и начальная матрица образуют матрицу 5х32 ( у начальной матрице в 5-й колонке будут 0).
В результате получили сочетания для пяти чисел!
Аналогично можно будет построить сочетания для любых чисел, если позволяет компьютер (размер матрицы!).
Сочетание 0000 используется только для построения матриц, при использовании матриц в расчетах это сочетание не нужно.

Теперь появилась новая задачка:
Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5, далее 1,2,3,4,5,6,7, и т.д.
Для каждой последовательности чисел нужно найти все сочетания. При этом:
в первой последовательности в одном сочетании не могут быть 1 и 3,
во второй - 1 и 4, 2 и 5,
в третьей - 1 и 5, 2 и 6, 3 и 7, и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность чисел, длиной 1 + 2 х К.

MBoВот для примера 5/3 (1,2,3,4,5, не могут быть 1 и 4, 2 и 5)
00000
10000
01000
11000
00100
10100
01100
11100
00010
01010
00110
01110
00001
10001
00101
10101
00011
00111
Когда рассматриваешь массивы очень большие, необходимо иметь программное обеспечение для поиска сочетаний. Ручной способ здесь не помогает

MBoGennadiy Usov,

С такими ограничениями проще всего сделать рекурсивную генерацию - на следующий уровень рекурсии передаем текущий набор (не стоит называть их сочетаниями - всё-таки сочетание есть устоявшийся термин из комбинаторики) и модифицированную маску ограничения


А если количество цифр 250? Можно будет определить все сочетания?

MBoGennadiy Usov,

авторА если количество цифр 250? Можно будет определить все сочетания?

2^250 множеств нереально перебрать, и тем более обработать и вывести или записать.
С ограничениями их будет поменьше, но даже 2^64 уже непомерно много (понадобится 600 лет при генерации миллиарда множеств в секунду)
1. А сколько будет немного? И как быть с величиной ячейки?
2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений 20960899 ?
3. А помечтать, что компьютер будет когда-то быстрее?

MBoGennadiy Usov,

>1. А сколько будет немного? И как быть с величиной ячейки?

Если перебирать все варианты, то считабельно 2^32-2^42 (10^14). Про ячейки я не в курсе.

>2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений20960899?

Вероятно, они используют алгоритм, не требующий брутфорсного перебора
А если и здесь будет алгоритм, а не прочий перебор?

MBoGennadiy Usov,

авторА если и здесь будет алгоритм, а не прочий перебор?

Ну так его, видимо, и нужно придумать? Хорошая идея алгоритма может позволить если и не уйти
от экспоненциального роста сложности, то хотя бы понизить его показатель
Согласен.
Пока вижу одну трудность в алгоритме 21283691 , которая заключается в следующем:
чтобы выйти с алгоритмом, который находит большое множество решений, на доску 1001х1001 (или близкую к ней) 21035592 , нужно найти возможность определения различных сочетаний для 250 чисел (количество независимых "четверок" ферзей на данной доске). А это где-то 9,04626E+74.
Такое число для выше указанного метода вряд ли подойдет: не влезет в ячейку. А если влезет, то пропадут всякие о-малые.
Поэтому необходимо несколько видоизменить алгоритм.