Алгоритъм за комбиниране: Отпечатайте всички възможни комбинации от R

по: Сара Чен Сара Чен
Hours Обновено

Какво представлява комбинацията?

Комбинацията е вид подреждане на дадени обекти. От гледна точка на математиката, комбинацията е набор от избори/избор на елементи от уникален набор от елементи/обекти. Тук редът на елементите няма значение. Известен е също като метод за изчисляване на общия резултат от събитие, където редът на резултата няма значение.

Например, дадена ви е чанта с 5 различни цвята и ви се иска да генерирате модел с произволни 3 цвята. Можете също така да изберете произволни 3 цвята от 4, след което да ги подредите в различен ред.

Да приемем, че цветовете са RGYBI(R= червено, G= зелено, Y= жълто, B= синьо, I= индиго). Така че възможният модел може да бъде RGB, RGY и т.н.

Нека да разгледаме следната фигура:

Комбинация от цветове
Комбинация от цветове

Обяснение:

  • Вземете произволни 4 цвята от 5 и ги избройте
  • От всеки блок от 4 цвята, изберете произволни 3 и ги избройте всички. Например, избрахме само „RGBI“ на фигурата и показахме 4 комбинации.
  • Зад това има теория за изчисляване на общия брой комбинации, които можем да направим. Комбинация от r елемента от 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(n2) време за изпълнение на задачата. Освен това, ако искаме да премахнем дублиращия се запис, тогава,

Трябва да изпълним следните стъпки:

Стъпка 1) Сортирайте данните от входния масив във възходящ ред. Времевата сложност на сортирането е O(n*log(n)).

Стъпка 2) Създайте друг масив, съдържащ уникален елемент от дадените данни за временен масив.

Стъпка 3) След това изпълнете комбинираната функция.

Така общата времева сложност става = O(n2) + O(nLog(n)). Можем да го считаме за O(n2), както n2 е много по-голямо от n*log(n).

Метод-1: Фиксиран елемент с рекурсия

В този метод ще изберем елемент, след което ще намерим комбинация от r-1 елементи. Докато избираме елемент от останалия елемент, ние правим рекурсивно и затова се нарича фиксиран елемент и рекурсия.

Нека демонстрираме алгоритъма стъпка по стъпка с диаграма:

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

Стъпките са дадени по-долу:

Стъпка 1) В първия слой вземете n-r+1 елемента. Това означава, че взехме 3 елемента.

Стъпка 2) Изберете елемент от 2-ри слой и го заведете до nr. Така че, ако вземем „R“, тогава с R можем да вземем G, Y и B.

Стъпка 3) Изберете елемент от 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 & 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.

  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 & 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 стойността са еднакви. По принцип поставете следните два реда код във функцията за комбиниране.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Използване на речник или неподредена карта за track дублиращи се комбинации

Така че, ако не искаме да сортираме елементите за tracкралят на дубликата, можем да следваме дадените стъпки.

Стъпка 1) Декларирайте глобален речник или hashmap.
Стъпка 2) Натиснете генерираната комбинация към hashmap и увеличете стойността с единица. Комбинацията е ключът, а тяхното появяване са стойности.
Стъпка 3) когато функцията приключи, просто ще отпечатаме всички ключове от hashmap или речника.

Ето реализацията в 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).

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

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

Обобщете тази публикация с: