สตริงที่เป็นไปได้ทั้งหมดที่มีความยาวเท่าใดก็ได้ที่สามารถสร้างได้จากสตริงที่กำหนด?

ในส่วนนี้ เราจะมาดูวิธีสร้างสตริงที่เป็นไปได้ทั้งหมดที่มีความยาวเท่าใดก็ได้ ซึ่งจะนำอักขระแต่ละชุดมารวมกันเป็นสตริง ตัวอย่างเช่น หากสตริงเป็น ABC ก็จะสร้าง − {A, B, C, AB, BA, BC, CB, CA, AC, ABC, ACB, BAC, BCA, CAB, CBA}

เรามาดูตัวอย่างเพื่อทำความเข้าใจกัน

อัลกอริทึม

printAllString(str)

Begin n :=ความยาวของสตริง str count คือ 2^n – 1 สำหรับแต่ละหมายเลข 0 ที่จะนับ ทำ sub_str :=สตริงว่างสำหรับ j ในช่วง 0 ถึง n ถ้า jth bit ของตัวนับถูกตั้งค่าไว้ จากนั้นเชื่อมอักขระ jth ของ str กับ sub_str end ถ้าเสร็จแล้ว ทำซ้ำ:พิมพ์ sub_string จนกว่าการเรียงสับเปลี่ยนย่อยของ sub_string ถัดไปจะไม่เสร็จสิ้นEnd

ตัวอย่าง

#include #include #include using เนมสเปซ std;void printAllString(string str) { int n =str.size(); จำนวน int ที่ไม่ได้ลงนาม =pow(2, n); สำหรับ (ตัวนับ int =1; ตัวนับ <นับ; ตัวนับ ++) {// สร้าง 2^n - 1 strings string subs =""; สำหรับ (int j =0; j  
ผลลัพธ์
 <ก่อนหน้าABABBACACCABCCBABCACBBACBCACABCBADADDABDDBABDADBBADBDADABDBACDDCACDADCCADCDADACDCABCDBDCCBDCDBDBCDCBABCDABDCACBDACDBADBCADCBBACDBADCBCADBCDABDACBDCACABDCADBCBADCBDACDABCDBADABCDACBDBACDBCADCABDCBAD