Алгоритм комбинирования: выведите все возможные комбинации R

Автор: Сара Чен Сара Чен
Hours обновлено

Что такое комбинация?

Комбинация – это своего рода расположение некоторых данных объектов. Говоря математическим языком, Комбинация — это набор вариантов/выбор предметов из уникального набора предметов/объектов. Здесь порядок элементов не имеет значения. Он также известен как метод расчета общего результата события, при котором порядок результата не имеет значения.

Например, вам дали сумку пяти разных цветов и попросили создать узор из любых трех цветов. Вы также можете выбрать любые 5 цвета из 3, а затем расположить их в разном порядке.

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

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

Сочетание цветов
Сочетание цветов

Объяснение:

  • Возьмите любые 4 цвета из 5 и перечислите их.
  • Из каждого блока из 4 цветов выберите любые 3 и перечислите их все. Например, на рисунке мы выбрали только «RGBI» и показали 4 комбинации.
  • За этим стоит теория, позволяющая подсчитать общее количество комбинаций, которые мы можем составить. Комбинацию r элементов из n можно математически представить как:
Формула сочетания

Формула сочетания

Знак «!» означает факториал, Например,
Н! = Н * (Н-1) * (Н-2) *… * 3 * 2 * 1
Скажем, 5! = 5*4*3*2*1 = 120

Итак, для нашей вышеуказанной задачи у нас есть 5 цветов, что означает n = 5, и в любой момент времени нам нужно выбрать любые 3. Итак, r = 3. После вычислений мы получаем:

Сочетание

Всего для приведенного выше сценария возможно 10 цветовых комбинаций.

Анализ временной сложности для комбинации

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

Если дан массив размера n, то он займет O(n2) время на выполнение задания. Кроме того, если мы хотим удалить повторяющуюся запись, тогда

Нам необходимо выполнить следующие шаги:

Шаг 1) Сортируем входной массив данных по возрастанию. Временная сложность сортировки составляет О(п*лог(п)).

Шаг 2) Создайте еще один массив, содержащий уникальный элемент из данных временного массива.

Шаг 3) Затем выполните функцию комбинирования.

Таким образом, общая временная сложность становится = На2) + O(nLog(n)). Мы можем считать это O(n2), как n2 намного больше, чем n*log(n).

Метод-1: фиксированный элемент с рекурсией

В этом методе мы выбираем элемент, а затем находим комбинацию элементов r-1. Когда мы выбираем элемент из остальной части элемента, мы делаем это рекурсивно, и поэтому это называется фиксированным элементом и рекурсией.

Продемонстрируем алгоритм пошагово на схеме:

Фиксированный элемент с рекурсией

Шаги приведены ниже:

Шаг 1) В первом слое возьмите n-r+1 элементов. То есть мы взяли 3 элемента.

Шаг 2) Выберите элемент второго слоя и поднимите его до номера. Итак, если мы возьмем «R», то вместе с R мы сможем взять G, Y и B.

Шаг 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)

Итак, для рекурсивного алгоритма будет две рекурсивные логики для поиска комбинации из r элементов из заданного массива размера n.

  1. Элемент включен в текущую Комбинацию
  2. Элемент исключен из текущей комбинации

Псевдокод

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). Итак, если вы используете словарь, то общая временная сложность выполнения кода будет:

О(1) + О(п*п)

Эквивалент O(n*n).

Используя предыдущий метод для отслеживания дубликатов, нам нужно O(n*log(n)) для сортировки; для сравнения нам нужно O(n), а сама функция занимает O(n*n). Общая временная сложность будет:

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