Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8 9      [все]
 Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Большая просьба!
Не подскажите, где можно найти алгоритм поиска всех возможных сочетаний из К чисел, включая одно число.
Хотя с одним числом все ясно.
Данный алгоритм необходим для поиска сочетаний двоек вертикалей при определения решений на досках МхМ.
В дальнейшем необходимо будет ввести ограничения, например, цифра 4 не может быть с цифрой 7 в одном сочетании.
23 мар 18, 14:01    [21280792]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Сочетания
23 мар 18, 14:03    [21280799]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.
23 мар 18, 16:19    [21281330]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
exp98
Member

Откуда:
Сообщений: 1492
Ну ведь если для парных, то ваще просто в лоб: каждый с каждым и "пополам", верхний треугольник 2мерной матрицы перебора.
23 мар 18, 17:32    [21281629]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
exp98,
а если и по 3, и по 4 и по.....
23 мар 18, 17:45    [21281685]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
m7m
Member

Откуда: Украина, Мариуполь
Сообщений: 1290
Gennadiy Usov
exp98,
а если и по 3, и по 4 и по.....


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

Сочетание из 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 очередное сочетание
23 мар 18, 18:48    [21281807]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Александр Бердышев
Member

Откуда: Санкт-Петербург
Сообщений: 213
Буквально на прошлой неделе решал задачу с сочетаниями.

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 в двоичном представлении.
23 мар 18, 19:03    [21281836]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Александр Бердышев,

Идея хорошая.
Но дело в следующем: как заполнить такую матрицу, размером, например, 120 х 120.
Вариантов где-то 6,64614E+35.
Можно начать и с меньших значений.
23 мар 18, 19:30    [21281904]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T,

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

Есть формула вычисления приближенного значения факториала, но для точного значения считать как в школьном учебнике, т.е. для n! перемножить числа от 1 до n.
23 мар 18, 19:54    [21281947]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Gennadiy Usov
Александр Бердышев,

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

Ошибся.
Для доски 1000х1000, наверное, потребуется сделать комбинации из 67 чисел.
Вариантов где-то 7,3787E+19.
23 мар 18, 20:00    [21281957]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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 очередное сочетание

Я попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное!
23 мар 18, 20:05    [21281966]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30607
Gennadiy Usov
Dima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.
на каком языке программирования?
23 мар 18, 20:07    [21281971]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30607
паскаль:

http://www.cyberforum.ru/turbo-pascal/thread113383.html

http://moul49.narod.ru/pascal/Pascal_10_1.pdf

http://e-maxx.ru/algo/generating_combinations
23 мар 18, 20:10    [21281979]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Я попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное!

Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.
23 мар 18, 20:31    [21282012]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
S.G.,

Спасибо за информацию. Изучаю.
23 мар 18, 20:32    [21282018]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Я попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное!

Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.

Все варианты. А потом буду отбрасывать те, в которых не устраивает сочетания цифр. Или делать это параллельно.
23 мар 18, 20:37    [21282024]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...

Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.

Все варианты. А потом буду отбрасывать те, в которых не устраивает сочетания цифр. Или делать это параллельно.

Gennadiy Usov
Вариантов где-то 7,3787E+19.

Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет
23 мар 18, 20:50    [21282030]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Вариантов где-то 7,3787E+19.

Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет

Пока я не говорю о вычислении.
Я пока говорю об алгоритме.
А там будет видно, для каких досок данный алгоритм будет применим с точки зрения производительности.
23 мар 18, 20:56    [21282042]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

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

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 до ..... вообщем много, получаем нужные нам сочетания, выбирая эти сочетания из элемента массива по-битово.
Все!!!!


Теперь нужно понять: какова вместительность ячейки на отдельно взятом компьютере.
24 мар 18, 07:08    [21282517]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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.
24 мар 18, 07:22    [21282522]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Если не удобно работать в двоичной системе и в работе с битами, то можно раотать в десятичной.
Для этого формируем матрицу 10 х 512, и формируем элементы этой матрицы следующим образом: либо 1, либо 0.
Такая матрица формирууется 1 раз.
Аналогично восьмеричной системе, с помощью такой матрицы можно формировать любые сочетания для очень больших массивов.
24 мар 18, 09:07    [21282572]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Тут посмотри
https://prog-cpp.ru/placement/
https://prog-cpp.ru/combinations/
24 мар 18, 11:23    [21282690]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Мудроглюков
Member

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


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

и конечно есть куча алгоритмов

и есть, уже традиционная, теория таких алгоритмов
вот, например, Рейнгольд, Нивергельт, Део Комбинаторные алгоритмы. Теория и практика. 1980 год (!)
...
Кнут начинал писать в 4 томе про это, дабы обощить еще более обще, но не дописал

______________
Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?
24 мар 18, 13:07    [21282841]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30607
Gennadiy Usov
То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

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

Все можно, только с временем будет напряг 21282030
24 мар 18, 13:56    [21282934]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Попробую ответить сразу всем.
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.
Чем этот алгоритм не нравится?
24 мар 18, 15:15    [21283013]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Мудроглюков
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 х К.
Вот и все.
24 мар 18, 15:24    [21283022]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
С другой стороны получился неплохой алгоритм поиска сочетаний21282517. Удобный, и цикл только один: от 1 до N.
Чем этот алгоритм не нравится?

Если подошел, то пользуйся. Мне показалось там совсем про другую задачу.
24 мар 18, 15:25    [21283023]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8313
Gennadiy Usov
Мудроглюков
пропущено...


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

Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?

Имеется несколько последовательностей чисел: 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 х К.
Вот и все.


в таком контексте наверно не последовательности (математические), а наборы из чисел из ... от 1 до 99 ...
и сочетания же: из множества М по сколько и с повторениями ли?
24 мар 18, 16:16    [21283046]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Треугольник Паскаля нам тут в помощь?
24 мар 18, 17:00    [21283073]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov,

Перебор перестановок, размещений, сочетаний http://www.guildalfa.ru/alsha/node/26
24 мар 18, 18:44    [21283210]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Мне предложили несколько вариантов алгоритмов определения сочетаний, так что глаза разбегаются. Буду изучать эти алгоритмы и сравнивать.
А пока попробую составить свой алгоритм, ведь остальные создают свои алгоритмы, о котором говорил в сообщении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 и конкретных цифр. Можно добавить процедуру, если нужно, которая убирает нули.
Вот и все сочетания.
25 мар 18, 06:53    [21283691]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Алгоритм 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
26 мар 18, 16:52    [21287095]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
unregestered
Member

Откуда:
Сообщений: 351
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать
26 мар 18, 17:40    [21287301]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

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

Это к чему?
26 мар 18, 19:30    [21287635]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
unregestered
Member

Откуда:
Сообщений: 351
что к чему?
27 мар 18, 01:39    [21288254]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

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

при чем здесь лицензии, или просто что-то надо сказать, типа, скучно
27 мар 18, 05:48    [21288288]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Gennadiy Usov
В задаче В чисел, причем В кратно 3. Разделим эти числа на три части, А = В/3,


Может оказаться, что при достаточно больших значений В, например, для доски 1000х1000 это значение более 20, количество сочетаний может превышать размер ячейки на компьютере. Поэтому лучше использовать массивы сочетаний более мелких массивов, а уже их них составлять большие массивы способом, аналогичным алгоритму 21283691.
27 мар 18, 07:28    [21288326]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8313
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

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


А какие алгоритмы-то использовал автор?
Или чт автор считает, что он что-то оригинальное реализовал,
хотя может быть, что ОРИГИНАЛЬНОЕ - тогда тем более заявить-описать "в чем и что оригинальное?"?

_______
Вот ПЕРЕСТАНОВКИ - уже выделяют ЧЕТЫРЕ типа алгоритмов:
- лексикографическое упорядочение
- вестор инверсий
- транспозиции смежных элементов
- вложенные циклы
ЗЫ и для разных задач - разные типы по-разному пригодны оказываются (при углублении в тему открываются всякая всячина)
ЗЫ 5-ый тип может быть уже кем-то изобретен.
27 мар 18, 07:51    [21288376]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Александр Бердышев
Если сочетаний 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 используется только для построения матриц, при использовании матриц в расчетах это сочетание не нужно.
29 мар 18, 07:22    [21294829]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Теперь появилась новая задачка:
Имеется несколько последовательностей чисел: 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 х К.
29 мар 18, 08:01    [21294859]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Gennadiy Usov,

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

   procedure GenLimitedSets(NMax, ASet, CurIdx, Mask, LimGap: integer);
   var
     tm: Integer;
   begin
     if CurIdx = NMax then
        Memo1.Lines.Add(BinS(ASet, NMax))  //бинарное представление числа
     else begin
        GenLimitedSets(NMax, ASet, CurIdx + 1, Mask, LimGap);
        tm := 1 shl (CurIdx + 1);
        if (Mask and tm) = 0 then
           GenLimitedSets(NMax, ASet or tm, CurIdx + 1, Mask or (tm shl LimGap), LimGap);
     end;

   end;

  GenLimitedSets(6, 0, 0, 0, 2);

000000
100000
010000
110000
001000
011000
000100
100100
001100
000010
100010
010010
110010
000110
100110
000001
100001
010001
110001
001001
011001
000011
100011
010011
110011
29 мар 18, 08:56    [21294937]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Вот для примера 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
29 мар 18, 09:03    [21294958]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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

Когда рассматриваешь массивы очень большие, необходимо иметь программное обеспечение для поиска сочетаний. Ручной способ здесь не помогает
29 мар 18, 10:13    [21295187]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
MBo
Gennadiy Usov,

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


А если количество цифр 250? Можно будет определить все сочетания?
29 мар 18, 10:35    [21295278]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Gennadiy Usov,

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


2^250 множеств нереально перебрать, и тем более обработать и вывести или записать.
С ограничениями их будет поменьше, но даже 2^64 уже непомерно много (понадобится 600 лет при генерации миллиарда множеств в секунду)
29 мар 18, 10:47    [21295322]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
MBo
Gennadiy Usov,

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


2^250 множеств нереально перебрать, и тем более обработать и вывести или записать.
С ограничениями их будет поменьше, но даже 2^64 уже непомерно много (понадобится 600 лет при генерации миллиарда множеств в секунду)

1. А сколько будет немного? И как быть с величиной ячейки?
2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений20960899?
3. А помечтать, что компьютер будет когда-то быстрее?
29 мар 18, 11:17    [21295450]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Gennadiy Usov,

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

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

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

Вероятно, они используют алгоритм, не требующий брутфорсного перебора
29 мар 18, 11:29    [21295487]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
MBo
Gennadiy Usov,

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

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

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

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

А если и здесь будет алгоритм, а не прочий перебор?
29 мар 18, 12:07    [21295670]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Gennadiy Usov,

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


Ну так его, видимо, и нужно придумать? Хорошая идея алгоритма может позволить если и не уйти
от экспоненциального роста сложности, то хотя бы понизить его показатель
29 мар 18, 12:15    [21295694]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
MBo
Gennadiy Usov,

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


Ну так его, видимо, и нужно придумать? Хорошая идея алгоритма может позволить если и не уйти
от экспоненциального роста сложности, то хотя бы понизить его показатель

Согласен.
Пока вижу одну трудность в алгоритме21283691, которая заключается в следующем:
чтобы выйти с алгоритмом, который находит большое множество решений, на доску 1001х1001 (или близкую к ней) 21035592, нужно найти возможность определения различных сочетаний для 250 чисел (количество независимых "четверок" ферзей на данной доске). А это где-то 9,04626E+74.
Такое число для выше указанного метода вряд ли подойдет: не влезет в ячейку. А если влезет, то пропадут всякие о-малые.
Поэтому необходимо несколько видоизменить алгоритм.
29 мар 18, 13:00    [21295868]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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.
29 мар 18, 13:25    [21295991]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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.
30 мар 18, 12:36    [21298982]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
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- к)).
Наверное, есть формула по определению таких сумм.
Может быть кто-то встречал такую формулу?
30 мар 18, 13:43    [21299298]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
exp98
Member

Откуда:
Сообщений: 1492
Gennadiy Usov,
формула по определению таких сумм безусловно есть, только знают её не только лишь все, мало кто вообще её знает.

А если б/сарказма, то можно попробовать метод производящих функций. Как раз есть возможность представить в рекуррентном виде.
30 мар 18, 14:04    [21299400]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
exp98
Gennadiy 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 сочетаний.
30 мар 18, 20:02    [21300743]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Замечен интересный момент периодичности или цикличности расположения сочетаний в массиве сочетаний из n цифр.
Для первой колонке справо имеем сначала 0, потом 1, затем 0 и опять 1, то есть 1 на 1.
Для второй колонки будет 2 на 2.
Для третьей колнки будет 4 на 4.
Для четвертой колонки будет 8 на 8.
и т. д.
Для колонки n будет Р на Р, где Р = 2 в степени n.
31 мар 18, 11:32    [21301656]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Gennadiy Usov
Алгоритм 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

Теперь добавляем средние А чисел.
И смотрим, сколько теперь получается сочетаний.
В ручном режиме получилось следующее:
для трех цифр получается 5 сочетаний,
для шести цифр получается 25 сочетаний,
для девяти цифр получается 125 сочетаний.
Если рассмотреть все сочетания, то оказывается, что получается сумма произведений сочетаний (к по n) на число 4 в степени к. То есть, это производящие функции. И сумма этих произведений будет
(1 + 4 ) в степени n.
31 мар 18, 19:27    [21302076]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Сообщение. Алгоритм определения сочетаний чисел, часть из которых несовместима с другими числами.
Ранее в сообщениях 21302076 21300743 говорилось о сочетаниях таких чисел. Приводятся описание алгоритмов определения сочетаний.

