Как найти количество возможных вариантов паролей

На этой странице вы узнаете

• Как и для чего информатика использует целый раздел математики?
• Как работают безопасные пароли?
• Зачем считать, если можно не считать? 

Что общего у автомобильного номера, карточной игры и расписания школьных занятий? Наука, их изучающая, — комбинаторика. 

Применение комбинаторики

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

Что может служить примерами таких данных?

• автомобильные номера — набор букв и цифр в определенном порядке;
• карточные игры — наборы карт, которые могут находиться у вас на руках;
• расписание занятий — варианты порядка проведения уроков. 

Собственно, комбинаторика может помочь нам:

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

Размещения и перестановки

Самое простое, с чем нам может помочь комбинаторика — это подсчет комбинаций элементов, от которого мы сможем отталкиваться дальше. Для удобства различают два основных вида расположения элементов в последовательностях:

• Размещения — элементы набора могут использоваться в последовательности определенной длины любое количество раз (в том числе ни разу).

Пример: кодовый замок. Никто не запретит нам использовать любую цифру любое количество раз или не использовать совсем.

• Перестановки — возможные последовательности образуются изменением порядка следования элементов друг за другом. Каждый элемент набора используется ровно 1 раз.

Пример: распределение 5 человек на дежурства в течение 5 дней. Было бы справедливо, если бы один человек дежурил только один раз, но вот в какой из дней — уже есть выбор.

Подсчет количества комбинаций

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

В размещениях каждый элемент может быть на любой позиции и может встретиться любое количество раз. То есть на каждой из k позиций может быть любой из n символов, тогда всего размещений может быть N=n^k.

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

• На первой позиции может стоять любой из n символов;
• На второй — любой из оставшихся n − 1 символов;
• На третьей — любой из еще не использовавшихся, то есть n − 2;
• В конце концов — на самой последней позиции может использоваться только 1 оставшийся символ.

Поэтому количество комбинаций перестановок рассчитывается как факториал количества символов: произведение всех чисел от 1 до количества.

В остальных случаях — составляем выражение согласно требованиям:

• Считаем, какое количество символов может находиться на каждой позиции.
• Перемножаем полученные значения.

Например, мы выбираем пароль по следующим условиям:

• длина пароля — 6 символов;
• используются только символы “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”;
• “Р” должен быть на первом месте и больше не встречаться в пароле;
• “3” должен быть на последнем месте и больше не встречаться в пароле.

Определим, какие символы на каких позициях могут находиться:

Теперь можем составить выражение, чтобы найти количество всех возможных вариантов пароля. Перемножим количество возможных символов на каждой позиции:

N = 1 * 8 * 8 * 8 * 8 * 1 = 4096.

Размещения и перестановки в программе Python

Для облегчения работы с ними в Python существует модуль itertools, который содержит инструменты для их создания:

• permutations(набор символов) — создает перестановки переданного набора

---

from itertools import permutations
for i in permutations(“abc”):
    print(i)

Вывод:
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

---

• product(набор символов, repeat = длина последовательности) — создает размещения заданной длины из заданного набора символов

---

from itertools import product
for i in product("abcd", repeat = 2):
    print(i)

Вывод:
('a', 'a')
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'a')
('b', 'b')
('b', 'c')
('b', 'd')
('c', 'a')
('c', 'b')
('c', 'c')
('c', 'd')
('d', 'a')
('d', 'b')
('d', 'c')
('d', 'd')

---

Все комбинации будут возвращены в виде списка символов.

Пример.

Допустим, мы будем составлять пароли длиной 6 символов из того же набора символов “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”, но с дополненными условиями:

• символ “Р” может использоваться в пароле любое количество раз, но обязательно должен быть на первом месте;
• символ “3” должен быть использован в пароле ровно 3 раза;
• в пароле не должно быть сочетания “123”.

Пошагово наш код должен состоять из следующих элементов:

1. Для создания всех вариаций пароля будем использовать product модуля itertools, все пароли будем перебирать циклом for. Также предварительно создадим переменную-счетчик подходящих паролей.
2. Нам нужно проверить все условия задачи. Элемент комбинации с индексом 0 равен “Р”, “3” встречается в ней ровно 3 раза, а также в списке символов комбинации не должно быть набора (“1”, “2”, “3”).
3. При нахождении подходящего пароля будем увеличивать наш счетчик на 1, в конце программы выведем его значение на экран.

---

from itertools import product

cnt = 0
for i in product("PASWORD123", repeat = 6):
    if i[0] == "P" and i.count("3") == 3 and ("1", "2", "3") not in i:
        cnt += 1
print(cnt)

Вывод: 810

---

Фактчек

• Размещения — наборы последовательностей определенной длины, состоящие из определенных символов, которые могут встречаться в последовательности сколько угодно раз. Количество размещений N зависит от длины последовательности k и количества символов n как N=n^k.
• Перестановки — наборы последовательностей, отличающиеся только порядком следования символов друг за другом. Количество перестановок N зависит от количества символов в них n как N = n!.
• В общем виде количество комбинаций высчитывается как произведение количества возможных символов на каждой позиции.
• Для записи перестановок в Python используется permutations из модуля itertools, для записи размещений — product из того же модуля.

Проверь себя

Задание 1.
Сколько будет размещений длинной 5, состоящих из набора “123”?

1. 243
2. 125
3. 120
4. 6

Задание 2.
Что такое перестановки?

1. Комбинации, состоящие из символов определенного набора, разной длины.
2. Комбинации, состоящие из символов определенного набора, одной длины.
3. Комбинации, состоящие из символов определенного набора и отличающиеся только порядком следования символов друг за другом.
4. Комбинации, состоящие из символов определенного набора и отличающиеся только длиной.

Задание 3.
Сколько может быть паролей длиной 4, состоящих из набора символов “ПАРОЛЬ”, в которых любой символ может использоваться сколько угодно раз, кроме “Ь” (используется только один раз и только на последнем месте)?

1. 15
2. 20
3. 125
4. 625

Задание 4.
Какая из записей на языке Python создаст размещения набора “ПАРОЛЬ” длинной 4?

1. itertools(“ПАРОЛЬ”, repeat = 4)
2. product(4, repeat = “ПАРОЛЬ”)
3. permutations(“ПАРОЛЬ”, repeat = 4)
4. product(“ПАРОЛЬ”, repeat = 4)

Ответы: 1. — 1; 2. — 3; 3. — 3; 4. — 4.

Здравствуйте, уважаемые профессионалы и знатоки! Совсем сломала голову над задачей, которая на первый взгляд мне показалось совсем не сложной, а может уже просто заучилась ))
Дан известный набор символов из n элементов в определенном порядке, например возьмем английский алфавит – 26 символов: a b c … x y z.
Имеется пароль который состоит из этих символов. Пароль соответствует след. условиям:
1) Пароль не имеет фиксированной длинны, может быть как 1 символ, так и несколько десятков, но символы не могут повторяться.
2) Символы в пароле идут в том же порядке, в котором они расположены в наборе, только в обратном )))))
3) Символы не могут быть соседними в наборе.

Используя все вышеуказанное, пароль может быть: z, g, z x v, x k c a и т.п., вариантов типа a s y, z y, b b a и т.п. быть не может. Это все что до меня “дошло” ))) ну и то, что максимальная длинна пароля для данного набора символов: 13 (z x v t r p n l j h f d b), а нужно как-то посчитать кол-во возможных вариантов и составить алгоритм получения этих вариантов.

Буду рада любой подсказке, идее или мысли ))