Форум на Исходниках.RU

Генерация размещений

mkudritsky — Fri, 08 Jan 2021 04:22:52 +0000

mkudritsky:

Цитата Qraizer @ 06.10.20, 17:32

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

Правильно делаете, что не уверены в эффективности рекурсии!
При решении другой комбинаторной задачи мы выявили, что рекурсия минимум в 3 раза уменьшает скорость работы программы.

P.S. В этой связи мы, например, переписали стандартный алгоритм поиска файлов по маске в файловой системе.
Убрали рекурсию и сделали все без рекурсии.
Эффективностью нового алгоритма не нарадуемся!

Генерация размещений

OpenGL — Wed, 07 Oct 2020 07:49:19 +0000

OpenGL: Да, что-то я не подумал про то, что тебе не просто размещения, а размещения с повторениями нужны. Их лучше самому написать, приспособить что-то из std вряд-ли будет сильно проще, чем написание. По крайней мере я всегда сам их генерировал.

Генерация размещений

JoeUser — Wed, 07 Oct 2020 04:51:56 +0000

JoeUser: Qraizer, :good:

Генерация размещений

Qraizer — Wed, 07 Oct 2020 03:30:40 +0000

Qraizer: Та понял я. Просто в контексте "брутфорс по словарю" обычно имеются в виду словарные атаки.

Цитата JoeUser @ 06.10.20, 08:22

И мне нужно из словаря размером D сгенирировать все размещения длинной от M до N, где M>0 и N>=M.

У тебя очень простая задача. Считай, что лексемы твоего словаря – это цифры D-ричной системы счисления. Просто перебирай все n-значные числа, где n пробегает весь диапазон от M до N

Добавлено 07.10.20, 03:33

Цитата JoeUser @ 06.10.20, 21:30

словарь - 'a','b'
длина - три
найти все размещения из словаря по длине три?

2-ичная система, цифры a и b. n пробегает от 1 до 3:

aaa

aab

aba

abb

baa

bab

bba

bbb

Добавлено 07.10.20, 03:34
P.S. Не думаю, что в std что-то существенно сможет помочь.

Генерация размещений

JoeUser — Tue, 06 Oct 2020 21:30:19 +0000

JoeUser:

Цитата Qraizer @ 06.10.20, 21:13

как из этого безобразия получить словарь

Я привел упрощенный вариант - когда в словаре составляющие - символы. Из них строится "Passphrase".

Скрытый текст

Но словарь может быть и не из символов, а допустим из слов.
Это ничего не меняет! "Мама раму мама мама мама мама мыла раму" - валидный вариант.

Ну давай на примере, чтобы уже было совсем просто:
словарь - 'a','b'
длина - три
найти все размещения из словаря по длине три?
Примеры вразброс:
б
баб
аб
бба
aaa
aa
ба
...

Генерация размещений

Qraizer — Tue, 06 Oct 2020 21:13:29 +0000

Qraizer: Секундочку. Это ж абсолютно другая задача. У тебя не словарь на входе, а набор лексем и правил, как из этого безобразия получить словарь.

Генерация размещений

JoeUser — Tue, 06 Oct 2020 20:53:37 +0000

JoeUser:

Цитата Qraizer @ 06.10.20, 20:25

У тебя в словаре могут быть повторения?

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

Бытовой пример:

Cгенерировать полный вариант набора паролей из алфавита ['a','b'] - длиной, допустим, от 1 до 8. Понятное дело,
если "полный" - то с повторениями. "aaaaa" - валидный набор, к примеру. Твое решение?

ЗЫ: И тут скорее не сам алгоритм интересен, а именно использование возможностей стандартной библиотеки!
Поиск, переборы, перестановки, обмены, срезы ... В общем, всем тем, чем богат #include .

Генерация размещений

Qraizer — Tue, 06 Oct 2020 20:25:38 +0000

Qraizer: У тебя в словаре могут быть повторения?

Добавлено 06.10.20, 20:26
В любом случае повторения легко сводятся к их отсутствию, достаточно лишь добавить к элементам индексы уникальности, учитываемые в сравнениях и игнорируемые в остальных случаях. Т.е. дело лишь за кастомным сравнением и value_type

Генерация размещений

JoeUser — Tue, 06 Oct 2020 18:31:43 +0000

JoeUser: Qraizer, есть нюанс ... с повторениями!
Ломает всю картину моего прекрасного мира :'(

Генерация размещений

Qraizer — Tue, 06 Oct 2020 17:32:42 +0000

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

Генерация размещений

JoeUser — Tue, 06 Oct 2020 15:59:00 +0000

JoeUser:

Цитата OpenGL @ 06.10.20, 14:02

Ты уверен, что тебе нужны именно сочетания, а не размещения?

Ты прав, порядок важен! Да - нужны размещения! Правлю название темы.

Ниже схемка - это так, для памяти :)

Генерация размещений

OpenGL — Tue, 06 Oct 2020 14:02:46 +0000

OpenGL: Ты уверен, что тебе нужны именно сочетания, а не размещения?
Сочетания из n элементов по k с использованием next_permutation получаются при помощи создания вектора из (n - k) нулей и k единиц, т.е. вектора длины n. А дальше как-то так:

{

for(int i = 0; i < n; ++i)

{

// v[i] == 1 означает, что i-ый элемент принадлежит сочетанию

}

} while(std::next_permutation(v.begin(), v.end());

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

Добавлено 06.10.20, 14:11
Или с размещениями лучше вообще вот так. Генерируешь вектор значений ((n - k) нулей, 1, 2, 3, ... k), и переставляешь уже его. На каждой итерации полагаешь, что если v[i] == 0, то i-ый элемент в размещение не входит, иначе он находится на v[i]-ой позиции.

Генерация размещений

JoeUser — Tue, 06 Oct 2020 09:57:25 +0000

JoeUser:

Цитата Wound @ 06.10.20, 09:36

Что такое сочетания ? И чем не подходит std::next_permutation?

Тем, что оно делает перестановки. ~~А сочетание - это немного другое.~~
упс, нужны размещения. :whistle:

Цитата Wound @ 06.10.20, 09:36

Оно же делает перестановки.

Да.

Добавлено 06.10.20, 10:00

Цитата Wound @ 06.10.20, 09:36

А вообще брутфорс по словарю

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

Генерация размещений

Wound — Tue, 06 Oct 2020 09:36:24 +0000

Wound: Что такое сочетания ? И чем не подходит std::next_permutation?
Оно же делает перестановки.

А вообще брутфорс по словарю - это когда ты берешь словарь и начинаешь его перебирать, без всяких перестановок.

Генерация размещений

JoeUser — Tue, 06 Oct 2020 08:22:51 +0000

JoeUser: Всем привет!

В стандартной либе () есть прекрасный механизм работы с перестановками - std::next_permutation.
А есть ли что-либо подобное, удобное для работы с размещениями?

Допустим, к примеру, я хочу реализовать брутфорс по словарю.
И мне нужно из словаря размером D сгенирировать все размещения длинной от M до N, где M>0 и N>=M.