К сообщению приложен файл (Сочетания 1.docx - 23Kb) cкачать
9 июн 18, 14:19    [21482003]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Как известно, количество сочетаний из К чисел равно 2^К.

Все эти сочетания можно разбить на пары, которые в «сумме» дадут сочетание 111111…1111. Если требуется оставить из этих пар только одно сочетание, а также убрать сочетания 00000....000 и 1111…111, то останутся 2^(К-1)-1 сочетаний.

Попробую написать программу для поиска таких сочетаний.
27 сен 18, 13:46    [21688151]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 64
Gennadiy Usov,
чего там искать: 00001....01111
27 сен 18, 20:03    [21688516]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Gennadiy Usov
Как известно, количество сочетаний из К чисел равно 2^К.

то о чем вы пишите есть количество подмножеств множества из k элементов,
27 сен 18, 20:06    [21688519]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
Как известно, количество сочетаний из К чисел равно 2^К.

Все эти сочетания можно разбить на пары, которые в «сумме» дадут сочетание 111111…1111. Если требуется оставить из этих пар только одно сочетание, а также убрать сочетания 00000....000 и 1111…111, то останутся 2^(К-1)-1 сочетаний.

Попробую написать программу для поиска таких сочетаний.

У вас - пробелы в дискретной математике.

Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf

Перестановки, сочетания, размещения. Это разные понятия.

В ферзевой задаче я использовал перестановки ладей.
27 сен 18, 20:26    [21688527]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
MBo
Gennadiy Usov,
чего там искать: 00001....01111
То, что точки в двух сочетаниях 00000....000 и 1111…111, это в левом 0, в правом 1, просто 0 или 1 очень много в каждом сочетании.

Идея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).
27 сен 18, 20:29    [21688528]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Идея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).

Если не ошибаюсь то достаточно перебрать все сочетания до 01111111, т.е. до 2^(К-1)
27 сен 18, 20:33    [21688530]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
У вас - пробелы в дискретной математике.
Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf
Перестановки, сочетания, размещения. Это разные понятия.
В ферзевой задаче я использовал перестановки ладей.
Я применил статью
https://ru.wikipedia.org/wiki/Сочетание

Мы с Вами говорим о разных задачах:
- Вы говорите о перестановке ладей (ферзей);
- я говорю о сочетаниях по работе с разными элементами задачи(с какими элементами должны работать в настоящий момент). Это не обязательно ферзи. Это могут быть двойки, тройки, четверки, пятерки и т.д. ферзей.

Поэтому я применяю термин сочетания.
27 сен 18, 20:39    [21688531]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Идея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).
Если не ошибаюсь то достаточно перебрать все сочетания до 01111111, т.е. до 2^(К-1)
С точки зрения количества - верно. А вот подряд перебирать сочетания не получится.

Самый лучший способ проверить - это сделать все сочетания для 3-х (001, 010, 100), 4-х и 5-ти чисел (объектов).
27 сен 18, 20:44    [21688534]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
У вас - пробелы в дискретной математике.
Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf
Перестановки, сочетания, размещения. Это разные понятия.
В ферзевой задаче я использовал перестановки ладей.
Я применил статью
https://ru.wikipedia.org/wiki/Сочетание

Мы с Вами говорим о разных задачах:
- Вы говорите о перестановке ладей (ферзей);
- я говорю о сочетаниях по работе с разными элементами задачи(с какими элементами должны работать в настоящий момент). Это не обязательно ферзи. Это могут быть двойки, тройки, четверки, пятерки и т.д. ферзей.

Поэтому я применяю термин сочетания.

Вы написали.
Gennadiy Usov
Как известно, количество сочетаний из К чисел равно 2^К.

Это - некорректно. 2^K - не имеет никакого отношения к термину сочетания.

Я вас поправил.
27 сен 18, 20:44    [21688535]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Используя опыт построения сочетаний для 2, 3, 4, 5 объектов в количестве одного из пары,
можно сделать следующую программу:
// K – количество чисел (объектов).
var P = new Array(K+1);
var i1;  

for(var i = 1; i <= K; i++) P[i]=0;

