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