Брут-форс, много ли требуется ресурсов?

[Danila96]

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

Для начала - хотел написать ТЗ, что бы методом перебора найти наименьшую комбинацию в массиве данных. Если что, это никак не связано с криминалом и хакингом
Открыл гугл, нашел сайт, где онлайн показывает количество комбинаций. Допустим 2 из 15 дают 105 вариантов. Вроде и не большие цифры, но стОит только начать увеличивать цифры, как идет прогрессия. Например 10 из 1000 дают "263409560461970212832400" комбинаций.
С одной стороны - сумасшедшие цифры. С другой - ну так и компьютер не 16 битный 90-х годов.

Собственно вопрос местным программистам - современный домашний комп, как долго будет просчитывать такое количество вариантов?
Я знаю что "домашний комп" понятие растяжимое, но я не знаю какой характеристике ТТХ нужно в данном случае отдать предпочтение - памяти, процессору, жесткому диску, но если узнать хотя бы порядок цифр, или кто поделится хотя бы каким макаром делать прикидки - буду благодарен.

[Arigato]

Сообщение от Danila96

как долго будет просчитывать такое количество вариантов?

А просто прикинуть сложно? Просто упрощенно. У ЦП тактовая частота в районе нескольких ГГц, даже если распараллелить задачу на несколько ядер, можно условно принять, что за секунду будет рассмотрено миллиард вариантов. А теперь считайте, сколько секунд потребуется для вашего значения:

263 409 560 461 970 (212 832 400) - в скобках это миллиард. То есть остается 263 409 560 461 970 секунд. В году 60 * 60 * 24 * 365 = 31 536 000 секунд. Делите - 8 352 662 лет. Если у вас есть 8 миллионов лет в запасе, то запускайте программу

[kvitaliy]

Сообщение от Danila96

методом перебора найти наименьшую комбинацию в массиве данных.

А что означает "наименьшая комбинация в массиве данных"?
Можно пример из 5 значений массива?

Сообщение от Danila96

Например 10 из 1000

Это означает например 10 символьный набор из 1000 возможных?
А где реально используется в компьютере 1000 различных символов?

[Danila96]

Сообщение от Arigato

А просто прикинуть сложно? Просто упрощенно. У ЦП тактовая частота в районе нескольких ГГц, даже если распараллелить задачу на несколько ядер, можно условно принять, что за секунду будет рассмотрено миллиард вариантов. А теперь считайте, сколько секунд потребуется для вашего значения:

263 409 560 461 970 (212 832 400) - в скобках это миллиард. То есть остается 263 409 560 461 970 секунд. В году 60 * 60 * 24 * 365 = 31 536 000 секунд. Делите - 8 352 662 лет. Если у вас есть 8 миллионов лет в запасе, то запускайте программу

Спасибо за консультацию, я думал что эта цифры будет исчисляться днями - максимум неделями

[Danila96]

Сообщение от kvitaliy

А что означает "наименьшая комбинация в массиве данных"?
Можно пример из 5 значений массива?


Это означает например 10 символьный набор из 1000 возможных?
А где реально используется в компьютере 1000 различных символов?

Это не для использования в ПК, это для использования в реальной жизни.
Что бы не плодить загадок - тотализатор. Бриф системы позволяют снизить затраты. Из того что есть в открытом доступе не совсем оптимальны. Есть более грамотно подобранные системы, которые дешевле на 30% чем в открытом доступе.

[kvitaliy]

Сообщение от Danila96

тотализатор

Ну тут да, рулят хитрые формулы и верные выигрыши

[Danila96]

Тут еще вопрос возник по данной теме, я правильно понимаю что перебор и распараллеливание это не совместимые вещи?

[evg_m]

перебрать от 00001 до 00999
перебрать от 01000 до 01999
перебрать от 02000 до 02999
...

вполне параллельные переборы, ЕСЛИ...
то что внутри не требует одного и того же ресурса в исключительном(монопольном) доступе ОДНОВРЕМЕННО.
например одновременная запись в один и тот же файл.

[Danila96]

Сообщение от evg_m

перебрать от 00001 до 00999
перебрать от 01000 до 01999
перебрать от 02000 до 02999
...

вполне параллельные переборы, ЕСЛИ...
то что внутри не требует одного и того же ресурса в исключительном(монопольном) доступе ОДНОВРЕМЕННО.
например одновременная запись в один и тот же файл.

Спасибо за ответ, по моим прикидкам не получается такой вариант.
Вот пример:
Комбинация из трех переменных в три ряда (надеюсь выразился не слишком криво):
А-В-С
А-В-С
А-В-С
дает нам 27 возможных комбинаций:
В-В-В
В-В-А
В-В-С
В-А-В
В-А-А
В-А-С
В-С-В
В-С-А
В-С-С
А-В-В
А-В-А
А-В-С
А-А-В
А-А-А
А-А-С
А-С-В
А-С-А
А-С-С
С-В-В
С-В-А
С-В-С
С-А-В
С-А-А
С-А-С
С-С-В
С-С-А
С-С-С
Если мы начнем искать минимально возможное количество комбинаций, что бы при любом исходе гарантированно в одном из вариантов цепляло 2 исхода мы получаем такой пакет вариантов.
С-С-С
В-В-В
А-А-В
А-В-А
В-А-А
Как видим, они разбросаны по всему столбцу из 27 вариантов. То есть если этот столбец "распилить" (распараллелить) на три подзадачи по 9 вариантов в каждом, мы получаем что задача не выполнится, так как в "своем" участке программы не найдут оптимальных комбинаций, или найдут, но там уже будет на 5, а 6 или 7 вариантов.

Я поразмышляв пришел что "распилить" можно, но другим путем. Берем основу из 27 вариантов, и начинаем формировать новые варианты. Нулевую строку вырезаем и переносим в конец, строка что шла за ней становится нулевым. Следующим шагом, из нового списка формируем таким же образом еще один такой список.
Таким образом мы формируем к основе еще 26 новых списков.
То есть перебор ускоряется на порядок.
Но я думаю, что есть еще варианты, просто мне из-за своего скудоумия это не очевидно.

[сфинкс]

Проверим 2 из 15:

= 15 * (15-1) / ( 2 * (2-1) )
= 105

Да автор темы считает там правильно

Визуализация в 3-ем ютюбе "Комбинаторика просто"
в моём сообщении
https://www.programmersforum.ru/show...41#post1806541

Количество перестановок простейшее: факториал

Например переставить 3 книги: 3! = 6 вариантов

123 132 213 231 312 321