var K1 = K-3;
for(var p1 = 0; p1<= K1; i++) {
               If (p1 > 0) {
                           I1=1;
                      D:
                           P[i1]=P[i1]+1;
                           If (P[i1] == 2) {
                                              P[i1] = 0;
                                              i1=i1+1;
                                              go to D;
                           }
              }

              for(var i2 = (i1+1); i2<= K; i++) {
                           P[i2]=1:

                         // получаем сочетание P[K] (либо 0, либо 1)

                           P[i2] = 0;
              }
} 
В данном виде программа позволяет получить массив сочетаний, так как все сочетаний формируются в цикле (и не в одном).
Поскольку сочетаний может быть очень много, то целесообразно сделать эту программу в виде процедуры, чтобы «вытаскивать» только одно очередное сочетание, по порядку.
28 сен 18, 07:31    [21688676]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В предыдущем сообщении 21688676 операторы:
var K1 = K-3;
for(var p1 = 0; p1<= K1; i++) {
нужно заменить на операторы:
var K1 = 2^(K-3)-1;
for(var p1 = 0; p1<= K1; i++) {
28 сен 18, 13:04    [21689019]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
И ещё заменить операторы
for(var p1 = 0; p1<= K1; i++) {
            .....
              for(var i2 = (i1+1); i2<= K; i++) {
на операторы
for(var p1 = 0; p1<= K1; р1++) {
            .....
              for(var i2 = (i1+1); i2<= K; i2++) { 
28 сен 18, 13:10    [21689027]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Кстати, можно немного упростить программу 21688676 с учетом последующих изменений с целью определения всех сочетаний:

// K – количество чисел (объектов).
var P = new Array(K+1);
var i1;  

for(var i = 1; i <= K; i++) P[i]=0;

var K1 = 2^K-1;
for(var p1 = 1; p1<= K1; p1++) {
                           i1=1;
                      D:
                           P[i1]=P[i1]+1;
                           if (P[i1] == 2) {
                                              P[i1] = 0;
                                              i1=i1+1;
                                              go to D;
                           }

                         // получаем сочетание P[K] (либо 0, либо 1)
} 
28 сен 18, 13:18    [21689031]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov, не совсем понимаю что должно получиться. Можно пример для K = 3 ?
28 сен 18, 13:40    [21689052]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov,

JavaScript не умеет возводить в степень так как вы описали.

С одной стороны похвально что вы пытаетесь помочь. С другой стороны это выглядит как медвежья услуга.

И помогли и запутали.
28 сен 18, 13:55    [21689073]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov, не совсем понимаю что должно получиться. Можно пример для K = 3 ?
Вы задали вопрос, а я нашел ошибку: при р1=0 не определен i1. Поэтому вместо:
for(var p1 = 0; p1<= K1; p1++) {
               if (p1 > 0) {
будут операторы:
for(var p1 = 0; p1<= K1; p1++) {
               i1=0;
               if (p1 > 0) { 
При К = 3 должно получиться 100, 010, 001.
28 сен 18, 15:00    [21689150]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
При К = 3 должно получиться 100, 010, 001.

А при К = 4 добавится 1000, 0100, 0010, 0001. Так ?

Если так то это К вариантов, а не 2^(K-1)

И показанное это степени двойки, если рассматривать эти числа как двоичные, т.е.
2^0 = 0b0001 = 1
2^1 = 0b0010 = 2
2^2 = 0b0100 = 4
2^3 = 0b1000 = 8
28 сен 18, 15:13    [21689173]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov,
JavaScript не умеет возводить в степень так как вы описали.
С одной стороны похвально что вы пытаетесь помочь. С другой стороны это выглядит как медвежья услуга.
И помогли и запутали.
Тогда по другому:
var K1=1;
for(var i = 1; i <= (K-3); i++) K1=K1*2;
К1=К1-1;
28 сен 18, 15:14    [21689174]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
При К = 3 должно получиться 100, 010, 001.
А при К = 4 добавится 1000, 0100, 0010, 0001. Так ?
Если так то это К вариантов, а не 2^(K-1)
И показанное это степени двойки, если рассматривать эти числа как двоичные, т.е.
2^0 = 0b0001 = 1
2^1 = 0b0010 = 2
2^2 = 0b0100 = 4
2^3 = 0b1000 = 8
А здесь сочетания для К=4
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1
28 сен 18, 18:09    [21689414]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Gennadiy Usov
[/src]
А здесь сочетания для К=4
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1
[/quot]Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.
29 сен 18, 06:04    [21689720]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Это текст, подготовленный в таблице EXCEL.

Постарался большую часть определения сочетаний "запрятать" в процедуру.
// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}					
					
процедура SOCHET(K, P, p1, i2)  {					
	var i1;  				
	P[i2] = 0;				
	if (i2 < K) go to D1;				
	p1 = p1 + 1;				
	i1=0;				
	if (p1 > 0) {				
		i1=1;			
	D:				
		P[i1]=P[i1]+1;			
		if (P[i1] == 2) {			
			P[i1] = 0;		
			i1=i1+1;		
			go to D;		
		}			
	}				
	i2 = i1;				
D1:					
	i2=i2+1;				
	P[i2]=1;				
					
 // получаем сочетание P[K]					
} 
29 сен 18, 09:44    [21689747]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Поторопился.

Конечно, не процедура, а function.
29 сен 18, 09:47    [21689748]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov,

Зачем тебе goto D1 ?
29 сен 18, 09:56    [21689753]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
А здесь сочетания для К=4
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1
Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.

Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?
29 сен 18, 10:55    [21689765]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
А здесь сочетания для К=4
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1
Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.
Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?
По условиям задачи пара сочетаний те, которые в сумме составляют сочетание 1111 (для К=4). А у нас уже есть для 0111 пара 1000(№ 4).

Поэтому выбирается одно сочетание из пары, т.е. 1000.
29 сен 18, 13:16    [21689836]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov,
Зачем тебе goto D1 ?
В процедуре ищутся две части сочетаний: левая и правая.
р1 отвечает за левую часть, а i2 отвечает за правую часть.
Массив Р - это шаблон сочетаний. D1 нужно для того, чтобы "проскочить" часть операций и поменять одну цифру в шаблоне для нового сочетания.

Далее, при К=3,4 или 5 получаются следующие сочетаний:
для К=3				для К=4					для К=5						
1	0	0		1	0	0	0		1	0	0	0	0		
0	1	0		0	1	0	0		0	1	0	0	0		
0	0	1		0	0	1	0		0	0	1	0	0		
				0	0	0	1		0	0	0	1	0		
				1	1	0	0		0	0	0	0	1		
				1	0	1	0		1	1	0	0	0		
				1	0	0	1		1	0	1	0	0		
									1	0	0	1	0		
									1	0	0	0	1		
									0	1	1	0	0		
									0	1	0	1	0		
									0	1	0	0	1		
									1	1	1	0	0		
									1	1	0	1	0		
									1	1	0	0	1	
29 сен 18, 13:28    [21689842]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov,

Да я не это имел в виду. Его можно заменить на if.

Второй goto скорее всего тоже.
29 сен 18, 15:45    [21689888]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.
По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
29 сен 18, 16:02    [21689894]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
Gennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.
По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.

Тоесть ты не видишь возможности сделать замену?
29 сен 18, 17:06    [21689914]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov
По-моему, у этих операторов разные функции.
if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
Тоесть ты не видишь возможности сделать замену?
Пока нет.
29 сен 18, 17:13    [21689918]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...
Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?
По условиям задачи пара сочетаний те, которые в сумме составляют сочетание 1111 (для К=4). А у нас уже есть для 0111 пара 1000(№ 4).

Поэтому выбирается одно сочетание из пары, т.е. 1000.

Ясно, тогда лишние 1000 и 1001, меняем их на 0111 и 0110.
В итоге получаем
ДвоичноеДесятичное
00011
00102
00113
01004
01015
01106
01117

Программно цикл такой
var max = 2^(K-1);
for(var i = 1; i < max; i++) {вывод i в двоичном виде}

или такой
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}


PS на это я и намекал 21688530
29 сен 18, 17:36    [21689923]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T,
Согласен, это есть другое решение задачи.

Если сравнивать эти два варианта решения задачи, то получаем:
1)- в Вашем варианте 3 сочетания по 1, 3 сочетания по 2, 1 сочетание по 3. Всего 12.
- в моём варианте 3 сочетания по 1, 4 сочетания по 2. Всего 11.
Следовательно, в дальнейшем применении процедуры надо будет обрабатывать на 1 объект больше. А это время.

2) - в Вашем варианте идет поиск max = 2^(K-1) чисел
- в моём варианте идет поиск max = 2^(K-3) чисел, а чтобы получить из этих чисел числа max = 2^(K-1) надо будет изменить только один 0 на 1 в массиве Р.

То есть, мой вариант более трудоёмкий по написанию программы, но, наверное, более быстрый(?). Трудно сравнивать битовое представление (а потом развертка на отдельные 0 и 1) и обычное представление.

Кроме того, массив Р может быть намного длиннее, чем i в двоичном виде.
29 сен 18, 18:23    [21689938]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T,
Согласен, это есть другое решение задачи.

Если сравнивать эти два варианта решения задачи, то получаем:
1)- в Вашем варианте 3 сочетания по 1, 3 сочетания по 2, 1 сочетание по 3. Всего 12.
- в моём варианте 3 сочетания по 1, 4 сочетания по 2. Всего 11.
Следовательно, в дальнейшем применении процедуры надо будет обрабатывать на 1 объект больше. А это время.

Твой сложный цикл это тоже лишнее время.

Gennadiy Usov
2) - в Вашем варианте идет поиск max = 2^(K-1) чисел
- в моём варианте идет поиск max = 2^(K-3) чисел, а чтобы получить из этих чисел числа max = 2^(K-1) надо будет изменить только один 0 на 1 в массиве Р.

Это за пределами постановки задачи. Выше было сказано что 1000 и 0111 равнозначны и можно взять любое из двух, а сейчас выясняется что одна единица лучше чем три. На сколько лучше?

Откуда появилось max = 2^(K-3) ?
Gennadiy Usov
Трудно сравнивать битовое представление (а потом развертка на отдельные 0 и 1) и обычное представление.

Открою тайну: все целые числа хранятся в двоичном виде. Компьютер так устроен что знает только нули и единицы. Десятичные цифры десятичны только в исходном коде, чтобы человеку было удобно читать, а во время исполнения программы используются их двоичные представления.

Gennadiy Usov
Кроме того, массив Р может быть намного длиннее, чем i в двоичном виде.

Почему?
29 сен 18, 20:06    [21690037]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
пропущено...
Тоесть ты не видишь возможности сделать замену?
Пока нет.


Посмотри. Второй goto можно попробовать заменить на цикл.

// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}					
					
процедура SOCHET(K, P, p1, i2)  {					
	var i1;  				
	P[i2] = 0;				
	if (i2 < K) {				
	   p1 = p1 + 1;				
	   i1=0;				
	   if (p1 <= 0) {				
		   i1=1;			
	   D:				
		   P[i1]=P[i1]+1;			
		   if (P[i1] == 2) {			
			   P[i1] = 0;		
			   i1=i1+1;		
			   go to D;		
		   }			
	   }
	   i2 = i1;				
        }				
	i2=i2+1;				
	P[i2]=1;				
					
 // получаем сочетание P[K]					
} 
29 сен 18, 20:28    [21690051]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Посмотри. Второй goto можно попробовать заменить на цикл.
В моём варианте - надо обойти операторы до D1, а в Вашем - эти операторы выполняются.

Тогда уж лучше
if (i2 == K) {
30 сен 18, 06:20    [21690212]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Откуда появилось max = 2^(K-3) ?
Из программы (значение К1):
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}
Ещё раз посмотрите на картинку 21689842: справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3
					
1	0	0		
0	1	0		
0	0	1	
30 сен 18, 06:29    [21690213]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Кроме того, массив Р может быть намного длиннее, чем i в двоичном виде.
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
30 сен 18, 06:35    [21690215]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
И ещё один момент:
Dima T
Программно цикл такой
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}
Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.
30 сен 18, 07:36    [21690216]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3

Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.

Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
30 сен 18, 14:23    [21690381]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).

Любое число. Процессор оперирует 32 и 64 битными словами, но никто не мешает взять массив слов и логически рассматривать его как одно число. Операции сравнения (больше, меньше, равно) сделать элементарно для этого числа.
Максимальный размер массива зависит от количества имеющейся памяти и размера элемента массива. Для простоты считай что возможен массив из 100 млн. элементов.

В принципе без разницы как представлено число: массив слов (двоичное представление) или просто массив где один элемент один бит. Второй способ просто займет больше памяти и медленнее будет обратываться.
30 сен 18, 14:36    [21690385]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3
Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.
Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
Не совсем так.

В сообщении21689842хорошо видны эти "лесенки".
Если идти сверху картинки К=5, то видно, что:
- сначала "лесенка" 5х5 - 5 сочетаний
- далее для 1 "лесенка" 4х4 - 4 сочетания
- далее для 01 "лесенка" 3х3 - 3 сочетания
- далее для 11 "лесенка" 3х3 - 3 сочетания. Итого 15 сочетаний.
А слева в каждом из этих сочетаний сформированы числа от 00 до 11.(К-3 = 2)
30 сен 18, 14:40    [21690386]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
И ещё один момент:
Dima T
Программно цикл такой
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}
Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.

Деление на 2 не требует деления в двоичной системе. Это сдвиг. Ты же не делишь на 10 в десятичной, а просто сдвигаешь запятую.

Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}


Думаю тебе будет интересно почитать что такое битовые операции и булева алгебра. Если по-простому - это набор операций для двоичной системы счисления.
30 сен 18, 14:57    [21690391]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...
Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.
Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
Не совсем так.

В сообщении21689842хорошо видны эти "лесенки".
Если идти сверху картинки К=5, то видно, что:
- сначала "лесенка" 5х5 - 5 сочетаний
- далее для 1 "лесенка" 4х4 - 4 сочетания
- далее для 01 "лесенка" 3х3 - 3 сочетания
- далее для 11 "лесенка" 3х3 - 3 сочетания. Итого 15 сочетаний.
А слева в каждом из этих сочетаний сформированы числа от 00 до 11.(К-3 = 2)

Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
30 сен 18, 15:03    [21690392]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
Имеется несколько последовательностей чисел: 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 х К.
Вот и все.

Давайте опишем задачу в форате контестера.

Test1

Input:
Numbers:1,2,3
Exclude:1,2


Output:
Empty


Test2

Input:
Numbers:1,2,3,4,5,6
Exclude:1,2;2,4;3,5;4,6


Output:
Empty


Верно?
30 сен 18, 15:07    [21690394]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
Процедура21689747, которая определяет сочетания "один из пары", уже включена в один из алгоритмов21690219.

А красота в том, что в одном сочетании включены элементы двух других сочетаний. Жалко, что Вы не поняли.
30 сен 18, 18:48    [21690483]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Должно быть так:
Test1
Input:
Numbers:1,2,3
Exclude:1,2;2,3

На самом деле, легко проглядывается зависимость второй строчки от первой строчки в виде формулы.
Пока я эту формулу ещё не вывел.
30 сен 18, 18:52    [21690484]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov,

А вывод какой?
30 сен 18, 18:57    [21690489]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Если я правильно понял, value & mask определяет значение (0 или 1) бита, определенного маской? А mask - позиция бита - 1, остальные 0?

А while(mask != 0) означает, что сдвиг маски будет больше К (1 выйдет за границу К)?
30 сен 18, 19:07    [21690495]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov,
А вывод какой?
Просто в одном из алгоритмов можно переставлять 3 (6, 9, ...., в зависимости от размера доски) вертикалей. Но если эти вертикали переставлять одновременно (те же сочетания), то появляется несовместимость некоторых вертикалей на одновременную перестановку.
30 сен 18, 19:12    [21690501]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
Слабо понял о чем речь. Меня другой вопрос интересует: в чем польза от этой красоты? Как это связано с расстановкой ферзей?
Процедура21689747, которая определяет сочетания "один из пары", уже включена в один из алгоритмов21690219.

А красота в том, что в одном сочетании включены элементы двух других сочетаний. Жалко, что Вы не поняли.

Алгоритм где-нибудь простыми словами описан? Заниматься реверс-инженерингом непонятного кода нет ни какого желания.

+ PS напомнило анекдот
Всплывает на дальнем востоке подводная лодка, американская.
На берегу сидит чукча.
Капитан подлодки спрашивает: - Как проплыть к Берингову проливу, а то у
нас приборы сломались?
Чукча отвечает: - Курс Зюйд-Зюйд-Вест.
Tanks, сказал капитан подлодки, и она погрузилась в море.
Через один час всплывает Русская подлодка.
Русский (Р) Капитан подлодки спрашивает чукчу (Ч):.
Р. - Ты не видел тут американскую подлодку?
Ч. Видел.
Р. Куда она поплыла?
Ч. Курс Зюйд-Зюйд-Вест.
Р. Ты не умничай, пальцем покажи.
30 сен 18, 19:39    [21690512]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Если я правильно понял, value & mask определяет значение (0 или 1) бита, определенного маской? А mask - позиция бита - 1, остальные 0?

А while(mask != 0) означает, что сдвиг маски будет больше К (1 выйдет за границу К)?

mask это 1 и К ноликов. После каждого сдвига на один нолик меньше. В итоге 1 уйдет и mask == 0
value & mask дает либо ноль либо mask если в этом разряде у value стоит 1.
30 сен 18, 19:42    [21690515]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Алгоритм где-нибудь простыми словами описан? Заниматься реверс-инженерингом непонятного кода нет ни какого желания.
Так Вы уже его читали. 21690386плюс картинка21689842

Так что не понятно?
30 сен 18, 19:52    [21690520]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
Gennadiy Usov,
А вывод какой?
Просто в одном из алгоритмов можно переставлять 3 (6, 9, ...., в зависимости от размера доски) вертикалей. Но если эти вертикали переставлять одновременно (те же сочетания), то появляется несовместимость некоторых вертикалей на одновременную перестановку.

Я вообще не это спрашивал.

Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.

То что функция должна выдать на выход.
30 сен 18, 19:55    [21690521]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Я вообще не это спрашивал.
Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.
То что функция должна выдать на выход.
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.
30 сен 18, 20:02    [21690524]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?
Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
Любое число. Процессор оперирует 32 и 64 битными словами, но никто не мешает взять массив слов и логически рассматривать его как одно число. Операции сравнения (больше, меньше, равно) сделать элементарно для этого числа.
Максимальный размер массива зависит от количества имеющейся памяти и размера элемента массива. Для простоты считай что возможен массив из 100 млн. элементов.

В принципе без разницы как представлено число: массив слов (двоичное представление) или просто массив где один элемент один бит. Второй способ просто займет больше памяти и медленнее будет обратываться.
Хорошо.

Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.
30 сен 18, 20:06    [21690525]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Хорошо.

Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.

Ничего хорошего. Я не понимаю почему 249 а не 997? В задаче на доску N*N надо выставить N ферзей.
Непонятно на основании чего сделано упрощение. С другой стороны если упрощено до каких-то "квадратов ферзей", то это уже отдельная фигура со своим поведением.
В общем я догадываюсь что выведены какие-то дополнительные правила, но эти правила нигде не озвучены. Про них и спрашиваю.
30 сен 18, 20:19    [21690536]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Хорошо.
Пример: доска 997х997, 249 квадратов ферзей. Как представить сочетания из 249 объектов? В битах, в массиве слов и т.д.
Ничего хорошего. Я не понимаю почему 249 а не 997? В задаче на доску N*N надо выставить N ферзей.
Непонятно на основании чего сделано упрощение. С другой стороны если упрощено до каких-то "квадратов ферзей", то это уже отдельная фигура со своим поведением.
В общем я догадываюсь что выведены какие-то дополнительные правила, но эти правила нигде не озвучены. Про них и спрашиваю.
Здесь ещё больше объяснять.
Процедура, которая определяет квадраты ферзей, 21690219.
Но мы говорим не о ферзях, а о сочетаниях объектов. Объектов 249. Как быть с представлением сочетаний?
30 сен 18, 20:24    [21690542]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
Я вообще не это спрашивал.
Если на вход этой волшебной функции подать цифры и ограничители которые я привёл.
То что функция должна выдать на выход.
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.

Я хотел узнать конкретное число(числа) для 123
30 сен 18, 20:37    [21690550]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov
пропущено...
Если на входе 3(6,9,...) цифр и есть ограничения, то на выходе должны быть сочетания этих цифр, которые не противоречат ограничениям.

Я хотел узнать конкретное число(числа) для 123
100, 010, 001, 101
30 сен 18, 20:52    [21690561]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
пропущено...

Я хотел узнать конкретное число(числа) для 123
100, 010, 001, 101

Аха...

Тоесть будет так:

Input:
Numbers:1,2,3
Exclude:1,2;2,3

Output:
1,
2,
3,
13


Верно?
30 сен 18, 21:41    [21690584]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
1 окт 18, 01:07    [21690657]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Как-то так.

object Main {

  def parseArgNumbers(argNumbers: String): List[Int] = argNumbers.split(",").map(s => s.toInt).toList

  def parseTuple(s : String) : (Int,Int) = {
    val sp = s.indexOf(",")
    (s.substring(0, sp).toInt, s.substring(sp + 1).toInt)
  }

  def parseExclude(argExclude: String): List[(Int,Int)] = argExclude.split(";").map(s => parseTuple(s)).toList

  def containsTuple(subNumbers: List[Int], pair: (Int, Int)): Boolean = {
    subNumbers.contains(pair._1) && subNumbers.contains(pair._2)
  }

  def contains(subNumbers: List[Int], excluded: List[(Int, Int)]): Boolean = {
    //for(pair <- excluded) {
    //  if (containsTuple(subNumbers,pair)) return true
    //}
    //false
    // TODO: I hope, breaking after 1st element of lazy collection will make perfomance
    return excluded.filter(pair => containsTuple(subNumbers,pair)).take(1).size == 1
  }

  def trickyCombinations(numbers: List[Int], excludes: List[(Int, Int)]): Unit = {
    val size = numbers.size
    for(i <- 1 to size) {
      printf(s"The combinations $i of $size\n")
      numbers.combinations(i).foreach(f => {
        if (!contains(f,excludes)) {
          for (v <- f) printf("%s,", v)
          printf("\n")
        }
      })
      printf("\n\n")
    }

  }

  def main(args : Array[String]) : Unit = {

    printf("\nNumbers : ")
    val argNumbers = "1,2,3,4,5" //scala.io.StdIn.readLine()

    printf("\nExclude : ")
    val argExclude = "1,2;2,3"   //scala.io.StdIn.readLine()

    println()

    val numbers = parseArgNumbers(argNumbers)
    val excludes = parseExclude(argExclude)

    trickyCombinations(numbers,excludes)

  }

}
1 окт 18, 01:41    [21690660]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Output
+
The combinations 1 of 5
1,
2,
3,
4,
5,


The combinations 2 of 5
1,3,
1,4,
1,5,
2,4,
2,5,
3,4,
3,5,
4,5,


The combinations 3 of 5
1,3,4,
1,3,5,
1,4,5,
2,4,5,
3,4,5,


The combinations 4 of 5
1,3,4,5,


The combinations 5 of 5
1 окт 18, 01:42    [21690661]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
В сообщении я попробовал составлять сочетания (второго уровня) из двух сочетаний (первого уровня). В данном случае одно из сочетаний первого уровня - "линейка". А Dima T меня не понял.

Ранее я рассматривал задачу 123, 123456, и т.д. 2130207621482003. Попробую ещё раз объяснить мой метод решения этой задачи.
В данной задаче интересно рассмотреть задачу объединения в одном сочетании 3-х сочетаний. Рассмотрим.
Все объекты, которые участвуют в данной задаче, кратны 3: 3,6,9,12,….
Следовательно, в каждом случае можно разделить конкретную задачу на 3 участка:
-для 3-х объектов: 1, 2, 3
-для 6-и объектов; 12, 34, 56
- для 9-и объектов: 123, 456, 789. и т.д.
Можно выбирать сочетания для 1-го и 3-го участка и составлять объединенное сочетание (средний участок пока нули).
Если теперь добавлять средний участок, то сравниваются на наличие 1 одинаковые колонки по номеру в 3-х участках. Если совпадают, то данное сочетание из среднего участка пропускается.
Пока так на пальцах.
1 окт 18, 07:17    [21690701]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
mayton
Хм.. мне вот не нравится ограничение в исключение пар. А если надо будет исключать тройки? Четверки?
В сообщении я попробовал составлять сочетания (второго уровня) из двух сочетаний (первого уровня). В данном случае одно из сочетаний первого уровня - "линейка". А Dima T меня не понял.

Я не понимаю что такое "уровни". Объясни. Ты не забывай что здесь - айтишники. Не математики.
Нам сложно искать смыслы в художественных словах и эпитетах.

Лучший вариант донести алгоритм - это привести код который всем понятен. И подкрепить
примером в формате Input/Output как я писал выше.
1 окт 18, 10:21    [21690799]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
Dima T
пропущено...
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;

Возможно отвечали. Я просто добавлю.

Не надо ставить так вопрос.

Любое число можно представить на которое хватит памяти. Но это не означает
что вы с этим мега-числом сможете эффективно работать.

Программирование - это постоянная инженерия возможностей
- CPU (регистры)/Memory
- Язык и компиллятор и типы данных
- Библиотеки

Мы всегда ищем компромиссы. Как бы сделать задачу. На базовых регистрах CPU (32/64).
На расширенных. На языковых типах данных. На библиотеках.

Поэтому не бывает такого вопроса. От задачи надо идти.
1 окт 18, 10:36    [21690807]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).

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

