Алгоритм поєднання: Вивести всі можливі комбінації R

Що таке комбінація?

Комбінація - це своєрідне розташування деяких заданих об'єктів. З математичної точки зору, Комбінація – це набір варіантів/вибору предметів з унікального набору предметів/об’єктів. Тут порядок елементів не має значення. Він також відомий як метод обчислення загального результату події, де порядок результатів не має значення.

Наприклад, вам дали сумку 5 різних кольорів і попросили створити візерунок із будь-яких 3 кольорів. Ви також можете вибрати будь-які 3 кольори з 4, а потім розташувати їх у різному порядку.

Припустімо, що кольори RGYBI(R= червоний, G= зелений, Y= жовтий, B= синій, I= індиго). Отже, можливий шаблон може бути RGB, RGY тощо.

Давайте подивимося на наступний малюнок:

Пояснення:

Візьміть будь-які 4 кольори з 5 і перелічіть їх
З кожного блоку з 4 кольорами виберіть будь-які 3 і перерахуйте їх усі. Наприклад, ми вибрали лише «RGBI» на малюнку та показали 4 комбінації.
За цим стоїть теорія, яка обчислює загальну кількість комбінацій, які ми можемо створити. Комбінацію r елементів із n можна математично представити як:

Знак "!" означає Факторіал, Наприклад,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Скажи, 5! = 5*4*3*2*1 = 120

Отже, для нашої вищезазначеної задачі ми маємо 5 кольорів, що означає n = 5, і в будь-який момент часу нам потрібно вибрати будь-які 3. Отже, r = 3. Після обчислення ми отримуємо,

Для вищевказаного сценарію можливе всього 10 комбінацій кольорів.

Аналіз часової складності для Комбінації

Тепер, скажімо, задано масив розміром n, нас просять взяти r елементів із масиву та виконати комбінації r елементів.

Якщо задано масив розміром n, він займе O(n²) час на виконання завдання. Крім того, якщо ми хочемо видалити повторюваний запис, тоді,

Нам потрібно виконати наступні дії:

Крок 1) Відсортувати дані вхідного масиву за зростанням. Часова складність сортування O(n*log(n)).

Крок 2) Створіть ще один масив, що містить унікальний елемент із заданих даних тимчасового масиву.

Крок 3) Потім виконайте функцію комбінування.

Отже, загальна часова складність стає = О (н.)²) + O(nLog(n)). Ми можемо вважати це O(n²), як п²набагато більше, ніж n*log(n).

Метод 1: фіксований елемент із рекурсією

У цьому методі ми виберемо елемент, а потім знайдемо комбінацію елементів r-1. Оскільки ми вибираємо елемент із решти елемента, ми робимо рекурсивно, і тому це називається фіксованим елементом і рекурсією.

Продемонструємо крок за кроком алгоритм за допомогою схеми:

Кроки наведені нижче:

Крок 1) У першому шарі візьміть n-r+1 елементів. Тобто ми взяли 3 елементи.

Крок 2) Виберіть елемент із 2-го шару та перенесіть його до nr. Отже, якщо ми візьмемо «R», то з R ми можемо взяти G, Y і B.

Крок 3) Виберіть елемент із 3-го шару та піднесіть його до n-го елемента та сформуйте блоки, що містять 3 елементи кожен.

Цифра вище є значенням, що повертається рекурсією. Буде надруковано лише останній шар.

Псевдокодекс

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

Реалізація на C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

вихід:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Реалізація в Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

вихід:

R G Y 
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Спосіб 2 (включити та виключити кожен елемент)

Цей метод заснований на тотожності Паскаля. Раніше ми використовували рекурсію для обчислення nCr. Тут метод просто розділений замість складного циклу.

Відповідно до особистості Паскаля,

nCr = (n-1)Cr + (n-1)C(r-1)

Отже, буде 2 рекурсивні логіки для рекурсивного алгоритму, щоб знайти комбінацію r елементів із заданого масиву розміром n.

Елемент включено в поточну комбінацію
Елемент виключено з поточної комбінації

Псевдокодекс

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

Реалізація на C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

вихід:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Реалізація в Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

вихід:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

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

Іноді у вхідному масиві можуть бути повторювані елементи.

Наприклад,

Вхідний масив містить n = {5, 2, 3, 1, 5}.
Тут ми бачимо, що 5 присутнє 2 рази.
Тепер, якщо ми хочемо запустити код для цього масиву, деякі комбінації будуть повторені.
Ми знайдемо {5, 2, 5}, {5, 2, 3} тощо або будь-яку комбінацію, яка містить 5, буде повторено.

Ми можемо використовувати ці два методи:

Відсортуйте вхідний масив. Сортування займе O(nlog(n)) часу.
Потім збільште значення i, тоді як значення i та i+1 однакові. По суті, помістіть наступні два рядки коду у функцію Combination.

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

Використання словника або невпорядкованої карти для відстеження повторюваних комбінацій

Отже, якщо ми не хочемо сортувати елементи для відстеження дубліката, ми можемо виконати наведені кроки.

Крок 1) Оголосити глобальний словник або хеш-карту.
Крок 2) Перемістіть згенеровану комбінацію на хеш-карту та збільште значення на одиницю. Комбінація є ключем, а їх виникнення є значеннями.
Крок 3) коли функція завершить роботу, ми просто надрукуємо всі ключі з хеш-карти або словника.

Ось реалізація на python

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

вихід:

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

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

Тепер, якщо ви напишете «print(unique_combination)», ви побачите частоту кожної комбінації. Це буде показано так:

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

Отже, ми бачимо, що RGB, RYB, GYB відбулися 2 рази. Часова складність вставки ключа до словника в основному становить O(1). Отже, якщо ви використовуєте словник, то загальна складність часу для виконання коду буде:

O(1) + O(n*n)

Еквівалент O(n*n).

Використовуючи попередній метод для відстеження дублікатів, нам потрібно O(n*log(n)) для сортування; для порівняння нам потрібно O(n), а сама функція приймає O(n*n). Загальна трудомісткість становитиме:

O(n*log(n)) + O(n) +O(n*n)

Вам може сподобатися:

Що таке комбінація?

Аналіз часової складності для Комбінації

Метод 1: фіксований елемент із рекурсією

Псевдокодекс

Реалізація на C/C++

Реалізація в Python

СТАТТІ ПО ТЕМІ

Спосіб 2 (включити та виключити кожен елемент)

Псевдокодекс

Реалізація на C/C++

Реалізація в Python

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

Використання словника або невпорядкованої карти для відстеження повторюваних комбінацій

Ось реалізація на python