Αλγόριθμος συνδυασμού: Εκτύπωση όλων των πιθανών συνδυασμών του R

Τι είναι ο Συνδυασμός;

Ο συνδυασμός είναι ένα είδος διάταξης ορισμένων δεδομένων αντικειμένων. Με μαθηματικούς όρους, ο συνδυασμός είναι ένα σύνολο επιλογών/επιλογών στοιχείων από ένα μοναδικό σύνολο αντικειμένων/αντικειμένων. Εδώ, η σειρά των αντικειμένων δεν έχει σημασία. Είναι επίσης γνωστή ως μέθοδος υπολογισμού του συνολικού αποτελέσματος ενός γεγονότος, όπου η σειρά του αποτελέσματος δεν έχει σημασία.

Για παράδειγμα, σας δίνεται μια τσάντα με 5 διαφορετικά χρώματα και σας ζητείται να δημιουργήσετε ένα μοτίβο με οποιαδήποτε 3 χρώματα. Μπορείτε επίσης να επιλέξετε 3 χρώματα από τα 4 και, στη συνέχεια, να τα τακτοποιήσετε σε διαφορετικές σειρές.

Ας υποθέσουμε ότι τα χρώματα είναι RGYBI (R= Κόκκινο, G= Πράσινο, Υ= Κίτρινο, Β= Μπλε, 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(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ο επίπεδο και μεταφέρετέ το μέχρι το ντο στοιχείο και σχηματίστε μπλοκ που περιέχουν 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++

#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 (Συμπερίληψη και εξαίρεση κάθε στοιχείου)

Αυτή η μέθοδος βασίζεται στην ταυτότητα του Pascal. Προηγουμένως χρησιμοποιούσαμε την αναδρομή για τον υπολογισμό του 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++

#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) Σπρώξτε τον συνδυασμό που δημιουργήθηκε στον 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).

Χρησιμοποιώντας την προηγούμενη μέθοδο για την παρακολούθηση διπλότυπων, χρειαζόμαστε O(n*log(n)) για ταξινόμηση. για σύγκριση, χρειαζόμαστε O(n), και η ίδια η συνάρτηση παίρνει O(n*n). Η συνολική χρονική πολυπλοκότητα θα είναι:

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

Τι είναι ο Συνδυασμός;

Η ανάλυση χρονικής πολυπλοκότητας για το συνδυασμό

Μέθοδος-1: Διορθώθηκε το στοιχείο με αναδρομή

Ψευδοκώδικας

Υλοποίηση σε Γ/C++

Εφαρμογή στο Python

ΣΧΕΤΙΚΑ ΑΡΘΡΑ

Μέθοδος 2 (Συμπερίληψη και εξαίρεση κάθε στοιχείου)

Ψευδοκώδικας

Υλοποίηση σε Γ/C++

Εφαρμογή στο Python

Χειρισμός διπλότυπων συνδυασμών

Χρήση λεξικού ή μη ταξινομημένου χάρτη για την παρακολούθηση διπλών συνδυασμών

Εδώ είναι η υλοποίηση στην python

Εγγραφείτε στο ενημερωτικό δελτίο