Сравнение двух сверх-больших чисел - это задача класса линейной вычислительной сложности. Тоесть чем длиннее числа
тем медленнее они будут сравниваться.
1 окт 18, 10:40    [21690811]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Тогда можно будет определить все сочетания для К объектов.Так?
// K – количество чисел (объектов).				
var P = new Array(K+1);				
// количество сочетаний				
var K1=1;				
for(var i = 1; i <=K; i++) K1=K1*2;				
K1=K1-1;				
// поиск всех сочетаний для К объектов				
for(var i = 0; i <= K1; i++) {				
	for(var i = 1; i <= K; i++) P[i]=0;			
	sochet_new(i);			
}				
				
				
function sochet_new(i) {				
	var i1=0;			
	mask = 1 << i;			
	while(mask != 0) {			
		i1=i1+1;		
		P[i1]=value & mask;		
	}			
	mask = mask >> 1;			
}				
Есть одно сомнение: для число 1 в массиве Р "1" находится в начале массива или в конце?
5 окт 18, 19:47    [21696770]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Что-то я намудрил в предыдущем сообщении. Теперь кажется верно:
// K – количество чисел (объектов).					
var P = new Array(K+1);					
// количество сочетаний					
var K1=1;					
for(var k = 1; k <=K; k++) K1=K1*2;					
K1=K1-1;					
var dlina1=1;					
var dlina2=1;					
// поиск всех сочетаний для К объектов					
for(var k1 = 0; k1 <= K1; k1++) {					
	for(var k = 1; k <= K; k++) P[k]=0;				
	if (k1>dlina1) {				
		dlina1=dlina1*2;			
		dlina2=dlina2+1;			
	}				
	sochet_new(k1, dlina2);
	// печать сочетания P[K]			
}					
					
					
function sochet_new(value, dlina2) {					
	var i1=0;				
	mask = 1 << dlina2;				
	while(mask != 0) {				
		i1=i1+1;			
		P[i1]=value & mask;			
	}				
	mask = mask >> 1;				
}
6 окт 18, 13:40    [21696995]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Что-то я намудрил в предыдущем сообщении. Теперь кажется верно:

Тут тоже намудрил, это надо внутрь цикла, иначе он будет бесконечный
	mask = mask >> 1;				


И это под вопросом:
		P[i1]=value & mask;			

value & mask дает или 0, или mask, выше ты 0 и 1 использовал, не знаю важно ли это для твоей задачи.
7 окт 18, 16:33    [21697391]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Тут тоже намудрил, это надо внутрь цикла, иначе он будет бесконечный
	mask = mask >> 1;	
И это под вопросом:
		P[i1]=value & mask;	
value & mask дает или 0, или mask, выше ты 0 и 1 использовал, не знаю важно ли это для твоей задачи.
Спасибо! Понял. Теперь так?
function sochet_new(value, dlina2) {					
	var i1=0;				
	mask = 1 << dlina2;				
	while(mask != 0) {				
		i1=i1+1;			
		if((value & mask) == 0) {			
			P[i1]=0;		
		} else {			
			P[i1]=1;		
		}			
		mask = mask >> 1;			
	}				
}
7 окт 18, 16:55    [21697400]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщениях 21696995 и 21697400представлена программа по поиску всех сочетаний К чисел.
Однако, если величина К окажется слишком большой, например, 200, 250, то в программе появляются большие числа: 2^200, 2^250, что приводит к необходимости вводить дополнительные программы для работы с такими большими числами.

В сообщениях 21697951 и 21698205 высказана мысль о переходе в программах, где есть большие числа, на другие числа, например, на величину степени 2 таких чисел.

Однако выше указанная программа, которая основывается на программе21690391, предполагает разложение чисел вида 2^200 на отдельные биты, что не позволяет избавиться от больших чисел.

Поэтому попробуем представить другую программу поиска сочетаний без использования больших чисел.
8 окт 18, 16:11    [21698295]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
А в этой программе не требуется использовать большие числа:
// K – количество чисел (объектов).				
var P = new Array(K+2);				
for(var i = 1; i <= K+1; i++) P[i]=0;				
				
while (P[К+1]< 1) {				
	SOCHET3(K, P);			
	// печать сочетания			
	for(var i = 1; i <= K; i++) print(P[i]);			
}				
				
function SOCHET3(K, P)  {				
	var i1;  			
	i1=1;			
D:				
	P[i1]=P[i1]+1;			
	if (P[i1] == 2) {			
		P[i1] = 0;		
		i1=i1+1;		
		go to D;		
	}			
 // получаем сочетание P[K]				
} 
Так что, получаем все сочетания. Где-то помогла картинка 21281836
8 окт 18, 20:42    [21698634]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov,

Так и не смог избавится от go to?
8 окт 18, 20:48    [21698636]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
mayton
Gennadiy Usov,

Так и не смог избавится от go to?

mayton, он только учится программировать, пока хоть так, потом почитает правила хорошего тона.
8 окт 18, 21:03    [21698644]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov,

Так и не смог избавится от go to?
Пока не вижу альтернативы
8 окт 18, 21:10    [21698649]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
mayton
Gennadiy Usov,

Так и не смог избавится от go to?
Пока не вижу альтернативы

Альтернатива это цикл и break
function SOCHET3(K, P)  {				
	var i1;  			
	i1=1;			
	while(true) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
		i1=i1+1;		
	}
}

Но в этом коде есть ошибка: i1 может выйти за пределы размера массива P[], поэтому лучше так
function SOCHET3(K, P)  {				
	for(var i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
}
9 окт 18, 07:54    [21698841]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Спасибо за 2 варианта программ!
Dima T
Но в этом коде есть ошибка: i1 может выйти за пределы размера массива P[], поэтому лучше так
function SOCHET3(K, P)  {				
	for(var i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
}
Данный вариант очень интересен с точки зрения упрощения программы.

Однако, все сочетания определяются в некотором цикле от 1 до ..... Процедура SOCHET3 будет в этом цикле.
Последним сочетанием должно быть 1111111111 и т.д. А цикл будет работать дальше.

Поэтому необходимо ввести ячейку P[К+1]. И пусть i1 выходит за пределы размера массива P[К], где мы 1 отловим в ячейке P[К+1].

Поэтому мне очень понравился 1-ый вариант. Никогда не работал со значениями true, поэтому спасибо за учение. Кстати, true можно применить и в оболочке над SOCHET3
			
// K – количество чисел (объектов).			
var P = new Array(K+2);			
for(var i = 1; i <= K+1; i++) P[i]=0;			
			
while(true) {			
	SOCHET3(K, P);		
	if (P[К+1]==1) break; // Выход из цикла по сочетаниям		
	// применение сочетаний
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			
			
function SOCHET3(K, P)  {			
	var i1;  		
	i1=1;		
	while(true) {		
		P[i1]=P[i1]+1;	
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2	
		P[i1] = 0;	
		i1=i1+1;	
	}		
}
9 окт 18, 15:00    [21699362]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Однако, все сочетания определяются в некотором цикле от 1 до ..... Процедура SOCHET3 будет в этом цикле.
Последним сочетанием должно быть 1111111111 и т.д. А цикл будет работать дальше.

Поэтому необходимо ввести ячейку P[К+1]. И пусть i1 выходит за пределы размера массива P[К], где мы 1 отловим в ячейке P[К+1]

Вот мы уже плавно подошли к теме обработки ошибок. Отлавливать ошибку в P[К+1] не самый красивый способ.
Лучше выбрать какое-то правило для обработки ошибок и его использовать. Например функция возвращает true в случае успешного выполнения.
В этом случае можно так
function SOCHET3(K, P)  {				
	var i1;
	for(i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
        return i1 <= K;
}


тогда вывод можно будет переписать так
while(SOCHET3(K, P)) {			
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			


PS Советую сделать паузу и прочитать какую-нибудь книгу по основам программирования.
9 окт 18, 15:22    [21699386]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Например функция возвращает true в случае успешного выполнения.
В этом случае можно так
function SOCHET3(K, P)  {				
	var i1;
	for(i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
        return i1 <= K;
}
тогда вывод можно будет переписать так
while(SOCHET3(K, P)) {			
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			

PS Советую сделать паузу и прочитать какую-нибудь книгу по основам программирования.
Пока некогда делать паузу.

Надо подвести некоторую черту.
Что мы имеем:
- вариант программы определения сочетаний для большого числа К21699386 (на основании картинок21281836);
- вариант программы определения сочетаний для небольшого числа К2169677021697400 с использованием идеи21690391.

Кому что нравится.
9 окт 18, 15:54    [21699436]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Что от нас требуется?
9 окт 18, 18:32    [21699600]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Что от нас требуется?
Да ничего
9 окт 18, 19:33    [21699668]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Gennadiy Usov
Надо подвести некоторую черту.
Что мы имеем:
- вариант программы определения сочетаний для большого числа К21699386 (на основании картинок21281836);
- вариант программы определения сочетаний для небольшого числа К2169677021697400 с использованием идеи21690391.
В первом варианте, как правило, перебираются "1" только в части двоичного вида числа, определяющего сочетание.

Во втором варианте маски перебирают все элементы двоичного вида числа, определяющего сочетание.

В первом варианте можно значительно уменьшить количество переборов, если массив P[K] разделим на несколько частей, и "работаем" отдельно с каждой частью.

Например, число К делится на 3. Тогда получаем программу (используем вариант21699436, предложенный Dima T):
// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=K/3;					
P[1] = -1;
P[K1+1] = -1;					
P[2*K1+1] = -1;					
					
var K2=0;					
var K3=2*K1;					
while(SOCHET4(K1, P, K2)) {					
	while(SOCHET4(K1, P, K3)) {				
		while(SOCHET4(K1, P, K1)) {			
			
			// печать сочетания		
			for(var i = 1; i <= K; i++) print(P[i]);		
			}		
		}			
	}				
}					
					
function SOCHET4(K1, P, i2)  {					
	var i1;				
	for(i1 = i2+1; i1 <=i2+K1; i1++) {				
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2			
		P[i1] = 0;			
	}				
	return i1 <= i2+K1;				
}					
12 окт 18, 19:37    [21702893]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В предыдущем сообщении массив P[K] был разделе на 3 равные части , и в каждой его части искались свои сочетания, а потом все эти сочетания совмещались в одно сочетание.

Оказывается, такое разделение (произвольное) можно сделать для любого массива P[K]. Таким образом, можно уйти от больших чисел.

Например, надо найти сочетания для 100 чисел.

Делим массив P[100] на 4 части, например, 15, 35, 27, 23. Тогда, используя результаты сообщения 21702893, получаем программу поиска сочетаний для 100 чисел:
var K=100;							
var P = new Array(K+1);							
for(var i = 1; i <= K; i++) P[i]=0;							
							
var K1=15;							
var K2=35;							
var K3=27;							
var K4=23;							
var Q1=0;							
var Q2= 15;							
var Q3=50;							
var Q4=77;							
P[1] = -1;							
P[15+1] = -1;							
P[50+1] = -1;							
P[77+1] = -1;							
							
while(SOCHET4(K1, P, Q1)) {							
	while(SOCHET4(K2, P, Q2)) {						
		while(SOCHET4(K3, P, Q3)) {					
			while(SOCHET4(K4, P, Q4)) {				
				// печать сочетания			
				for(var i = 1; i <= K; i++) print(P[i]);			
				}			
			}				
		}					
	}						
}	
Правда, первое сочетание будет состоять из одних 0, но пока от этого не удаётся избавиться.
13 окт 18, 12:54    [21703238]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В двух последних сообщениях 21702893 и 21703238 лишняя закрывающая скобка } в головной программе.
13 окт 18, 17:51    [21703339]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Этот кусок кода имеет рекурсивную природу. Убежден что его можно переписать на более компактный вид.

while(SOCHET4(K1, P, Q1)) {							
	while(SOCHET4(K2, P, Q2)) {						
		while(SOCHET4(K3, P, Q3)) {					
			while(SOCHET4(K4, P, Q4)) {				
				// печать сочетания			
				for(var i = 1; i <= K; i++) print(P[i]);			
				}			
			}				
		}					
	}						
}	
13 окт 18, 17:54    [21703341]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Этот кусок кода имеет рекурсивную природу. Убежден что его можно переписать на более компактный вид.
Возможно.

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

Могут быть процедуры, которые будут решать специальные задачи на отдельных участках массива P[K]. Например, сравнение с другими участками.
13 окт 18, 18:56    [21703362]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

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

Можно взять программу 21702893 и добавить к ней процедуру SOCHET5, которая сравнивает значения «1» в 3-х разделах массива P[K].
// K – количество чисел (объектов).						
var P = new Array(K+1);						
for(var i = 1; i <= K; i++) P[i]=0;						
						
var K1=K/3;						
P[K1+1] = -1;						
P[2*K1+1] = -1;						
P[1] = -1;						
						
var K2=0;						
var K3=2*K1						
while(SOCHET4(K1, P, K2)) {						
	while(SOCHET4(K1, P, K3)) {					
		while(SOCHET5(K1, P, K1)) {				
			// печать сочетания			
			for(var i = 1; i <= K; i++) print(P[i]);			
		}				
	}					
}						
						
function SOCHET5(K1, P, i2)  {						
	var i1;					
	for(i1 = i2+1; i1 <=i2+K1; i1++) {					
		P[i1]=P[i1]+1;				
		if(P[i1] == 1)  {				
			if((P[i1 - K1] == 1) || (P[i1 + K1] == 1)) {			
				P[i1]=2;		
				for(var i = i2+1; i <= i1-1; i++) P[i]=0;		
			}			
		}				
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2				
		P[i1] = 0;				
	}					
	return i1 <= i2+K1;					
}						
14 окт 18, 06:50    [21703514]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Обычно цикл WHILE имеет обязывает программиста реализовать следующий паттерн:

<инициализация>
while(<условие цикла>) {
   <тело цикла>
   <итерационное выражение>
}


Если вы опускаете итерационное выражение то рискуете получить бесконечный цикл. Теоретически
это выражение может быть инкапсулировано в функцию условия но в вашем случае - есть сомнения
что это реализовано.
14 окт 18, 16:24    [21703650]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
mayton, 21699386
14 окт 18, 17:01    [21703659]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Dima T, вы тестировали это?
14 окт 18, 17:04    [21703660]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Может оно и работает. ХЗ. Но эти функции с глобальным состоянием. Это ... unsupportable. Зачем так вообще делать?
14 окт 18, 17:25    [21703665]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Может оно и работает. Зачем так вообще делать?
Ранее было сообщение21699436, что имеется 2 варианта программы определения сочетаний. Можно применить вместо процедуры работы с массивом процедуру работу с масками для битовых операторов.

Представьте на минуту, что надо найти сочетания для 200 чисел. Есть такой вариант для одного из алгоритмов для доски 1000х1000.
Ячейка вмещает около 1,1259E+15. Если перевести в двоичные, то это 2^50.
Теперь разбиваем массив P[200] на 4 части по 50, и можно применить какую-нибудь процедуру SOCHET6, в которой вместо работы с массивов применяется работа с масками. А далее 4 цикла, как в 21703238.

И никаких проблем с длинными числами.

Кстати, работа с кусками массива P[K] позволяет, если необходимо, "поплотнее" поработать с одним из участком массива P[K].
14 окт 18, 19:02    [21703686]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
mayton
Dima T, вы тестировали это?

Конкретно это 21699386 обычный двоичный счетчик на K разрядов, вернет false при переполнении.
Проходили на микросхемотехнике, такое не забудешь )))

