Комбінації 4 значних паролів. Комбінаторика. Генератор поєднань з N по M

Отже, передісторія.

Мені видали нову банківську картку, і я, як водиться, граючи вгадала її пін-код. Але не підряд. У сенсі, скажімо, пін-код був 8794, а я назвала 9748. Тобто, я тріумфально вгадала всі цифри, що містилися у цьому чотиризначному числі. Ну так, не саме число, а просто його складові угадала. Але цифри всі вірні! ПРИМІТКА - я діяла навмання, тобто мені не треба було розставити вже відомі числа в потрібному порядку, я просто діяла в дусі: ось тут є невідомі мені чотири цифри, і я вважаю, що серед них можуть бути 9, 7, 4 і 8, а порядок їх важливий.Ми тут же запитали, скільки у мене взагалі було варіантів(напевно, щоб зрозуміти, наскільки це круто, що я взяла і вгадала). Тобто, з яких комбінацій чотирьох цифр мені потрібно було вибирати? І тут, природно, почалося пекло. У нас весь вечір вибухала голова, і у всіх, зрештою, вийшли абсолютно різні варіанти відповіді! Я навіть почала виписувати всі ці комбінації в блокнот поспіль у міру зростання, але на чотирьох сотнях зрозуміла, що їх більше чотирьох сотень (принаймні це спростувало відповідь фізика Треша, який запевняв мене, що комбінацій чотири сотні, але все одно це не абсолютно однозначно) - і здалася.

Власне, сутність питання.Яка ймовірність вгадування (у будь-якому порядку) чотирьох чисел, що містяться у чотиризначному числі?

Або ні, переформулюємо (я гуманітарій, вибачте, хоча до математики завжди мала велику слабкість), щоб було ясніше і чіткіше. Скільки не повторюванихкомбінацій цифр міститься у ряді порядкових числівників від 0 до 9999? ( будь ласка, не плутайте це з питанням "скільки комбінацій не повторюванихцифр"!!! цифри можуть повторюватись! у сенсі, 2233 і 3322 - це даному випадкуодна і та сама комбінація!!).

Або ще конкретніше. Мені потрібно чотири рази вгадати одну цифру із десяти. Але не підряд.

Ну чи ще якось. Загалом, потрібно дізнатися, скільки я мав варіантів числової комбінації, з якої складався пін-код картки. Допоможіть, люди добрі! Тільки, будь ласка, допомагаючи, не починайте відразу писати, що варіантів цих 9999(вчора таке всім спадало на думку спочатку), тому що це ж дурниці - адже в тому ракурсі, який нас хвилює, число 1234, число 3421, число 4312 і так далі одним і тим самим! Ну і так, цифри можуть повторюватися, адже буває пін-код 1111 або там, наприклад, 0007. Можна уявити замість пін-коду номер машини. Припустимо, яка можливість вгадати всі однозначні цифри, з яких складається номер машини? Або щоб взагалі прибрати теорію ймовірності - зі скількох числових комбінацій мені потрібно було вибрати одну?

Будь ласка, підкріпіть свої відповіді та міркування якими-небудь точними формулами, бо ми вчора й так мало не збожеволіли. Заздалегідь усім дякую!

P.S. Одна розумна людина, програміст, художник і винахідник, щойно дуже правильно підказав правильне вирішення проблеми, подарувавши мені кілька хвилин прекрасного настрою: " розв'язання задачі таке: у неї обсесивно-комп ульсивний розлад, лікування таке: заміж і підгортати помідори. мене б більше на її місці хвилювало не питання «яка ймовірність», а питання «чи згортаючи я звертаю увагу на всі ці цифри»?Загалом, навіть нічого додати:)

Калькулятор нижче призначений для створення всіх поєднань з n по m елементів.
Число таких поєднань, як можна розрахувати за допомогою калькулятора Елементи комбінаторики. Перестановки, розміщення, сполучення.

Опис алгоритму створення під калькулятором.

Алгоритм

