ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
25 сообщений из 206, страница 1 из 9
  1  все
Поиск любых сочетаний из К чисел
    #39619520
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Большая просьба!
Не подскажите, где можно найти алгоритм поиска всех возможных сочетаний из К чисел, включая одно число.
Хотя с одним числом все ясно.
Данный алгоритм необходим для поиска сочетаний двоек вертикалей при определения решений на досках МхМ.
В дальнейшем необходимо будет ввести ограничения, например, цифра 4 не может быть с цифрой 7 в одном сочетании.
...
Рейтинг: 0 / 0
23.03.2018, 14:01
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619522
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Сочетания
...
Рейтинг: 0 / 0
23.03.2018, 14:03
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619629
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.
...
Рейтинг: 0 / 0
23.03.2018, 16:19
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619723
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Ну ведь если для парных, то ваще просто в лоб: каждый с каждым и "пополам", верхний треугольник 2мерной матрицы перебора.
...
Рейтинг: 0 / 0
23.03.2018, 17:32
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619741
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
exp98,
а если и по 3, и по 4 и по.....
...
Рейтинг: 0 / 0
23.03.2018, 17:45
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619783
m7m
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m7m
Участник
Gennadiy Usovexp98,
а если и по 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 очередное сочетание
...
Рейтинг: 0 / 0
23.03.2018, 18:48
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619788
Александр Бердышев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Александр Бердышев
Участник
Буквально на прошлой неделе решал задачу с сочетаниями.

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 в двоичном представлении.
...
Рейтинг: 0 / 0
23.03.2018, 19:03
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619800
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Александр Бердышев,

Идея хорошая.
Но дело в следующем: как заполнить такую матрицу, размером, например, 120 х 120.
Вариантов где-то 6,64614E+35.
Можно начать и с меньших значений.
...
Рейтинг: 0 / 0
23.03.2018, 19:30
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619804
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.
Есть формула вычисления приближенного значения факториала, но для точного значения считать как в школьном учебнике, т.е. для n! перемножить числа от 1 до n.
...
Рейтинг: 0 / 0
23.03.2018, 19:54
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619807
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy UsovАлександр Бердышев,

Идея хорошая.
Но дело в следующем: как заполнить такую матрицу, размером, например, 120 х 120.
Вариантов где-то 6,64614E+35.
Можно начать и с меньших значений.
Ошибся.
Для доски 1000х1000, наверное, потребуется сделать комбинации из 67 чисел.
Вариантов где-то 7,3787E+19.
...
Рейтинг: 0 / 0
23.03.2018, 20:00
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619810
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
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 очередное сочетание
Я попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное !
...
Рейтинг: 0 / 0
23.03.2018, 20:05
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619813
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Gennadiy UsovDima T,

Эту формулу я видел.
Думал. что кто-то видел алгоритм, реализующий эту формулу.на каком языке программирования?
...
Рейтинг: 0 / 0
23.03.2018, 20:07
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619815
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
паскаль:

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

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

http://e-maxx.ru/algo/generating_combinations
...
Рейтинг: 0 / 0
23.03.2018, 20:10
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619823
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovЯ попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное !
Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.
...
Рейтинг: 0 / 0
23.03.2018, 20:31
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619825
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
S.G.,

Спасибо за информацию. Изучаю.
...
Рейтинг: 0 / 0
23.03.2018, 20:32
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619826
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovЯ попробовал начать писать алгоритм, и получается, что количество вложенных циклов - переменное !
Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.
Все варианты. А потом буду отбрасывать те, в которых не устраивает сочетания цифр. Или делать это параллельно.
...
Рейтинг: 0 / 0
23.03.2018, 20:37
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619828
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima Tпропущено...

Тебе что надо: количество сочетаний или все варианты сочетаний? Это разные вещи.
Все варианты. А потом буду отбрасывать те, в которых не устраивает сочетания цифр. Или делать это параллельно.
Gennadiy UsovВариантов где-то 7,3787E+19.
Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет
...
Рейтинг: 0 / 0
23.03.2018, 20:50
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619830
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovВариантов где-то 7,3787E+19.
Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет
Пока я не говорю о вычислении.
Я пока говорю об алгоритме.
А там будет видно, для каких досок данный алгоритм будет применим с точки зрения производительности.
...
Рейтинг: 0 / 0
23.03.2018, 20:56
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619901
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Александр БердышевБуквально на прошлой неделе решал задачу с сочетаниями.

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

Теперь нужно понять: какова вместительность ячейки на отдельно взятом компьютере.
...
Рейтинг: 0 / 0
24.03.2018, 07:08
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619902
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
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.
...
Рейтинг: 0 / 0
24.03.2018, 07:22
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619913
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Если не удобно работать в двоичной системе и в работе с битами, то можно раотать в десятичной.
Для этого формируем матрицу 10 х 512, и формируем элементы этой матрицы следующим образом: либо 1, либо 0.
Такая матрица формирууется 1 раз.
Аналогично восьмеричной системе, с помощью такой матрицы можно формировать любые сочетания для очень больших массивов.
...
Рейтинг: 0 / 0
24.03.2018, 09:07
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619933
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тут посмотри
https://prog-cpp.ru/placement/
https://prog-cpp.ru/combinations/
...
Рейтинг: 0 / 0
24.03.2018, 11:23
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619946
Мудроглюков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Мудроглюков
Участник
Gennadiy UsovБольшая просьба!
Не подскажите, где можно найти алгоритм поиска всех возможных сочетаний из К чисел, включая одно число.
Хотя с одним числом все ясно.
Данный алгоритм необходим для поиска сочетаний двоек вертикалей при определения решений на досках МхМ.
В дальнейшем необходимо будет ввести ограничения, например, цифра 4 не может быть с цифрой 7 в одном сочетании.

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

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

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

______________
Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?
...
Рейтинг: 0 / 0
24.03.2018, 13:07
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619954
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Gennadiy Usov То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

Мы можем для удобства выстроить любую систему счисления, в зависимости от удобства, кратную 2.
Все можно, только с временем будет напряг 21282030
...
Рейтинг: 0 / 0
24.03.2018, 13:56
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39619977
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Попробую ответить сразу всем.
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.
Чем этот алгоритм не нравится?
...
Рейтинг: 0 / 0
24.03.2018, 15:15
| Ответить | Цитировать | Написать  
25 сообщений из 206, страница 1 из 9
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=12&tid=1340024]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 64ms
get topic data:
 12ms
get forum data:
 2ms
get page messages:
 65ms
get tp. blocked users:
 2ms
others: 14ms
total:  191ms
созд. / загр.: 191ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]