อัลกอริธึมการรวมกัน: พิมพ์ชุดค่าผสมที่เป็นไปได้ทั้งหมดของ R

การรวมกันคืออะไร?

การรวมกันเป็นการจัดเรียงวัตถุที่กำหนดบางอย่าง ในแง่คณิตศาสตร์ การรวมกันคือชุดของตัวเลือก/การเลือกรายการจากชุดรายการ/วัตถุที่ไม่ซ้ำกัน ที่นี่ลำดับของรายการไม่สำคัญ เรียกอีกอย่างว่าวิธีการคำนวณผลลัพธ์รวมของเหตุการณ์ โดยที่ลำดับของผลลัพธ์ไม่สำคัญ

ตัวอย่างเช่น คุณได้รับกระเป๋าที่มี 5 สีที่แตกต่างกัน และขอให้สร้างลวดลายที่มี 3 สีใดก็ได้ คุณสามารถเลือกสีใดก็ได้ 3 สีจาก 4 สี จากนั้นจัดเรียงตามลำดับที่แตกต่างกัน

สมมติว่าสีต่างๆ คือ RGYBI(R= แดง, G= เขียว, Y= เหลือง, B= น้ำเงิน, I= สีคราม) ดังนั้นรูปแบบที่เป็นไปได้อาจเป็น RGB, RGY เป็นต้น

มาดูรูปต่อไปนี้กัน:

คำอธิบาย:

นำสีใดก็ได้ 4 สีจาก 5 สีมาเรียงกัน
จากแต่ละบล็อกที่มี 4 สี ให้เลือก 3 สีและแสดงรายการทั้งหมด ตัวอย่างเช่น เราเลือกเฉพาะ "RGBI" ในรูปและแสดงชุดค่าผสม 4 ชุด
มีทฤษฎีเบื้องหลังในการคำนวณจำนวนชุดค่าผสมทั้งหมดที่เราสามารถทำได้ การรวมกันขององค์ประกอบ r จาก 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*บันทึก(n))

ขั้นตอน 2) สร้างอาร์เรย์อื่นที่มีองค์ประกอบเฉพาะจากข้อมูลอาร์เรย์ชั่วคราวที่กำหนด

ขั้นตอน 3) จากนั้นจึงดำเนินการฟังก์ชันผสม

ดังนั้นความซับซ้อนของเวลาทั้งหมดจึงกลายเป็น = บน²) + O(nLog(n)) เราพิจารณาได้ O(n²) เช่นเดียวกับ 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);
}

Output:

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)

Output:

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 ในที่นี้ วิธีนี้จะแบ่งออกแทนการวนซ้ำแบบซับซ้อน

ตามอัตลักษณ์ของปาสคาล

เอ็นซีอาร์ = (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);
}

Output:

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)

Output:

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 มีค่าเท่ากัน โดยพื้นฐานแล้ว ให้ใส่โค้ด XNUMX บรรทัดต่อไปนี้ในฟังก์ชัน Combination

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

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

การใช้พจนานุกรมหรือแผนที่ที่ไม่เรียงลำดับเพื่อติดตามชุดค่าผสมที่ซ้ำกัน

ดังนั้น หากเราไม่ต้องการจัดเรียงองค์ประกอบสำหรับการติดตามรายการที่ซ้ำกัน เราก็สามารถทำตามขั้นตอนที่กำหนดได้

ขั้นตอน 1) ประกาศพจนานุกรมหรือแฮชแมปทั่วโลก
ขั้นตอน 2) พุชชุดค่าผสมที่สร้างขึ้นไปที่แฮชแมปและเพิ่มค่าทีละหนึ่ง การรวมกันคือกุญแจสำคัญ และการเกิดขึ้นคือค่าต่างๆ
ขั้นตอน 3) เมื่อฟังก์ชันทำงานเสร็จแล้ว เราก็จะพิมพ์คีย์ทั้งหมดจากแฮชแมปหรือพจนานุกรม

นี่คือการใช้งานในหลาม

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)

Output:

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*บันทึก(n)) + O(n) +O(n*n)

ที่คุณอาจชอบ:

การรวมกันคืออะไร?

การวิเคราะห์ความซับซ้อนของเวลาสำหรับการรวม

วิธีที่ 1: องค์ประกอบคงที่พร้อมการเรียกซ้ำ

รหัสหลอก

การใช้งานใน C/C++

การนำไปปฏิบัติใน Python

บทความที่เกี่ยวข้อง

วิธีที่ 2 (รวมและไม่รวมทุกองค์ประกอบ)

รหัสหลอก

การใช้งานใน C/C++

การนำไปปฏิบัติใน Python

การจัดการชุดค่าผสมที่ซ้ำกัน

การใช้พจนานุกรมหรือแผนที่ที่ไม่เรียงลำดับเพื่อติดตามชุดค่าผสมที่ซ้ำกัน

นี่คือการใช้งานในหลาม