Комбінації генеруються у лексикографічному порядку. Алгоритм працює з порядковими індексами елементів множини.
Розглянемо алгоритм з прикладу.
Для простоти викладу розглянемо безліч із п'яти елементів, індекси в якому починаються з 1, а саме, 1 2 3 4 5.
Потрібно згенерувати усі комбінації розміру m = 3.
Спочатку ініціалізується перша комбінація заданого розміру m – індекси в порядку зростання
1 2 3
Далі перевіряється останній елемент, тобто i = 3. Якщо його значення менше n - m + i, він інкрементується на 1.
1 2 4
Знову перевіряється останній елемент, і він інкрементується.
1 2 5
Тепер значення елемента дорівнює максимально можливому: n – m + i = 5 – 3 + 3 = 5, перевіряється попередній елемент з i = 2.
Якщо його значення менше n - m + i, він інкрементується на 1, а всіх наступних його елементів значення прирівнюється до значення попереднього елемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далі знову триває перевірка для i = 3.
1 3 5
Потім – перевірка для i = 2.
1 4 5
Потім настає черга i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
І далі,
2 3 5
2 4 5
3 4 5 - останнє поєднання, тому що всі його елементи дорівнюють n - m + i.

Незважаючи на важливу роль PIN-кодів у світовій інфраструктурі, досі не проводилося академічних досліджень про те, як люди, власне, вибирають PIN-коди.

Дослідники з університету Кембриджу Sören Preibusch та Ross Anderson виправили ситуацію, опублікувавши перший у світі кількісний аналіз складності вгадування 4-циферного банківського PIN-коду.

Використовуючи дані про виток паролів з небанківських джерел та онлайн анкетування, вчені з'ясували, що до вибору PIN-кодів користувачі ставляться набагато серйозніше, ніж до вибору паролів для веб-сайтів: більшість кодів містять майже випадковий набір цифр. Тим не менш, серед вихідних даних присутні і прості комбінації, і дні народження, тобто при деякому везенні зловмисник може просто вгадати заповітний код.

Відправною точкою дослідження був набір 4-циферних послідовностей у паролях з бази RockYou (1.7 млн), та бази з 200 тисяч PIN-кодів від програми блокування екрану iPhone (базу надав розробник програми Daniel Amitay). У графіках, побудованих за цими даними, проступають цікаві закономірності — дати, роки, цифри, що повторюються, і навіть PIN-коди, що закінчуються на 69. На основі цих спостережень вчені побудували лінійну регресійну модель, яка оцінює популярність кожного PIN-коду залежно від 25 факторів, - наприклад, чи є код датою у форматі ДДММ, чи він зростаючою послідовністю, і так далі. Цим загальним умовам відповідають 79% і 93% PIN-кодів у кожному наборі.

Отже, користувачі вибирають 4-циферні коди на основі лише кількох простих факторів. Якби так вибиралися і банківські PIN-коди, 8-9% з них можна було б вгадати лише за три спроби! Але, звичайно, до банківських кодів люди ставляться набагато уважніше. Зважаючи на відсутність скільки-небудь великого набору справжніх банківських даних, дослідники опитали більше 1300 осіб, щоб оцінити, наскільки реальні PIN-коди відрізняються від розглянутих. Враховуючи специфіку дослідження, у респондентів запитували не про самі коди, а лише про їх відповідність якомусь із вищеназваних факторів (зростання, формат ДДММ тощо).

Виявилося, що люди справді набагато ретельніше вибирають банківські PIN-коди. Приблизно чверть опитаних використовують випадковий PIN, згенерований банком. Понад третину вибирають свій PIN-код, використовуючи старий номертелефону, номер студентського квитка, або інший набір цифр, що виглядає випадковим. Згідно з отриманими результатами, 64% власників карток використовують псевдовипадковий PIN-код, - це набагато більше, ніж 23-27% у попередніх експериментах з не-банківськими кодами. Ще 5% використовують цифровий патерн (наприклад, 4545), а 9% віддають перевагу патерну на клавіатурі (наприклад, 2684). Загалом зловмисник із шістьма спробами (три з банкоматом та три з платіжним терміналом) має менше 2% шансів вгадати PIN-код чужої карти.

100 найпопулярніших PIN-кодів

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S.Насправді, зрозуміло, зловмиснику набагато простіше підглянути ваш PIN-код, ніж вгадувати його. Але й від підгляду можна захиститися навіть, здавалося б, у безвихідному становищі: