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

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

⚡ Умное резюме

Алгоритм комбинаций выводит все возможные варианты выбора из r элементов из множества n, где порядок не имеет значения. В этом ресурсе объясняется формула комбинаций, временная сложность, два рекурсивных метода, обработка дубликатов и полный код на языке C. C++ и Python Реализации.

  • 🎯 Определение: Комбинация выбирает r элементов из n элементов, при этом порядок выбора не имеет значения.
  • 🧮 Формула: Число комбинаций равно nCr, что равно n!, деленному на r!(nr)!.
  • 🔁 Метод 1: Рекурсия с фиксированным числом элементов выбирает один элемент, а затем находит комбинации оставшихся r-1 элементов.
  • ➕ Метод 2: Рекурсия с включением и исключением, основанная на тождестве Паскаля, либо использует, либо пропускает каждый элемент.
  • 🇧🇷 Дубликаты: Сортировка или словарь удаляют повторяющиеся комбинации, если входные данные содержат дублирующиеся значения.
Читать

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

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

Например, вам дали сумку пяти разных цветов и попросили создать узор из любых трех цветов. Вы также можете выбрать любые 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 элемента каждый.

Рисунок выше — это возвращаемое значение рекурсии. Будет напечатан только последний слой.

Прозвище Code

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 < r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i <= end && end - i + 1 >= 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 <= end and end - i + 1 >= 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. Элемент исключен из текущей комбинации

Прозвище Code

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 < r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  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);
}
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 >= 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

Использование словаря или неупорядоченной карты для track повторяющихся комбинаций

Итак, если мы не хотим сортировать элементы для tracЧтобы создать копию, мы можем следовать указанным шагам.

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

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

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

Часто задаваемые вопросы (FAQ)

Комбинация — это выборка, в которой порядок не имеет значения, поэтому RGB и BGR считаются одним целым. Перестановка — это расположение, в котором порядок имеет значение, поэтому RGB и BGR считаются двумя целыми. Комбинации используют nCr; перестановки используют nPr.

nCr — это количество способов выбрать r предметов из n предметов, когда порядок не имеет значения. Оно вычисляется как n!, деленное на r!, умноженное на (nr)!. Например, 5C3 равно 10.

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

Инструменты искусственного интеллекта могут генерировать все возможные комбинации набора данных, фильтровать дубликаты и даже предлагать наиболее эффективный метод для больших объемов входных данных. Это экономит время, хотя для проверки правильности подсчета следует сверить его с формулой nCr.

Да. Искусственный интеллект, помогающий программировать, может писать комбинированный код на языке C. C++, Pythonа также другие языки, включая рекурсивные методы и методы включения-исключения. Всегда проверяйте выходные данные и учитывайте граничные случаи, такие как повторяющиеся элементы или r больше n.

Подведем итог этой публикации следующим образом: