1.3: Комбінації та перестановки

Приклад \(\PageIndex\) Скільки результатів можливо, коли три кістки кидаються, якщо жодна з них не може бути однаковою? Перші дві кістки разом мають \(6\cdot 5=30 \) можливі результати, зверху. Для кожного з цих 30 результатів, є чотири можливі результати для третього померти, так що загальна кількість результатів є \(30\cdot 4=6\cdot 5\cdot 4=120\) . (Зверніть увагу, що ми вважаємо кістки помітними, тобто кидок 6, 4, 1 відрізняється від 4, 6, 1, тому що перший і другий кубики різні в двох кидках, хоча цифри в наборі однакові.)

Приклад \(\PageIndex<2>\) Припустимо, блоки під номером 1 через \(n \) знаходяться в бочці; ми витягуємо \(k \) з них, поміщаючи їх в лінію, як ми робимо. Скільки можливих результатів? Тобто, скільки різних домовленостей \(k \) блоків ми можемо побачити? Це, по суті, те саме, що і в попередньому прикладі: є \(k \) «плями», які потрібно заповнити блоками. Будь-який з \(n \) блоків може з’явитися першим у рядку; потім наступний \(n-1 \) може з’явитися будь-який з решти і так далі. Кількість результатів \(n(n-1)(n-2)\cdots(n-k+1)\) , таким чином, за принципом множення. У попередньому прикладі першим «плямою» було вмирати номер один, друге місце було вмирати номер два, третє місце померти номер три, і \(6\cdot5\cdot4=6(6-1)(6-2)\) ; зверніть увагу, що \(6-2=6-3+1\) .

