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

Dima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.

exp98,
а если и по 3, и по 4 и по.....

Александр Бердышев,

Идея хорошая.
Но дело в следующем: как заполнить такую матрицу, размером, например, 120 х 120.
Вариантов где-то 6,64614E+35.
Можно начать и с меньших значений.

Gennadiy UsovАлександр Бердышев,

Идея хорошая.
Но дело в следующем: как заполнить такую матрицу, размером, например, 120 х 120.
Вариантов где-то 6,64614E+35.
Можно начать и с меньших значений.
Ошибся.
Для доски 1000х1000, наверное, потребуется сделать комбинации из 67 чисел.
Вариантов где-то 7,3787E+19.

m7mЕсли я правильно понял и нигде не ошибся
то как-то так

Сочетание из N по К (K>1)

1. цикл L от 1 до N-K+1
1.1. Заполняем M[1]=L; M[2]=L+1;... M[K-1]=L+K-2; --(Это тоже циклом, лень писать)
1.2. цикл J от L+K-1 до N
1.2.1. M[K]=J;
1.2.2. Здесь имеем в M очередное сочетание
Я попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное !

S.G.,

Спасибо за информацию. Изучаю.

Dima TGennadiy UsovЯ попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное !
Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.
Все варианты. А потом буду отбрасывать те, в которых не устраивает сочетания цифр. Или делать это параллельно.

Dima TGennadiy UsovВариантов где-то 7,3787E+19.
Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет
Пока я не говорю о вычислении.
Я пока говорю об алгоритме.
А там будет видно, для каких досок данный алгоритм будет применим с точки зрения производительности.

Александр БердышевБуквально на прошлой неделе решал задачу с сочетаниями.

ABCD - 4 символаю
сочетаний будет 2^4 - 1. Если сочетаний n, то 2^n - 1

Как решать:
ABCD

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

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

Как ты понял, в матрице будет i в двоичном представлении.
Спасибо Александр Бердышев!
По новому посмотрел на это сообщение.
Вот оно решение.
И не надо сложных программ, и не нужно много времени.

Если посмотреть на данный перечень сочетаний, то оказывается, что он состоит из последовательности чисел от 1 до 15, представленных в двоичном виде (есть ошибка: вместо первого 1111 надо писать 1000).
То есть,
" загоняя" в массив перменных последовательность чисел от 1 до ..... вообщем много, получаем нужные нам сочетания, выбирая эти сочетания из элемента массива по-битово.
Все!!!!

Теперь нужно понять: какова вместительность ячейки на отдельно взятом компьютере.

Gennadiy UsovДля доски 1000х1000, наверное, потребуется сделать комбинации из 67 чисел.
Вариантов где-то 7,3787E+19.

То есть,
" загоняя" в массив перменных последовательность чисел от 1 до ..... вообщем много, получаем нужные нам сочетания, выбирая эти сочетания из элемента массива по-битово.
Все!!!!

Теперь нужно понять: какова вместительность ячейки на отдельно взятом компьютере.
Далее интереснее.

Могут сказать, что не хватит памяти для массива из 7,3787E+19 чисел, а если смотреть большие доски, и большие массивы.
Однако если еще раз взглянуть на сочетания, которые представил Александр Бердышев, то окажется, что

сочетания с 8 по 15 повторяют сочетания с 1 по 7 (с добавлением сочетания 0000) при добавлении сочетания 1, но уже со сдвигом по колонкам на 3 колонки.
То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

Мы можем для удобства выстроить любую систему счисления, в зависимости от удобства, кратную 2.

Если не удобно работать в двоичной системе и в работе с битами, то можно раотать в десятичной.
Для этого формируем матрицу 10 х 512, и формируем элементы этой матрицы следующим образом: либо 1, либо 0.
Такая матрица формирууется 1 раз.
Аналогично восьмеричной системе, с помощью такой матрицы можно формировать любые сочетания для очень больших массивов.

Попробую ответить сразу всем.
S.G.Gennadiy Usov То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

Мы можем для удобства выстроить любую систему счисления, в зависимости от удобства, кратную 2.
Все можно, только с временем будет напряг 21282030
Когда-нибудь напряг всегда наступает.
А использовать или не использовать алгоритм уже решают пользователь и его компьютер. Главное, чтобы алгоритм был.

Dima TТут посмотри
https://prog-cpp.ru/placement/
https://prog-cpp.ru/combinations/
Спасибо. Я конечно посмотрю.
С другой стороны получился неплохой алгоритм поиска сочетаний 21282517 . Удобный, и цикл только один: от 1 до N.
Чем этот алгоритм не нравится?

Мудроглюков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.
Такое число для выше указанного метода вряд ли подойдет: не влезет в ячейку. А если влезет, то пропадут всякие о-малые.
Поэтому необходимо несколько видоизменить алгоритм.

