Логика для выбора определенного множества из декартова множества

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

Итак, что я хочу, так это иметь возможность сказать, что это набор возможных символов, если я вычислил декартово множество всех возможных комбинаций этого набора до длины n, каково множество в точке x?

Однако я хочу сделать это, не вычисляя весь набор. Я видел подобную логику в одном месте в Интернете, но я не смог обобщить ее, чтобы она соответствовала.

Любая помощь будет фантастической, спасибо! Я свободно говорю на C#, если это поможет.

Изменить: вот вопрос, о котором я упоминал ранее: rq=1">Как выбрать конкретный элемент из декартового произведения без вычисления всех остальных элементов

Изменить: вот пример того, что я имею в виду:

Char set = [abcd]

Length n = 4

Permutations:

[aaaa]
[aaab]
[aaac]
[aaad]
[aaba]
....
[dddd]

Так что, если я ищу набор в 4, я получу [aaad]. Но если я ищу элемент 7000, то мне потребуется много времени, чтобы добраться до этой точки.


c# cartesian-product brute-force set-theory
person Transmission    schedule 08.03.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Это реализует ответ на вопрос, который вы связываете:

static string Get(string chars, int n, int i)
{
    string ret = "";
    int sizes = 1;
    for (int j = 0; j < n; j++) {
        ret = chars[(i / sizes) % chars.Length] + ret;
        sizes *= chars.Length;
    }
    return ret;
}

Пример:

string chars = "abcd";
int n = 3;

for (int i = 0; i < Math.Pow(chars.Length, n); i++)
    Console.WriteLine(i + "\t" + Get(chars, n, i));

0       aaa
1       aab
2       aac
3       aad
...
61      ddb
62      ddc
63      ddd
person Julián Urbano    schedule 08.03.2014
comment
Спасибо за это, это прекрасно, именно то, что я хотел! Я не могу проголосовать за вас, пока у меня не будет 15 представителей, но я отметил вас как правильного, надеюсь, вы согласны? - person Transmission; 08.03.2014
comment
Между прочим, когда я запускаю ваш метод с длиной char 62, n 900000 и i 500 000 000, это занимает около 23 минут, если это разумно, или вы думаете, что я ввел ошибка? - person Transmission; 09.03.2014
comment
@Передача 23 минуты за один вызов метода? - person Julián Urbano; 09.03.2014
comment
Да, я думаю, что задержка возникает из-за использования BigInteger для обработки огромных чисел в игре выше. Не уверен, что есть обходной путь. - person Transmission; 09.03.2014
comment
@Передача, да, похоже. 62 символа для паролей длиной 900000 (кстати, длина 900k! wtf!) дает вам смехотворно большое число, которое, я уверен, компьютер даже не может представить. - person Julián Urbano; 09.03.2014
comment
Ты прав. Мне интересно, должен ли я каким-то образом разбить вычисления на блоки или есть вероятность, что я мог бы сгенерировать требуемые огромные числа, затем прочитать их в массив целых чисел или что-то подобное и выполнить какую-то дискретную логику FSA? - person Transmission; 09.03.2014