สมมติว่าเรามีคอลเล็กชันของจำนวนเต็มที่แตกต่างกัน เราต้องหาการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด ดังนั้นหากอาร์เรย์เป็นเหมือน [2,1,3] ผลลัพธ์จะเป็น [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [3,1,2], [3,2,1]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เราจะใช้วิธีการแบบเรียกซ้ำ ซึ่งจะทำให้รายการ เริ่ม สกุลเงิน และ res
- ถ้า start> ความยาวของรายการ – 1 จากนั้นเพิ่ม curr ลงใน res แล้วกลับ
- สำหรับฉันอยู่ในช่วงเริ่มต้นจนถึงความยาวของรายการที่กำหนด – 1
- สลับองค์ประกอบของรายการที่แสดงเมื่อเริ่มต้นดัชนีและ (เริ่ม + (ผม – เริ่ม))
- การเรียงสับเปลี่ยน(รายการ, เริ่ม + 1, สกุลเงิน + [รายการ[เริ่ม]], res)
- สลับองค์ประกอบของรายการที่แสดงเมื่อเริ่มต้นดัชนีและ (เริ่ม + (ผม – เริ่ม))
- เริ่มต้นเรียกการเปลี่ยนแปลง (arr, 0, [], res)
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
คลาส Solution(object):def permute(self, nums):result =[] self.permute_util(nums,0,[],result) คืนค่าผลลัพธ์ def permute_util(self,given_list,start,curr,result):ถ้า start> len(given_list)-1:#print(curr) result.append(curr) return for i in range(start,len(given_list)):self.swap(given_list,start,start+(i-start)) self.permute_util(given_list,start+1,curr+[given_list[start]],result) #print(given_list) self.swap(given_list, start, start + (i - start)) def swap(ตัวเอง, nums,index1, index2):temp =nums[index1] nums[index1] =nums[index2] nums[index2] =tempob1 =Solution()print(ob1.permute([1,2,3,4])))
อินพุต
[1,2,3,4]