Визначення \(\PageIndex<1>\) : Permutations Кількість перестановок \(n \) речей, зроблених за \(k \) один раз, становить \[(P(n,k)=n(n-1)(n-2)\cdots(n-k+1)=.\nonumber \] Перестановка деяких об’єктів є певним лінійним упорядкуванням об’єктів; по \(P(n,k) \) суті підраховує дві речі одночасно: кількість способів вибору та порядку \(k \) з \(n \) об’єктів. Корисним особливим випадком є \(k=n\) , в якому ми просто підраховуємо кількість способів впорядкування всіх \(n \) об’єктів. Це і є \(n(n-1)\cdots(n-n+1)=n!\) . Зверніть увагу, що друга форма \(P(n,k) \) з визначення дає \[\frac=\frac.\nonumber\] Це правильно тільки в тому випадку \(0!=1\) , якщо, тому ми приймаємо стандартну конвенцію, що це правда, тобто ми \(0! \) визначаємо бути \(1\) .

Припустимо, ми хочемо порахувати тільки кількість способів вибору \(k \) елементів з \(n\) , тобто нас не хвилює порядок. У прикладі \(\PageIndex\) ми підрахували кількість кидків з трьох кубиків з різними цифрами, показаними. Кістки були помітні, або в певному порядку: перша вмирає, друга і третя. Тепер ми хочемо просто порахувати, скільки комбінацій чисел є, з 6, 4, 1 тепер вважається такою ж комбінацією, як 4, 6, 1.

Приклад \(\PageIndex<3>\) Припустимо, ми повинні були перерахувати всі 120 можливостей у прикладі \(\PageIndex\) . Список містить багато результатів, які ми зараз хочемо вважати єдиним результатом; 6, 4, 1 і 4, 6, 1 були б у списку, але не повинні враховуватися окремо. Скільки разів буде з’являтися один результат у списку? Це проблема перестановки: є \(3! \) порядки, в яких можуть з’явитися 1, 4, 6, і всі 6 з них будуть в списку. Фактично кожен результат буде з’являтися в списку 6 разів, так як кожен результат може з’являтися в \(3! \) замовленнях. Отже, список занадто великий на 6 разів; правильний підрахунок для нової проблеми є \(120/6=20\) .

Дотримуючись тих самих міркувань загалом, якщо у нас є \(n \) об’єкти, кількість способів їх вибору \(k \) є \(P(n,k)/k!\) , оскільки кожна колекція \(k \) об’єктів буде підрахована \(k! \) раз \(P(n,k)\) .

Визначення \(\PageIndex<2>\) : Permutations Кількість підмножин розміру набору \(k \) розміру \(n \) (також називається \(n\) -set) є \[C(n,k)=\frac=\frac=.\nonumber\] Позначення \(C(n,k) \) використовується рідко; замість цього ми використовуємо \(n\choose k\) , вимовляється ” \(n \) вибрати \(k\) ».

Приклад \(\PageIndex\) Розглянемо \(n=0,1,2,3\) . Легко перерахувати підмножини невеликого \(n\) -set; типовим \(n\) -set є \(\\) . \(0\) -set, а саме порожній набір, має одну підмножину, порожню множину; \(1\) -subset має дві підмножини, порожній набір і \(\\) ; a \(2\) -subset має чотири підмножини \(\emptyset\) \(\\) , \(\\) ,, \(\\) ; і \(3\) -subset має вісім: \(\emptyset\) , \(\\) , \(\\) , \(\\) , \(\\) \(\\) , \(\\) , \(\\) . З цих списків потім легко обчислити \(n\choose k\) : \[\displaylines$>>\cr &0\cr n&1\cr &2\cr &3\cr >\left\vert \matrix< 0&\lower 3.5pt\hbox<>\rlap>>1&2&3\cr 1\cr 1&1\cr 1&2&1\cr 1&3&3&1\cr >\right.\cr>\nonumber\]

Ви, напевно, дізнаєтеся ці цифри: це початок трикутника Паскаля. Кожен запис у трикутнику Паскаля генерується шляхом додавання двох записів з попереднього рядка: тієї, що безпосередньо зверху, та тієї, що зверху та ліворуч. Це говорить про те \(=+\) , і дійсно це правда. Щоб зробити цю роботу акуратно, ми приймаємо конвенцію, що \(=0 \) коли \(k< 0 \) або \(k>n\) .

Теорема \(\PageIndex\) \(=+\) . Доказ Типовий \(n\) -набір є \(A=\\) . Розглянуто два типи підмножин: ті, які містять \(a_n \) і ті, які не містять. Якщо \(k\) -subset \(A \) не містить \(a_n\) , то це \(k\) -підмножина \(\\>\) , і є \(n-1\choose k \) з них. Якщо він містить \(a_n\) , то він складається з \(a_n \) і \(k-1 \) елементів \(\\>\) ; оскільки є з \(n-1\choose k-1 \) них, є \(n-1\choose k-1 \) підмножини цього типу. Таким чином, загальна кількість \(k\) -підмножин \(A \) є \(+\) . Зверніть увагу \(k=0\) , що коли \(==0\) , і коли \(k=n\) \(==0\) , так що \(= \) і \(=\) . Ці значення є граничними в трикутнику Паскаля.

Багато проблем з підрахунком покладаються на такі міркування, які ми бачили. Ось кілька варіацій на тему.

Приклад \(\PageIndex<5>\) Шість людей повинні сидіти за круглим столом; скільки там розсадження? Рішення Незрозуміло, що саме ми маємо на увазі розраховувати тут. Якщо є «спеціальне сидіння», наприклад, може мати значення, хто опиниться на цьому сидінні. Якщо це не має значення, ми дбаємо лише про відносне положення кожної людини. Тоді може мати значення, чи не має значення, чи знаходиться певна людина зліва чи праворуч від іншого. Так що це питання можна трактувати (принаймні) трьома способами. Давайте відповімо на них усім. По-перше, якщо власне крісла, зайняті людьми, мають значення, то це точно так само, як підкладка шість осіб поспіль: 6 варіантів для сидіння номер один, 5 для сидіння два і так далі, в цілому \(6!\) . Якщо стільці не мають значення, то \(6! \) розраховує одне і те ж розташування занадто багато разів, один раз для кожної людини, яка може бути на одному місці. Так що підсумок в даному випадку є \(6!/6=5!\) . Інший підхід до цього: оскільки фактичні місця не мають значення, просто покладіть одного з шести людей у крісло. Потім потрібно розташувати решту 5 осіб поспіль, що можна зробити \(5! \) способами. Нарешті, припустимо, все, що нас хвилює, це хто поруч з ким, ігноруючи правого і лівого. Потім попередня відповідь підраховує кожну композицію двічі, один раз для порядку проти годинникової стрілки і один раз за годинниковою стрілкою. Отже, загальна сума є \(5!/2=P(5,3)\) .

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

Приклад \(\PageIndex<6>\) Скільки способів існує, щоб вибудувати шість людей, щоб конкретна пара людей не була сусідньою? Рішення Позначають народ \(A \) і \(B\) . Загальна кількість замовлень є \(6!\) , але це враховує ті замовлення з \(A \) і \(B \) поруч один з одним. Скільки їх там? Подумайте про цих двох людей як про одиницю; скільки способів є, щоб \(AB \) вирівняти блок з іншими 4 людьми? У нас є 5 пунктів, тому відповідь є \(5!\) . Кожен з цих порядків відповідає двом різним порядкам, в яких \(A \) і \(B \) є суміжними, залежно від того, \(A \) чи \(B \) є першим. Отже, \(6! \) кількість занадто висока, \(2\cdot5! \) і кількість, яку ми шукаємо, є \(6!-2\cdot 5!=4\cdot5!\) .

Дописувачі та атрибуція

Pairwise testing. Що таке попарне тестування: відкриваємо таємницю

Попарне тестування (pairwise testing) – це метод тестування програмного забезпечення, який використовується для зменшення кількості тестових сценаріїв з мінімальним втручанням у якість. Уявіть, що у нас є декілька взаємодіючих функцій або параметрів, і ми хочемо перевірити їхню взаємодію. Відповідно, попарне тестування полягає в перевірці всіх можливих комбінацій значень двох параметрів одночасно.

Застосовуючи попарне тестування, ми спрощуємо процес тестування та зменшуємо кількість тестових сценаріїв, що забезпечує швидке тестування без значного впливу на якість. Далі ми розглянемо приклад попарного тестування.

Попарне тестування проти потрійного та більш складних комбінацій

При виборі методу тестування важливо розуміти, чому саме попарне тестування так популярне та чому інші методи, як-от потрійне або більш складні комбінації, не застосовуються так широко.

Ефективність попарного тестування

Одна з основних переваг попарного тестування полягає в його ефективності. Згідно з дослідженнями, більшість помилок в програмному забезпеченні зазвичай знаходяться в межах взаємодії двох компонентів. Тобто, попарне тестування дозволяє виявити значну кількість помилок, використовуючи меншу кількість тестових випадків, порівняно з більш складними комбінаціями.

Економія часу та ресурсів

Попарне тестування значно економить час та ресурси, оскільки кількість тестових випадків зменшується порівняно з потрійним або більш складними комбінаціями. Чим більше параметрів включається у тестування, тим більше тестових випадків потрібно створити та виконати. Внаслідок цього, збільшення кількості комбінацій призводить до збільшення часу та витрат на тестування.

Співвідношення вартості та якості

Застосування попарного тестування забезпечує оптимальне співвідношення вартості та якості. Це означає, що використання попарного тестування дозволяє досягти високого рівня якості програмного забезпечення з меншими витратами порівняно з іншими методами.

Менша складність тестування

При попарному тестуванні створення та аналіз тестових сценаріїв є менш складним, ніж при використанні потрійного чи більш складних комбінацій. Тестувальники можуть швидше розробити та оцінити тестові випадки, спрощуючи процес тестування. Більш того, це дозволяє зосередитися на взаємодії між компонентами, де імовірність знаходження помилок найвища.

Потрійне та більш складні комбінації можуть бути застосовані в окремих випадках, коли вимоги до якості програмного забезпечення є дуже високими, або коли досвід показує, що значна кількість помилок знаходиться в межах взаємодії трьох та більше компонентів. Однак, в загальному випадку, попарне тестування вважається найефективнішим методом тестування, який забезпечує оптимальне співвідношення вартості та якості програмного забезпечення.

Приклади pairwise testing

Давайте на прикладах розберемо, як ми можемо використовувати попарне тестування.

Приклад №1. Веб-додаток замовлення їжі

Припустимо, що ми маємо веб-додаток для замовлення їжі, який пропонує різні опції для користувача. Ці опції включають:

1. Тип кухні (українська, італійська, японська).
2. Спосіб доставки (кур’єр, самовивіз).
3. Оплата (готівкою, картою).

Всього ми маємо 12 можливих комбінацій, що можуть виникнути при взаємодії цих параметрів. Проте, застосування попарного тестування дозволяє зменшити кількість тестових випадків без втрати якості перевірки.

Спочатку створимо таблицю попарних комбінацій:

Застосування попарного тестування дозволяє зменшити кількість тестових випадків з 12 до 6, але при цьому досить ефективно перевіряє взаємодію параметрів. Це дозволяє заощадити час та ресурси на проведення тестування, а також спрощує аналіз отриманих результатів.

Приклад №2. Тестування мобільного додатку відеозвʼязку

Розглянемо приклад мобільного додатку для відеозв’язку, який має наступні налаштування:

1. Роздільна здатність відео (720p, 1080p, 4K).
2. Ступінь стиснення (високий, середній, низький).
3. Звук (увімкнено, вимкнено).

Враховуючи ці параметри, ми маємо 18 можливих комбінацій. Однак застосування попарного тестування дозволяє зменшити кількість тестових випадків, не втрачаючи якості перевірки.

Створимо таблицю попарних комбінацій:

Застосування попарного тестування зменшило кількість тестових випадків з 18 до 9, одночасно забезпечуючи ефективну перевірку взаємодії параметрів. Це дозволяє заощадити час та ресурси на проведення тестування, а також спрощує аналіз отриманих результатів.

Алгоритм тестування: вибір правильної стратегії

При застосуванні попарного тестування важливо вибрати правильний алгоритм тестування, що буде генерувати тестові сценарії. Існує декілька алгоритмів, які можуть бути використані, такі як ортогональні масиви, та графові алгоритми.

Ортогональні масиви генерують тестові сценарії, які оптимально покривають простір параметрів, гарантуючи високу якість тестування з мінімальною кількістю тестів. Ін-тайференс є евристичним підходом, який генерує тестові сценарії на основі набору вхідних даних. Графові алгоритми, зокрема алгоритм А*, використовуються для розв’язання задачі генерації тестових сценаріїв на основі графових моделей.

Недоліки попарного тестування: все має свою ціну

Попарне тестування, хоч і ефективне в більшості ситуацій, має деякі недоліки. По-перше, цей метод не підходить для тестування взаємодії більш ніж двох параметрів. Це може призвести до того, що деякі помилки не будуть виявлені.

По-друге, попарне тестування може бути неефективним для тестування систем з великою кількістю параметрів. У таких випадках може знадобитися використання інших методів, таких як тестування з покриттям тверджень або мутаційне тестування.

Інструменти для попарного тестування: обираємо найкраще

Існує багато інструментів, які допоможуть вам застосовувати попарне тестуванання у вашому проекті. Деякі з них включають:

1. Pict – безкоштовний інструмент від Microsoft, який дозволяє генерувати тестові сценарії на основі моделі введення, заданої користувачем. Pict підтримує різні алгоритми тестування та має зручний синтаксис для опису моделі.
2. AllPairs – інший безкоштовний інструмент для попарного тестування, який працює з текстовими файлами і генерує комбінації вхідних даних для тестування.
3. Hexawise – комерційний інструмент для попарного тестування, який пропонує широкий спектр функцій, включаючи генерацію тестових сценаріїв, візуалізацію результатів тестування та інтеграцію з системами керування випробуваннями.
4. ACTS – інструмент від NIST (Національний інститут стандартів та технологій США), який допомагає генерувати попарні тестові сценарії та підтримує розширені методи тестування, такі як n-штрихове тестування.

Підводячи підсумки: чи варто використовувати попарне тестування?

Попарне тестування є ефективним методом тестування програмного забезпечення, який дозволяє зменшити кількість тестових сценаріїв без втрати якості. Цей метод підходить для тестування взаємодії двох параметрів і може бути використаний у різних областях, від веб-додатків до систем реального часу.

Проте, попарне тестування має деякі недоліки, які варто враховувати. Воно не підходить для тестування взаємодії більш ніж двох параметрів.

Навчитись всім методам та нюансам тестування ви зможете на наших курсах QA.