mayton
Может оно и работает. ХЗ. Но эти функции с глобальным состоянием.

Глобального состояния там нет, состояние в параметрах передается. Написано в процедурном стиле.

mayton
Это ... unsupportable. Зачем так вообще делать?

Тут все unsupportable. Я только небольшой рефакторинг предложил.
14 окт 18, 20:04    [21703702]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
И никаких проблем с длинными числами.


Их и не было.
Была проблема с длинным временем.
15 окт 18, 10:09    [21703884]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
И никаких проблем с длинными числами.
Их и не было.
Была проблема с длинным временем.
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?
15 окт 18, 12:53    [21704055]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
Их и не было.
Была проблема с длинным временем.
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?


Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.

Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
15 окт 18, 13:06    [21704080]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?
Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.
Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.
15 окт 18, 13:14    [21704104]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.
Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.


давно хотел спросить, вы русский язык хорошо понимаете?
15 окт 18, 13:16    [21704109]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.
давно хотел спросить, вы русский язык хорошо понимаете?
Так Вы же не ответили на мой вопрос о работе с большими числами!
15 окт 18, 13:18    [21704112]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov,

вы совсем не допускаете мысль, что могли не заметить ответа в моем сообщении?
15 окт 18, 13:25    [21704127]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov,

вы совсем не допускаете мысль, что могли не заметить ответа в моем сообщении?
Aleksandr Sharahov,

вы совсем не допускаете мысль, что я вам ответил по-русски?
15 окт 18, 13:27    [21704129]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
Gennadiy Usov
Aleksandr Sharahov
пропущено...
давно хотел спросить, вы русский язык хорошо понимаете?
Так Вы же не ответили на мой вопрос о работе с большими числами!

Александр вам не ответил. Потому-что сам по себе вопрос лишен смысла. Современные библиотеки
и типы данных могут поддержать числа любой разрядности. Но пропорционально вы потеряете
память. И потеряете время линейно для операций сложений-вычитаний и квадратично для умножений и т.д.

Современное программирование для науки и техники использует double. Финансовое - числа символьной точности
до 38 двоично-десятичных разрядов. Криптография (теоретически) использует

int64 используется много и плотно для внутреннего представления указателя памяти. И int128 используется
во всех современных файловых системах для внутренних расчетов смещений. Более длинные целые 256/512/1024
и т.д используются в криптографии (и там это обосновано).

То что вы спрашиваете о максимальной длине лишено по большему счету смысла. Это меряние хоботами.
Никто из нас в здравом рассудке не станет применять в программировании сверх-числа "просто-так" или из амбиций.

Нужно исходить из потребностей алгоритма. И поставить вопрос так. Зачем алгоритму оперировать сверх-длинными
целыми числами? Есть ли строгое обоснование? Кроме желания просто посмотреть глазами на это число.
15 окт 18, 13:37    [21704150]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Нужно исходить из потребностей алгоритма. И поставить вопрос так. Зачем алгоритму оперировать сверх-длинными
целыми числами? Есть ли строгое обоснование? Кроме желания просто посмотреть глазами на это число.
В сообщении 21703686 было сказано, зачем это нужно.
Потому что по ходу работы алгоритма, например, на доске 1000х1000, появляются число вида 2^200.

Я попытался от этих чисел уйти за счет разбивки массива P[K].
И тогда я работаю с обычными числами int64 и с масками для них.
mayton
Более длинные целые 256/512/1024
и т.д используются в криптографии (и там это обосновано).
Следовательно, в этих случаях применяются дополнительные специальные программы. Я от этих специальных программ ухожу.
15 окт 18, 13:54    [21704175]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Ы2
Member

Откуда:
Сообщений: 165
Gennadiy Usov, вам же предлагали уже python общего назначения. Поставьте его и вычисляйте:
>>> pow(2,65000) + pow(2,17111)