Gennadiy Usov сочетания с 8 по 15 повторяют сочетания с 1 по 7 (с добавлением сочетания 0000) при добавлении сочетания 1, но уже со сдвигом по колонкам на 3 колонки.
То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

Мы можем для удобства выстроить любую систему счисления, в зависимости от удобства, кратную 2.
Попробуем взглянуть на проблему по другому.
Имеем число А = 2 в степени 250.
Данное число можно представить как А = В в степени 10, где В = 2 в степени 25.
Количество сочетаний для 25 чисел равно 16777216. Данное число будет «считабельно». И все сочетания для 25 чисел поместим в массив С (25, 16777216), естественно, вместе с 00000….00000.
Осталось придумать алгоритм собирания 10 сочетаний по 25 из массива С в одно сочетание по 250.

Gennadiy UsovИмеем число А = 2 в степени 250.
Данное число можно представить как А = В в степени 10, где В = 2 в степени 25.
Количество сочетаний для 25 чисел равно 16777216. Данное число будет «считабельно». И все сочетания для 25 чисел поместим в массив С (25, 16777216), естественно, вместе с 00000….00000.
Осталось придумать алгоритм собирания 10 сочетаний по 25 из массива С в одно сочетание по 250.
Рассмотрим один из возможных алгоритмов, позволяющих решить данную задачу.
Допустим имеется массив сочетаний С(25, 16777216), массив сочетания С1 (250), массив счетчиков Р(10) и общий счетчик Р1.
Присвоим всем значениям счетчика значение 1:
Р( i ) = 1, 1 <= i <= 10, Р1 =1, Р2 = 16777216, где Р1 – счетчик сочетаний по 250.
Метка 1:
Далее основное присвоение:
цикл С1( j + 25 * (i – 1)) = С( j, Р( i ) ), 1 <= i <= 10, 1 <= j <= 25.
Р( 1 ) = Р( 1 ) + 1, Р1 = Р1 +1,
если Р( 1 ) > Р2 то
(Р( 1 ) = 1,
Р( i ) = Р( i ) +1, 2 <= i <= 10,
если Р( i ) <= Р2 то (переход к метке 1) иначе Р( i ) = 1).
Здесь массив С1 (250) - одномерный. Но можно его сделать двумерным с помощью счетчика Р1.
Можно рассмотреть другие варианты соотношений длины малых массивов и их количества : 10 и 25, 50 и 5, 5 и 50.

Gennadiy UsovТеперь появилась новая задачка:
Имеется несколько последовательностей чисел: 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 х К.
Перед тем как считать все сочетания в лоб, попробуем оценить количество сочетаний.
Разделим массив 1 + Кх2 на части:
в первую группу возьмем первые числа от 1 до К +1,
во вторую группу возьмем остальные К чисел.
Тогда в первой группе получается Р1 = (2 в степени (К + 1)) сочетаний чисел, а во второй группе получается Р2 = (2 в степени К ) сочетаний чисел.
Попробуем складывать сочетания из первой и второй группы.
В силу условий несовместимости отдельных чисел получается следующая зависимость:
при выборке по 1 числу из второй группы первая группа уменьшается в два раза,
при выборке по 2 числа из второй группы первая группа уменьшается в четыре раза,
при выборке по 3 числа из второй группы первая группа уменьшается в восемь раз,
…
При выборке всех чисел из второй группы имеем только 2 сочетаний из первой группы.
Осталось только сложить между собой произведения сочетаний (к по n ) на число (2 в степени (К + 1- к)).
Наверное, есть формула по определению таких сумм.
Может быть кто-то встречал такую формулу?

exp98Gennadiy Usov,
формула по определению таких сумм безусловно есть, только знают её не только лишь все, мало кто вообще её знает.

А если б/сарказма, то можно попробовать метод производящих функций. Как раз есть возможность представить в рекуррентном виде.
Спасибо!
Посмотрел производящие функции.
https://ru.wikipedia.org/wiki/Сочетание
Сумма сочетаний умноженных на х в степени к.
У нас х = 2. Только умножение идет на 2 в степени (К + 1- к).
С другой стороны, сочетание (к по n) равно сочетанию ( (n- к) по n). То есть, сумму произведений сочетаний на степень можно развернуть в другую сторону. И получается нормальная производящая функция, только значения каждой степени умноженное еще на 2. Следовательно, значение производящая функция равно:
2 х ( 1 + 2 ) (в степени n).
Кажется так.
Проверки на массивах вручную показали:
массив 3 – 6 сочетаний, массив 5 – 18 сочетаний, массив 7 – 54 сочетаний.
Следовательно, можно говорить, что для массива из 83 чисел имеем 2,66056E+39 сочетаний.