+
89067273653340927323517259932354619871558825103436606716706453781843763534415748
12965213416152925263199662391673697765933464203777998083007139715736799813496437
41400204028253349032666883642470869082222942916093938419222455091242836462074821
64386026661717449970658566073460848199161736489843799333191713085182395564042704
01690044754449283601331379324615672913823080930697705982904511229994638319021461
33864071358165526567741960022949724630408293146248058570630262301141836262256770
32258735473548356179546623643347470660070077465003021865213363678295064310563824
69828116926061298942974551572328495067058331823937715768276354423445179866769513
40261801005021385997739586579167309674886578472241839175666028486397213554543444
78621060751878086538548783792663360579391258173969792675553045587717825138174049
39607307776166817386953995704957642552250086576077461721086382444742917912705333
50311452759713456483766553934984261335921505205908882625783394059522845613335732
47258654432980174433788543734035435356340698291972143766256342296090163012396905
23800194866611908931741982414736841903119847837392292121374026777918206082606804
95557625044903772085770734006589988799754023366598834387753412461227655109783711
94575396301234163661586829266118998856839620566234920593319020715976524847302996
49374027722927001638604994655408549444337242420021297008165232062378031597698159
50789009708342295148850153146109863114600464670205768777292310897068464032666411
32353677342030535043596409846994934904901607558506049335904644145260092001105446
41247508771880060935268337908562506204502137940847890700956304791886967768256941
15958246890052164501544524798670610404183416497452690110533758878518336716901736
33056179408807650253129677322911032855004278444996823459556036812287454241779365
35925157097794709201443295093205846912242588436062424685730089694907674138222690
79190881923458681564941651072166238865805337579597870991622766098584410686979830
40847869928658821909480547246984023665532994322147639321494854052137535861771902
86034787820685769625092546331786500033667140019657145510823185319879820703974259
94180747511612544083261153007619843991139798395834137110370911543397730547842948
54668811767472300937781014552924092875711797994119548699967617671238995718318966
07467563150574986416188281424361989030799327681785578936910749665233732884889979
05763164171986764062940900337893879680549927049640784247721300782089273533673807
08465769205367003891974379700980598224759128350161036527158969973775119792782542
78501446910692678966792795081662952083790941084161248067923290760481965771567065
62427541897789795298059696747068981572085509334358213526865029578611560073782979
56240239961860449506916198746831054751240446081083680945067162662807671725238542
84171927451592942087371733739482546787054858855421361297392483983220336662068391
21940731101764837946767768579996906231439350738345932011096375389776150743458726
01845472679388741789090961267064309948055231141247399989118203527877879360469279
60050331963308066026244048409828230579941672892681617691052614908440452732604108
54655827091760126969981643925784671342963519076784639829144917127400963479715396
86657612994562388790066789653877896891764216403868468202288868897866505274533790
27852616475784367646768083775045285224386400451812981371206041787628248576165614
48530004155757923612176117703637399832543008356800496813209444643126633041702826
52157415253838184419886932925696407783281010048808372415712357066455838206941412
65741479744842662532346726845792929590467843650848387368813159842971908206923273
86965959316215418940348757470140830081558384825014231955272387857749802880593404
81135416271904854581036735957705021299202376401224766265791088383678307447968442
74704776516578880829922868833072416246076721182016501772831501661690078156609199
13928328369763912880792190745665252269663440094918600826138680628648594626040055
06448211794563004398683897034107000491130632316639348508075973701222558475673142
86975570796543244020261951669720675103134031047228323184496517894110900436633077
05237069400727704898273534649955698623269236847624442952390778102319898528297681
39310244030535071273790197689467112824749747608577335390491416119479041022164339
24302674954916959037370011330076368026832294893054226081642160117178738072050221
58169230109073466433959203906331410530614423653934220474243028250319235963605974
51369889942740596387823370768875334499043125609533137203131629019720428703685775
78582246920427656429113481422857281126067996376355229411874775087710611270172243
73142154554813247935630589790149144191781786110946045115617930131899311847941063
36625911312097408077109837441018785038493991931649911485097720182810300422528781
50161635231733409587069112031597700306994950652774748773072530186135903244796776
81713083143063252906790529671784237623983265559553245758013200875546726365923957
48699185624468917570471918418880913111968183739668561160706347187390510139242812
73403332438611630927599192954827217355603756707895377376769645621098383265139182
90887095667768906227048042951114452332377331376517078314171181532401866207823267
67577017445092763909673688642171325831689463665015698586352406307995326762677815
58122358807535369369867622789042396202560217765223093689977660945132387123435195
46237140498782904232546001389159797252795681535247142650942160320178535864896986
36470655044848899026785662984951983655456105695219038712316669734532260560746214
00351208152742490868793959531792503296871983171301439113160939600293025766571642
53847735734821621276295408995313996131566040968531368126621615897120904209464498
31323272808342730450459510280601189008088302927524285110062762509440828355831999
12430317285478162499743411119186414814294321299331406966415722436419215830653719
70396011178488356801256654675046507600112267489637575902635155838038788338990201
11571767072522273262124753623904483113916916943203350050704349679809633306761229
08254591770388228371064139620742842280867525591571746532373162830017756889317309
75798934075869455274085853540238288368100170343931312858754348140127046118156219
81049749734291702233814719727553125611446883328824658564279388519817460219700229
47910180489666257936404954393715769108847745503473876651607461346445184455903584
84361362900786926648731410523916520949129490089225229806575737309380054375970498
57184019881575545686092910746232839831299803181990818928907766255906029474525397
73402995139594144363324115578905772451138288327493081272556410659794512579513805
98144420159917901110442250978552170982267534015566289317382412669524133472890884
73672949961921834571548775538266806022558021020863404895977831221312390434791428
51871327002513560885817900520507493371837398488449686738468339583556739937827331
22990807447975819059189127325242598912449154492646356245678325970112669209384613
96713743137676565384490902187229200282340988745778560729201634071887010363861281
00230965367267004023625386406751926687410834871075526336185533166572694708950537
15144147777357841015883109890592077923286237686063929700012931794297973774297238
74874349353213079124937260843284484730887882710758296790208436247134454151693596
61777892845483664298746653402888075968734338617048611660503005589293139915504213
48673271962690020175829392987667806365389692446169868493813209119529891886887200
57950451869726849256697373148074991832485637342845160334449767045692121185588967
04972876209480771138133625380875883795712240987288245013430641258558465714141806
31400484639675507546151111041158534195373123026871724182799256086598394209420484
81059407556849889405747142747166579504343087525241236301337290609522155633067944
47773862705570296967246806599345767910343581857807095081077893850041387595268624
66173146763421905001420513588355310197625645233239193759857437461256642187754061
84786374899220809357342976045269983518613864102069383155422921160116295421627130
76886749595210229531974682974270114338596977741419432730164764323621185123535228
70310167976682755194199930133594146362057897037548135004758558616013646987761011
00293280874338021025935613833372059699953081078310642472307386735459620193638500
91339162979872156450512056634785573000397230081096155444389372865419362014782682
90961055917641474496178584323297510777268561520435736033227098192607479791435258
75557749875371212079212676055874722035927259808363977277901606301382651307426995
07765222044061755452477599161541090629102448111932547366018855779639456037183359
16237963421242210510401012251339289865804301188367529308079990113873677336324038
22648932724164724842236314846341271955076525872507025460051134319927963739684002
66248227943691455569932906486747433446083954873606888044622282845277332135490045
70968548735248691390876092140574278724234732013494768055065135972371282728589084
52798394055624162923904240570904109322356389702015125413026055638586225117218819
85475572431616045403642523569599508322199738440364801763358437135258799602280800
49121546749085361448512038450131595329001210933843405155385063559165274548128791
32208362532512397370123090130729768379648549545284328637051975955642502836202545
43897147542836432566463420933666052999797220740743325439324829527217451647774447
58286171480711534460593642805113577888571344441130482323490927143258719687957020
89892299478432227347771678296075525232978125260914465976505818522314570463843100
85825974903495443254945321601202252686408754402845811239346008695239924251066807
37338676423907949964903698326766349931651024680814884606877909766628435785851667
39232904995526401471780939803980972351866302665794990864633178219348377722026536
62222029278155812315450660632749824140342533858222851806007041131279050042187621
58090964574129002466866083780264490500100715220566026842013397416346791530749080
97127062686005432613527952078360261507300644327192841283212305483877973455199029
53421260769632629011818963024675066865306592263508899486520900450483942996706878
52041504831481771620866399100507314828740006042473048017664928764707237328009100
90768454381373294239715981532551983197858030532812689916782278373782363603482561
76294360261928219233766950700693709851040566528370565345893357084790242778372745
37010385936942745594007489473032800444675727133491752710935711981535105618870991
40013963086945664959965974479753987622073758864338537118121223172013747286684495
48911170564037623287135734034213563171313190143638197150334495747655610296018316
32458263092678850557961269415916692420994993913082254801575567155637837301716321
13375935284566564922674462078594470214267787821486526795266547672458881357121504
92712567684990946302091972721710171734716771881715251789342552434856815150721002
94401908303026408636596125509071237145563688026808919488871887761347096629835957
32625766323119725658560193829678086016282442053810808134248134113243415424846240
31032439879763035628990707298906760378846959710939162159046209362907204893563649
19045360729717220287976899650190914008604185200179172521007300206067137783819950
74625621023613214360849487773008922100730616930805949257092738761488395078594503
47500627558679290026185973287760013956180465985966490809712632281541417662477875
73004832654046320985896537892707355615844544679204113021090698230900434782888310
63422725181826287559943767006080287638261960586892402217404451950147237288753734
14759464648542955911912573962294861347161091075494437328458241568739444020311940
49387746122201206675463426218381497481202382567936371455901734086646472811743136
36184502705368709476244900966367715916761019677361044247483642579297847814035674
78100611645388494344243111573115207359684425935104848752508403942244302212510866
80875965246900470488616602581446182469835965475213170681743465075384364206336293
40016690757352707474269753995031126042745684042937325468366362853525800330698311
14950167780266141614742837513605687206305650159222409793458407047214545205627906
24394678038131808575383537610237194699062674412575234596746970487060133624517538
95093625568332525425792885285719293598748311663642481405988859808568567842846778
14903644103970325227399314171927397755013594143673692773386740674222140445129849
13157302560375030372018543267164880010051729550526707673038111669481295555535597
04665780898799659162564501672552881510088873439723846403790119441248954526966582
75472393327356601353729730458625741848327375604605686847265108204674751386718708
81213969771140527564064185177144833639973027082033868281481895204219986322520709
44850691747504046803900554128597007377044204309606184910776865533555447969243510
50308353664329479197855064288487839786401493522716121483344706334053056835541440
96293295863701610856772184506849256003909240892140429047753075154832862196283664
12664520449981489917836218675616363070049463905278871961793933107963976849537837
41616888980369378972295875260819305271492109299920231484451449256617480340247743
07856140026475082690835665499963900723090641268721683899455023822968443618524046
22124602024105414714397504352013938945504562473799267639742723998823673688977330
09344975836396918334114396799572481115269254007304384079064413314175956122383828
11678001961607065765583929863960845927504006602758921148954125731914935275302778
59352407442437446005734705977816179652501686380834101696270705905788079129646939
98249319604028562741288930194521927967359689241607832379606856386568683827029923
30948918204892239435616948786221222109008230573933851360970612671947177183245984
91605226964952947427332735821010958032709957602756963119376988403235824771716525
13171099629280734620134455875755026833637230796151078656979561314584789655992743
10654900835440682558036687738813325799593683790853331997660744869114569756649021
31376632257208567477692424285336327621883257478683756245679919461823652469132373
04997170483169887969873425982932370037857602462843448829017629026728238311275805
27466893252178864873354845523382706768748423861046595338314710825093338823783896
68181102390016139583588416521933652435081765709853200683344491666045089228055314
94396876752359903644461239459794284225659938590692789246861509533059075604893446
54837230086183790099343114195901318240743123781739223144888501176403308750191679
82835036776727886936445645061124425929746262706481399959067891899078269501062252
89545975880719774894214355585035234498500872347768396387866509855726373847225197
22673130262409261477297220236920370295019894870565697770003871215031299073616144
27813555849725926917874979686403279656280897697086943284832099706573616740056776
56254005107584012915044024526046978106475653238297013319786586349339201949771247
50855532946254979794776478705784742133049099086051775861194957866942599005140170
68201393835262491358114670659870309348117623305761397608939140886716397964582942
07402142064166918851572869168329989468553333569985045162618557264711871422299260
58956741805800630292880596626067981598098631926586889679695518307383133367099795
31027100382725566103165003290543624491008887958224501777955227195713616135186389
59383839196720051645997055264392015676605611375651861930125264136459699669435156
36083820286133648581143664727370038034882599911370655651540526022875422150676597
66194245368742380404116243034634210120990526849144152660633667511317795831369739
43271956513685447277269799961079722421061441943365553271580837308981774192808518
51890380268039126610704795247100822809928220341558083212381861103891414021356229
66961020010831630942863716766399632216169218032748565005984932163031385295823791
96687377772219740071587698068186300324777074535438514194745490150853192081418549
44603894633816817359559747968684348788064195862771694333489043053709114891808801
72477859588452705576526013923405304199519008770869591686381460651540481278503220
32534321049318012409740754885448487011891888340727456063156080088755953007006038
33293080572355355892650934081264014700264077488952037391672397340498290580494422
45225255168149342039618386929579801213383078397932125748570998074144916858434008
55524390546779702676672871242231853571411280947004638503671651126821085257496292
27770793887656595349015006663905860157031038152907875240747461757540674106532840
75273431037726065836727248139017782426053251204009291992654775805268150523619825
34430732411751418256388007929553494121607019103759525586067889792245637626441032
11290722239523849476214950353838418027978450507439741666839155424105552895452284
14497087062002274958798969717048534535558574800488376264355501097041024809972412
64156293341904992109536345686802647386727991866007577351334676072280858807156937
38708289211038259893891880529150319339913248811816047616724744454127072570192049
95083883278942608366558487642821972248979761723924896764296665948177118422707759
39765078289537575529418508465514770207492969914507537477980139682297325932270821
11552255127526004055863443347598356281118429748015962866112609092351586398022777
82022821013699474641279368130324310188614477551420957560119209433272302350722608
25015736197238270964876479850274752365751022870918785875957074495541913853189904
10237727876734939291455706947489816533418472537614615648948039877798722087687391
31294932545215417560563546199606030336151875218192671489806272722950564343322105
24611114956140227798074318736270233330699405036712190623526829554668852176810344
54245333520457165102189707058635903635476148494677017820362372352097756702920896
81675079250252907090868336086388215050638921974507889668422723948048402908787637
14916221828198123741792478652569825750459886934428314411633187977964483452429862
42852779498932431628067172565317574400643138712273148481035200383603653633861334
33702608198383395237198851318671181013258581684526418897635149033510646568096573
10024090470506118865181390538929532646377957388558016735083334955515542137291208
95010583482712754259399856701252376690998164751346183812428909905571353525906020
40924583371823504760983832960400315885835439957734511375764136796448261241467264
31095219443355377069559214639672743365129426974097885310773969196358146992017798
12984189758315741773392080359648679812569244805778784320717386575146076385874445
98961085365247825921355240267184910377329301935312357557025269343972569081150853
95753477189624783708234172639710087402533662707002327873216452109751129932585147
74846077532053941234736700777430383208972558783732115632858787961374037344984187
98582584443689912838400794258252182402457804038215495624120589406633904492083746
39727840918627241169634116456990002086743697234271743873643800569015665921677450
05190869898100457345271436995697918265062478216008008698530283503150878822030996
06650309161464831372771060274049620366564726082094411343316196503690168012331678
27365264348221608829792419663767433662474748030256841809485626625264217058243715
84617521890175224753147004124410985502897047520498868089688500917635504831582768
98280023858657651967155548220643466390401870715205507687240542627321527705792845
97059070854495577425696937230617528743254898259529154665491375472899056410316244
79006921110927613111388507985505575752071241731804492444103733484106910218020422
54435577890209567493350017863942246923463399353587746005717072353358963184052864
63935892999315500347902728978124275910841408052780287701520634430199516411790353
90042804771626914434826393106819616391045880214049463911159841177852861616285012
20087792795633828177336075261413664912293233995008625627778034361851244363845411
28537525587798348127021265575274546665920702359951774618007599836406935668244059
61557559747556853989442594017567489710862956135070895837213033626783802224127777
95444060673809679858440326717515289844084753353428345919276682294524095705442745
37889391969836701085282934312820921197710216808638491339334194584326746951981657
20601917965850906127989939926348375509553515716587942054952167827042243578419589
59544391981029312684912021595958260074662540535545369698003482456337450077119313
25731713500118460269689689622991039437077479424L
15 окт 18, 14:07    [21704195]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Ы2
Gennadiy Usov, вам же предлагали уже python общего назначения. Поставьте его и вычисляйте:
Пока я работаю в JavaScript. Добавлять туда ещё python? А это и есть дополнитеьная программа.

Пока не хочется добавлять.
15 окт 18, 14:14    [21704202]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov,

в своей книге Йодан приводит занимательный пример. Во время занятий по структурному проектированию ему встречались группы программистов, которые не могли продолжить проектирование системы до тех пор, пока они окончательно не поймут, что именно внутри себя делает второстепенный модуль ОЦЕНКАПАРАМЕТРОВ, даже если его напишет кто-то другой вместо них.

Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
15 окт 18, 15:45    [21704289]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
На самом деле всё не так.

Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.
15 окт 18, 15:57    [21704305]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
На самом деле всё не так.

Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.


Ваше убегание - всего лишь один из способов представления длинных чисел. Не засоряйте алгоритм ненужными подробностями. Просто используйте любой удобный вам целочисленный тип, считайте что надо вычислить результат по модулю 2^32 или 2^64. Сам алгоритм напишите.
15 окт 18, 16:06    [21704314]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
На самом деле всё не так.
Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.
Ваше убегание - всего лишь один из способов представления длинных чисел. Не засоряйте алгоритм ненужными подробностями. Просто используйте любой удобный вам целочисленный тип, считайте что надо вычислить результат по модулю 2^32 или 2^64. Сам алгоритм напишите.
Алгоритмы написаны: 21703514 и 21703238 с учетом 21703339.

Я не ищу длинные числа. Я ищу сочетания, которые определяет множество длинных чисел от 1 до 2^K. Например:21690391.

В частности, найти все сочетания 200 чисел. (2^200).
Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний:
20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число.
15 окт 18, 16:44    [21704344]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov,

допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания.

У вас есть алгоритм, который будет ее использовать?
15 окт 18, 16:52    [21704354]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov,

допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания.

У вас есть алгоритм, который будет ее использовать?
Конечно есть: 21690219 или 21693196.

Для доски 997х997 имеется 2^249 сочетаний.
15 окт 18, 17:01    [21704366]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov,

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

Например, кусок из 21690219
				while (p1 < K1) {							
					SOCHET(K, P, p1, i2);		
						
					q=q+1;						
					for(var i = 1; i <=N; i++) {MR[q][i]=F[i];}						
					// признак ФМР3						
					MR[q][0]=16;						
					for(var k2 = 1; k2 <=K; k2++) {						
						if (k2 == 1) {					
							MR[q][ MCHET[k2][1] ]=F[ MCHET[k2][2] ];				
							MR[q][ MCHET[k2][2] ]=F[ MCHET[k2][1] ];				
							MR[q][ MCHET[k2][3] ]=F[ MCHET[k2][4] ];				
							MR[q][ MCHET[k2][4] ]=F[ MCHET[k2][3] ];				
						}					
					}						
15 окт 18, 17:17    [21704378]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov,

Так как мы обсуждаем один из алгоритмов задачи N ферзей, то лучше это обсуждать на другом топике.
15 окт 18, 19:02    [21704447]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21699386 была рассмотрен код поиска всех сочетаний чисел в случае, когда числа имеют два значения 0 или 1.

Попробуем этот код переделать, чтобы искать все сочетания для чисел, которые могут иметь значения от 1 до М.
// K – количество чисел (объектов).							
var P = new Array(K+1);							
for(var i = 1; i <= K; i++) P[i]=1;							
var M;							
while(SOCHETM(K, P, M)) {							
        // печать сочетания							
	for(var i = 1; i <= K; i++) print(P[i]);						
}							
							
function SOCHETM(K, P, M)  {							
	for(var i1 = 1; i1 <=K; i1++) {						
		P[i1]=P[i1]+1;					
		if (P[i1] != (M + 1)) break; 				// Выход из цикла если P[i1] != M+1	
		P[i1] = 1;					
	}						
	return i1 <= K;						
}	
Всего сочетаний будет М^К.
20 ноя 18, 07:14    [21738688]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Тогда поиск сочетаний К чисел, которые могут принимать значения либо 0, либо 1, будет частным случаем поиска сочетаний К чисел (значения от 1 до М).

В этом случае будут два значения: 1 и 2. Это даже удобно для последующей работы с точки зрения нумерации объектов, для которых ищутся сочетания.
При двух значениях К чисел количество сочетаний будет 2^К.
20 ноя 18, 13:51    [21739087]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Есть ещё одна задача.

Необходимо найти сочетания для М чисел из общего количества N чисел.
Каждое число из М чисел может принимать значение либо 1, либо 2.

Конечно, можно составить ещё один массив из М чисел, а затем провести соответствие между этим массивом и масивом P[N].
Однако можно всё сделать в одном массиве, если для этих чисел в массиве P[N] будут значения 0.

Тогда имеем код для этого варианта сочетаний:
function main {							
	var N1=13;						
	var P = new Array(N1+2);						
	for(var i = 1; i <= N1; i++) P[i]=1;						
	P[3]=0;						
	P[9]=0;						
	p[11]=0;						
	var M=8;						
	var M1=2;						
	while(SOCHET3(N1, P, M1)) {						
		for(var i = 1; i <= N1; i++) print(P[i]);					
	}						
}							
							
function SOCHETM(K, P, M)  {							
	for(i1 = 1; i1 <=K; i1++) {						
		if (P[i1] >0) {					
			P[i1]=P[i1]+1;				
			if (P[i1] != (M + 1)) break; 			// Выход из цикла если P[i1] != M+1	
			P[i1] = 1;				
		}					
	}						
	return i1 <= K;						
}	
24 ноя 18, 13:34    [21743628]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1016
Gennadiy Usov
Aleksandr Sharahov
Gennadiy Usov,

допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания.

У вас есть алгоритм, который будет ее использовать?
Конечно есть: 21690219 или 21693196.

Для доски 997х997 имеется 2^249 сочетаний.
Возьмите доску поменьше, убедитесь в том, что вы никогда не сможете дождаться перебора даже 2^64 сочетаний. Зачем вам алгоритм, который требует триллионы лет для завершения?
24 ноя 18, 20:24    [21743845]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Barlone
Gennadiy Usov
Конечно есть: 21690219 или 21693196.

Для доски 997х997 имеется 2^249 сочетаний.
Возьмите доску поменьше, убедитесь в том, что вы никогда не сможете дождаться перебора даже 2^64 сочетаний. Зачем вам алгоритм, который требует триллионы лет для завершения?
Есть формула, а есть реализация этой формулы на компьютере.

Это две разные вещи!
24 ноя 18, 21:21    [21743869]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Ранее рассматривались "линейные" сочетания для одномерного массива чисел.

А если рассмотреть сочетания на плоскости для двумерного массива чисел.

То есть, необходимо найти сочетания для чисел из массива N на М.
Каждое число из массива чисел может принимать значение либо 1, либо 2.

Конечно, можно составить ещё один массив из NxM чисел, а затем провести соответствие между этим массивом и масcивом P[N][M].
Однако интереснее иметь сочетания для двумерного массива.

Тогда имеем код для варианта сочетаний двумерного массива чисел:
						
function main {						
	var N1=13;					
	var N2=13;					
	var P = new Array(N1+2);					
	for (var i = 0; i < =N1 + 1; i++) { MR5[i] = new Array(N2+1);}					
	for(var i = 1; i <= N1; i++) {					
		for(var j = 1; j <= N2; j++) {				
			P[i][j]=1;			
		}				
	}					
	var M=2;					
	while(SOCHETNxM(N1, N2, P, M)) {					
		for(var i = 1; i <= K; i++) print(P[i]);				
	}					
}						
function SOCHETNxM(K1, K2, P, M)  {						
	for(i1 = 1; i1 <=K1; i1++) {					
		for(i2 = 1; i2 <=K2; i2++) {				
			if (P[i1] [i2] >0) {			
				P[i1][i2]=P[i1][i2]+1;		
				if (P[i1][i2] != (M + 1)) break; 		
				P[i1] [i2]= 1;		
			}			
		}				
	}					
	return i1 <= K1;					
}	
Аналогично можно будет определять сочетания для R-мерного массива чисел.

И аналогично можно будет в этих массивах чисел искать сочетания не для всех чисел.
25 ноя 18, 07:06    [21743999]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Есть ещё интересная задача.

Необходимо найти сочетания N чисел, которые принимают значения либо 1, либо 2.
При этом, количество "двоек" в сочетаниях не должно превышать некоторого предельного значения PR.

Попробуем составить код для данной задачи:
							
function main {							
	var N1=13;						
	var P = new Array(N1+2);						
	for(var i = 1; i <= N1; i++) P[i]=1;						
	P[0]=0;						
							
	var PR=(N-1)/4;						
							
	var M1=2;						
	while(SOCHET3(N1, P, M1, PR)) {						
		for(var i = 1; i <= K; i++) print(P[i]);					
	}						
}							
							
function SOCHETM(K, P, M, PR)  {							
	for(i1 = 1; i1 <=K; i1++) {						
		if (P[i1] >0) {					
			P[i1]=P[i1]+1;				
			P[0]=P[0]+1;				
			if (P[i1] != (M + 1) || P[0] <=PR) break; 				// Выход из цикла если P[i1] != M+1
			if (P[i1] == (M + 1)) {				
				P[0]=P[0]-1;			
				P[i1] = 1;			
			}				
		}					
	}						
	return i1 <= K;						
}	
26 ноя 18, 06:38    [21744442]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
В другом форуме ту же проблему обсуждают.
Дали ссылку на алгоритм https://habr.com/post/248493/

Дублирую сюда. Может чем поможет.
26 ноя 18, 13:49    [21744930]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
В другом форуме ту же проблему обсуждают.
Дали ссылку на алгоритм https://habr.com/post/248493/
Дублирую сюда. Может чем поможет.
Спасибо за информацию!

Но, по-моему, несколько сложно.
Ведь у нас очень неплохо получилось: 21699386 или 21690515.

Меня сейчас больше интересуют усложнения сочетаний: сочетания с ограничениями, сочетания чисел, принимающих М значений, сочетания на плоскости.
Может быть ещё что-то появится.
26 ноя 18, 16:56    [21745176]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Dima T
В другом форуме ту же проблему обсуждают.
Дали ссылку на алгоритм https://habr.com/post/248493/

Дублирую сюда. Может чем поможет.


Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))
26 ноя 18, 18:26    [21745291]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Aleksandr Sharahov
Dima T
В другом форуме ту же проблему обсуждают.
Дали ссылку на алгоритм https://habr.com/post/248493/

Дублирую сюда. Может чем поможет.


Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))

Возможно. Алгоритм интересный, но упирается в изъятие элементов массива, что тормоз. Может я его не допонял, читаю исходник, пытаюсь в синтаксисе VB разобраться. Наверно лучше там упомянутую книгу качнуть.
26 ноя 18, 19:05    [21745331]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Aleksandr Sharahov
Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.
26 ноя 18, 19:13    [21745339]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Aleksandr Sharahov
Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.
Что-то похожее на разделение в 21702893?
26 ноя 18, 19:32    [21745363]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Dima T
Aleksandr Sharahov
Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.


тогда будет проблемой, как подменять элементы в сгенерированных раскладах
26 ноя 18, 20:35    [21745417]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Aleksandr Sharahov
Dima T
пропущено...

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.


тогда будет проблемой, как подменять элементы в сгенерированных раскладах


Сделал заготовку, лучше ее показать чтобы понятнее было, а то потом после тюнинга код тяжело читать будет.
Пример кода слияния двух последовательностей комбинаций для N = 2: 01 10
// Последовательности для слияния
PermutationBy2 first = new PermutationBy2(), second = new PermutationBy2();
int[] first_arr = new int[2], second_arr = new int[2];
// Порядок слияния
var union = new Union(first_arr.Length, second_arr.Length);
// Массив под очередное значение результата
var result = new int[first_arr.Length + second_arr.Length];

// Перебор элементов первой последовательности
first.Reset();
while(first.Next(ref first_arr)) { 
	// Перебор всех элементов второй последоватильности
	second.Reset();
	while(second.Next(ref second_arr)) { 
		// Перебор всех порядков слияния
		union.Reset();
		while(union.Next()) {
			int first_pos = 0, second_pos = 0;
			// Слияние согласно union
			for(int i = 0; i < result.Length; i++) {
				if(union.IsFirst(i)) {
					result[i] = first_arr[first_pos];
					first_pos++;
				} else {
					result[i] = second_arr[second_pos] + first_arr.Length;
					second_pos++;
				}
			}
			result.Print(); // Вывод строки результата
		}
	}
}

+ код классов
	// Последовательность перестановок по 2
	sealed class PermutationBy2{
		static int[,] data = {{0, 1}, {1, 0}};
		int pos;

		// Инициализация 
		public void Reset() {
			pos = 0;
		}

		// Следующая комбинация в массив arr. false если все кончились
		public bool Next(ref Int32[] arr) {
			if(pos > 1) return false;
			arr[0] = data[pos, 0];
			arr[1] = data[pos, 1];
			pos++;
			return true;
		}
	}



	// Последовательность порядков слияния. Комбинации типа 0011, 0101, 0110, 1001, 1010, 1100
	sealed class Union {
		bool[] pos; // текущий порядок
		int first; // Размер первой последовательности
		bool need_init;

		public Union(int first, int second) {
			pos = new bool[first + second];
			this.first = first;
		}

		// Сброс в начальное состояние
		public void Reset() {
			need_init = true;
		}

		// Следующая комбинация. false если ее нет
		public bool Next() {
			if(need_init) {
				for(int i = 0; i < pos.Length; i++) pos[i] = (i < first);
				need_init = false;
				return true;
			}

			bool stop = true;
			int pos1 = -1, cnt = -1;
			for(int i = 0; i < pos.Length; i++) {
				if(pos[i]) {
					if(pos1 == -1) pos1 = i;
					cnt++;
				} else {
					if(pos1 != -1) {
						pos[i] = true;
						for(int j = 0; j < i; j++) pos[j] = (j < cnt);
						stop = false;
						break;
					}
				}
			}
			return !stop;
		}

		// Проверка что элемент n относится к первой последовательности
		public bool IsFirst(int n) {
			return pos[n];
		}

		public void Print() {
			pos.Print();
		}
	}

+ Результат
0 1 2 3
0 2 1 3
2 0 1 3
0 2 3 1
2 0 3 1
2 3 0 1
0 1 3 2
0 3 1 2
3 0 1 2
0 3 2 1
3 0 2 1
3 2 0 1
1 0 2 3
1 2 0 3
2 1 0 3
1 2 3 0
2 1 3 0
2 3 1 0
1 0 3 2
1 3 0 2
3 1 0 2
1 3 2 0
3 1 2 0
3 2 1 0

Оптимизации пока никакой не делал, чтоб читаемость не рушить. Как минимум просится предварительный перегон в массивы second и union.
Единственный минус что массив с очередным результатом каждый раз полностью заполняется, но это относительно небольшой тормоз.

Суть задумки что внутри каждого объекта PermutationBy2 может быть два других объекта, т.е. дерево.
В итоге будет класс Permutation(int N) с генератором последовательности комбинаций N по N.
Примерно так
Permutation p = new Permutation(N);
int[] arr = new int[N];
while(p.Next(ref arr)) ... обработка arr
28 ноя 18, 10:32    [21746929]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Dima T,

вопрос в том, будет ли процедура Union.Next достаточно быстрой, т.к. все упирается в ее скорость
28 ноя 18, 11:55    [21747079]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Aleksandr Sharahov
Dima T,

вопрос в том, будет ли процедура Union.Next достаточно быстрой, т.к. все упирается в ее скорость

Если внутри Union все загнать в массив, то будет быстро.

В общем случае для Union(K, M) потребуется (K+M)! / (K!*M!) массивов bool[K+M]
Например для Union(10,10) потребуется массив 184756 массивов bool[20].

Union(K, M) это все варианты разместить K единиц в K+M элементах.
Для случая (2,2) получается 6:
0011, 0101, 0110, 1001, 1010, 1100

И самое главное что я тут вижу - этот алгоритм параллелится. Просто разбить Union на части.
28 ноя 18, 13:54    [21747331]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Dima T,

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

Проблемы запараллелить генерацию перестановок, в принципе, нет.
Это можно провернуть почти с любым алгоритмом.
28 ноя 18, 14:50    [21747441]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Для случая (2,2) получается 6:
0011, 0101, 0110, 1001, 1010, 1100
А как же следующие перестановки:
0001, 0100, 0010, 0001, 1000, 1101, 
и т.д., где 1 или 3 единички?
28 ноя 18, 17:17    [21747680]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Aleksandr Sharahov
Нерекурсивный алгоритм по той ссылке, скорее всего, по всем параметрам проиграет рекурсивному ))

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.
В сообщении 21704344 рассматривался вопрос

"Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний:
20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число."

Далее можно ещё делить, пока не придем к наименьшим составляющим:

Например: 33= 2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+1, или формируется дерево, где элементы расположены попарно и постепенно уменьшаются.
28 ноя 18, 17:34    [21747689]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
Для случая (2,2) получается 6:
0011, 0101, 0110, 1001, 1010, 1100
А как же следующие перестановки:
0001, 0100, 0010, 0001, 1000, 1101, 
и т.д., где 1 или 3 единички?

Это не все решение, а его часть. Надо склеить два массива в данном примере по два элемента. На место 0 подставляем из первого, на место 1 - из второго. Если будет три 0 или 1, то получим ошибку выхода за пределы массива, т.к. в каждом по два элемента.
28 ноя 18, 18:40    [21747790]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...

У меня еще есть идея нерекурсивного алгоритма с деревом. Основано на идее что все комбинации по N элементов можно получить имея все комбинации по K и M, где K+M=N.
Например для N=15 берем 7+8, где 7 = 3+4, 8 = 4+4, 3 = 2+1, 4 = 2+2.
В сообщении 21704344 рассматривался вопрос

"Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний:
20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число."

Далее можно ещё делить, пока не придем к наименьшим составляющим:

Например: 33= 2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+1, или формируется дерево, где элементы расположены попарно и постепенно уменьшаются.

Извини, но тут я просто тебя не понимаю, я не понимаю как работает твой алгоритм. Мой пост был по теме топика "сочетания из К чисел".
+ Я под этим понимаю что например так выглядит сочетание из 4-х по 4
0 1 2 3
0 2 1 3
2 0 1 3
0 2 3 1
2 0 3 1
2 3 0 1
0 1 3 2
0 3 1 2
3 0 1 2
0 3 2 1
3 0 2 1
3 2 0 1
1 0 2 3
1 2 0 3
2 1 0 3
1 2 3 0
2 1 3 0
2 3 1 0
1 0 3 2
1 3 0 2
3 1 0 2
1 3 2 0
3 1 2 0
3 2 1 0

У тебя же как-то по-другому, и я не смог понять как и почему.
28 ноя 18, 18:47    [21747801]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
А как же следующие перестановки:
0001, 0100, 0010, 0001, 1000, 1101, 
и т.д., где 1 или 3 единички?

Это не все решение, а его часть. Надо склеить два массива в данном примере по два элемента. На место 0 подставляем из первого, на место 1 - из второго. Если будет три 0 или 1, то получим ошибку выхода за пределы массива, т.к. в каждом по два элемента.
Так и у меня склейка: склеиваю несколько массивов, которые в сумме дают длину N.

При этом существует правило:
- к каждому сочетанию первого массива "приклеиваются" все сочетания второго массива;
- к каждому сочетанию первого и второго массивов "приклеиваются" все сочетания третьего массива;
- к каждому сочетанию первого, второго и треьего массивов "приклеиваются" все сочетания четвертого массива;
и т.д.
Dima T
Gennadiy Usov
В сообщении 21704344 рассматривался вопрос
"Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний:
20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число."
Далее можно ещё делить, пока не придем к наименьшим составляющим:
Например: 33= 2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+1, или формируется дерево, где элементы расположены попарно и постепенно уменьшаются.
Извини, но тут я просто тебя не понимаю, я не понимаю как работает твой алгоритм. Мой пост был по теме топика "сочетания из К чисел".
+ Я под этим понимаю что например так выглядит сочетание из 4-х по 4
0 1 2 3
0 2 1 3
2 0 1 3
0 2 3 1
2 0 3 1
2 3 0 1
0 1 3 2
0 3 1 2
3 0 1 2
0 3 2 1
3 0 2 1
3 2 0 1
1 0 2 3
1 2 0 3
2 1 0 3
1 2 3 0
2 1 3 0
2 3 1 0
1 0 3 2
1 3 0 2
3 1 0 2
1 3 2 0
3 1 2 0
3 2 1 0
У тебя же как-то по-другому, и я не смог понять как и почему.
Это не мой алгоритм, а наш совместный:
21690391 или 21699386.
+ Я так понимаю сочетания из 4-х по 4
0	0	0	0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
И чем отличается у Вас первое и последнее сочетания по смыслу?
28 ноя 18, 19:11    [21747819]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Это не мой алгоритм, а наш совместный:
21690391 или 21699386.

Нет. Там я не вникал в алгоритм. Я просто указал как правильнее делать его части.

Gennadiy Usov
+ Я так понимаю сочетания из 4-х по 4
0	0	0	0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
И чем отличается у Вас первое и последнее сочетания по смыслу?

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

Умножь первое число на 8, второе на 4, третье на 2, четвертое как есть. Сложи что получилось и получишь 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15. Это типа перевод из двоичной в десятичную.

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

PS Можно на "ты"
28 ноя 18, 20:27    [21747883]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Если ты не можешь описать задачу, которую решаешь - то ты ее не решишь, ни сам, ни с чужой помощью, т.к. не помогут потому что банально не поймут в чем помочь надо.
28 ноя 18, 20:36    [21747886]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
+ Я так понимаю сочетания из 4-х по 4
0	0	0	0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
И чем отличается у Вас первое и последнее сочетания по смыслу?

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

Умножь первое число на 8, второе на 4, третье на 2, четвертое как есть. Сложи что получилось и получишь 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15. Это типа перевод из двоичной в десятичную.

Я не понимаю зачем тебе надо изобретать этот древний велосипед?
Нет, сам велосипед я прекрасно понимаю, но не понимаю что дальше ты хочешь с ним делать?
Это ты увидел двоичную систему, а я увидел номера чисел, которые участвуют в сочетаниях: 1 в третьей колонке - значит третье число участвует в сочетании.
Кстати, это описано в 21281836.

А ты так и не ответил на вопрос:
И чем отличается у тебя первое и последнее сочетания в твоих сочетаниях по смыслу?

Мне кажется, что ты рассматриваешь не сочетания, а перестановки чисел. А эта задача уже не по теме топика.
Из вики: "сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов".
28 ноя 18, 20:47    [21747889]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
А ты так и не ответил на вопрос:
И чем отличается у тебя первое и последнее сочетания в твоих сочетаниях по смыслу?

Я не могу ответить на этот вопрос, не вижу в нем смысла!

Мои сочетания просты и понятны. Если применительно к ферзям, то число означает позицию в строке, а его положение - номер строки.
Т.е. 3,2,0,1 это такая доска
0123
Ф
Ф
Ф
Ф
28 ноя 18, 21:03    [21747899]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Теперь ты объясни что значит твое 1101. Простыми словами.
28 ноя 18, 21:07    [21747900]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
А ты так и не ответил на вопрос:
И чем отличается у тебя первое и последнее сочетания в твоих сочетаниях по смыслу?

Я не могу ответить на этот вопрос, не вижу в нем смысла!

Мои сочетания просты и понятны. Если применительно к ферзям, то число означает позицию в строке, а его положение - номер строки.
Т.е. 3,2,0,1 это такая доска
0123
Ф
Ф
Ф
Ф
Далее я теряюсь...
А почему нельзя рассматривать такие комбинации, если работаем с плоскостью:
0123
Ф
Ф
Ф

0123
ФФ
Ф
Ф
28 ноя 18, 21:23    [21747906]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Теперь ты объясни что значит твое 1101. Простыми словами.
Очень просто: из четырех объектов в сочетании участвуют первый, второй и четвертый.
28 ноя 18, 21:24    [21747907]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Dima T
пропущено...

Я не могу ответить на этот вопрос, не вижу в нем смысла!

Мои сочетания просты и понятны. Если применительно к ферзям, то число означает позицию в строке, а его положение - номер строки.
Т.е. 3,2,0,1 это такая доска
0123
Ф
Ф
Ф
Ф
Далее я теряюсь...
А почему нельзя рассматривать такие комбинации, если работаем с плоскостью:
0123
Ф
Ф
Ф

0123
ФФ
Ф
Ф

Форма записи выбирается под решаемую задачу.
Если речь про ферзей, то комбинации с двумя ферзями в столбце или строке недопустимы, поэтому нет смысла их рассматривать.
Самая компактная форма записи - массив, где значение элемента обозначает столбец, положение (индекс массива) - строку.
Т.е. моя запись описывает одну доску 4*4, с возможно правильной расстановкой ферзей.
Генерим все возможные комбинации - получаем множество решений, внутри которого содержаться все правильные решения.
Gennadiy Usov
Dima T
Теперь ты объясни что значит твое 1101. Простыми словами.
Очень просто: из четырех объектов в сочетании участвуют первый, второй и четвертый.

Зачем? Дальше что с этим знанием делать? Я не понимаю, потому что не вижу практического смысла в этом.
29 ноя 18, 08:29    [21748026]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Dima T
Мои сочетания просты и понятны. Если применительно к ферзям, то число означает позицию в строке, а его положение - номер строки.
Т.е. 3,2,0,1 это такая доска
0123
Ф
Ф
Ф
Ф
Форма записи выбирается под решаемую задачу.
Если речь про ферзей, то комбинации с двумя ферзями в столбце или строке недопустимы, поэтому нет смысла их рассматривать.
Самая компактная форма записи - массив, где значение элемента обозначает столбец, положение (индекс массива) - строку.
Т.е. моя запись описывает одну доску 4*4, с возможно правильной расстановкой ферзей.
Генерим все возможные комбинации - получаем множество решений, внутри которого содержаться все правильные решения.
Значит, все-таки ферзи на доске 4х4. Я думал, что что-то другое.
Тогда пишите не ферзи, а ладьи.
И всем будет понятно, почему можно ставить фигуры на доску, и при этом не быть под боем.

И что при этом означает твоя фраза: "с правильной расстановкой ферзей", когда ферзи под боем?
29 ноя 18, 09:15    [21748052]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Gennadiy Usov
Значит, все-таки ферзи на доске 4х4. Я думал, что что-то другое.
Тогда пишите не ферзи, а ладьи.
И всем будет понятно, почему можно ставить фигуры на доску, и при этом не быть под боем.

Пусть будут ладьи. Все множество ладьей содержит в себе подмножество ферзей.
Если бы существовал формат записи, при котором каждая запись давала бы очередное решение задачи ферзей, то задачи бы не было.
Количество комбинаций расстановки ладьей без боя считается элементарно.

Gennadiy Usov
И что при этом означает твоя фраза: "с правильной расстановкой ферзей", когда ферзи под боем?

Это не моя фраза. В моей фразе было слово "возможно".

Повторюсь: я говорю про формат записи. Его задача уместить все правильные решения с минимальной избыточностью, т.е. минимум неправильных решений.
29 ноя 18, 09:38    [21748071]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Dima T
Gennadiy Usov
Dima T
Теперь ты объясни что значит твое 1101. Простыми словами.
Очень просто: из четырех объектов в сочетании участвуют первый, второй и четвертый.
Зачем? Дальше что с этим знанием делать? Я не понимаю, потому что не вижу практического смысла в этом.
Ты не видишь, и это плохо.

Есть понятие: выбрать К объектов из N объектов – это общеизвестный термин «сочетания».
Если применительно к задаче N ферзей, то приложений сочетаний там много.

Это было показано в нескольких кодах на соседнем топике.
Например, в алгоритме МММ на доске (NхМ)x(NхМ) имеет место включенная матрица МхМ. Этих матриц будет N по количеству ферзей на доске NxN.

Оказалось, что в одном алгоритме могут быть 2 включенные матрицы.
Тогда сочетание из 0 и 1 в количестве N чисел показывает: на месте включенной матрицы будет либо 1-ая матрица, либо 2-ая матрица.
Можно вместо 0 и 1 применить 1 и 2.
29 ноя 18, 13:08    [21748458]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8 9      [все]
Все форумы / Программирование Ответить