อัลกอริทึมของฮีปสร้างการเรียงสับเปลี่ยน ที่เป็นไปได้ทั้งหมด ของ วัตถุn ชิ้น อัลกอริทึมนี้ได้รับการเสนอครั้งแรกโดย บีอาร์ ฮีป ในปี 1963 ^{[ 1 ]}อัลกอริทึมนี้ลดการเคลื่อนไหวให้น้อยที่สุด โดยสร้างการเรียงสับเปลี่ยนแต่ละแบบจากแบบก่อนหน้าโดยการสลับคู่ขององค์ประกอบเพียงคู่เดียว องค์ประกอบอีกn −2ตัวจะไม่ถูกรบกวน ในการทบทวนอัลกอริทึมการสร้างการเรียงสับเปลี่ยนในปี 1977 โรเบิร์ต เซดจ์วิกสรุปว่าในขณะนั้นเป็นอัลกอริทึมที่มีประสิทธิภาพมากที่สุดสำหรับการสร้างการเรียงสับเปลี่ยนด้วยคอมพิวเตอร์^{[ 2 ]}

ลำดับ การ เรียงสับเปลี่ยนของ วัตถุ nชิ้นที่สร้างขึ้นโดยอัลกอริทึมของฮีป เป็นจุดเริ่มต้นของลำดับการเรียงสับเปลี่ยนของ วัตถุ n + 1ชิ้น ดังนั้นจึงมีลำดับการเรียงสับเปลี่ยนอนันต์หนึ่งลำดับที่สร้างขึ้นโดยอัลกอริทึมของฮีป (ลำดับA280318ในOEIS )

สำหรับชุดข้อมูลที่มี องค์ประกอบที่แตกต่างกัน nตัว ฮีปได้ค้นพบวิธีการที่เป็นระบบในการเลือกคู่ขององค์ประกอบที่จะสลับในแต่ละขั้นตอน เพื่อสร้างการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดขององค์ประกอบเหล่านั้นเพียงครั้งเดียว ${\displaystyle C}$

อัลกอริทึมของฮีป (Heap) อธิบายได้ด้วยการเรียกซ้ำว่าเป็นวิธีการลดและพิชิต (decrease and conquer) โดยในแต่ละขั้นตอนจะทำงานกับ องค์ประกอบเริ่มต้นของคอลเลกชัน เริ่มต้นและหลังจากนั้น แต่ละขั้นตอนจะสร้างการเรียงสับเปลี่ยนที่ลงท้ายด้วยองค์ประกอบสุดท้ายที่เหมือนกัน โดยจะเรียกตัวเองซ้ำหนึ่งครั้งโดยที่ องค์ประกอบไม่เปลี่ยนแปลง และจากนั้น เรียกซ้ำ อีกสามครั้งโดยที่องค์ประกอบ ( ) ถูกสลับกับองค์ประกอบเริ่มต้นแต่ละตัวการเรียกซ้ำจะแก้ไของค์ประกอบเริ่มต้น และจำเป็นต้องมีกฎในแต่ละรอบเพื่อเลือกองค์ประกอบที่จะถูกสลับกับองค์ประกอบสุดท้าย วิธีการของฮีปกล่าวว่าการเลือกนี้สามารถทำได้โดยพิจารณาจากจำนวนองค์ประกอบที่ดำเนินการในขั้นตอนนี้ ถ้าเป็นเลขคู่ องค์ประกอบสุดท้ายจะถูกสลับกับดัชนีองค์ประกอบแต่ละตัวซ้ำๆ ถ้าเป็นเลขคี่ องค์ประกอบสุดท้ายจะถูกสลับกับองค์ประกอบแรกเสมอ ${\displaystyle k}$${\displaystyle k=n}$${\displaystyle k<n}$${\displaystyle k!}$${\displaystyle nk}$${\displaystyle k{\text{th}}}$${\displaystyle k-1}$${\displaystyle k{\text{th}}}$${\displaystyle k-1}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle k}$

// แสดงผลลัพธ์การเรียงสับเปลี่ยน k! ครั้งของ A โดยที่องค์ประกอบ k ตัวแรกถูกสลับตำแหน่งในทุกวิธี// หากต้องการแสดงผลลัพธ์การเรียงสับเปลี่ยนทั้งหมดของ A ให้ใช้ k := ความยาวของ A // // ถ้า k > ความยาวของ A จะพยายามเข้าถึง A นอกขอบเขต// ถ้า k <= 0 จะไม่มีผลลัพธ์ (อาร์เรย์ว่างไม่มีการเรียงสับเปลี่ยน) procedure permutations ( k : integer , A : array of any ) : if k = 1 then output ( A ) else // การเรียงสับเปลี่ยนโดยที่องค์ประกอบสุดท้ายคงที่permutations ( k - 1 , A ) // การเรียงสับเปลี่ยนโดยที่องค์ประกอบสุดท้ายถูกสลับตำแหน่งfor i := 0 ; i < k - 1 ; i += 1 do if k is even then swap ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) end if permutations ( k - 1 , A ) end for end if

นอกจากนี้ยังสามารถเขียนอัลกอริธึมในรูปแบบที่ไม่ต้องเรียกซ้ำได้อีกด้วย^{[ 3 ]}

ขั้นตอนpermutations ( n : จำนวนเต็ม, A : อาร์เรย์ของจำนวนใดๆ) : // c คือการเข้ารหัสสถานะของสแต็ก// c[k] เข้ารหัสตัวนับลูป for สำหรับเมื่อเรียก permutations(k + 1, A) c : อาร์เรย์ของจำนวนเต็มสำหรับi := 0 ; i < n ; i += 1 ทำซ้ำc [ i ] := 0 จบการวนซ้ำเอาต์พุต( A ) // i ทำงานคล้ายกับตัวชี้สแต็กi := 1 ; ในขณะที่i < n ทำถ้าc [ i ] < i แล้วถ้าi เป็นเลขคู่ให้สลับ( A [ 0 ] , A [ i ]) มิฉะนั้น ให้สลับ( A [ c [ i ]] , A [ i ]) สิ้นสุดเงื่อนไขเอาต์พุต( A ) // การสลับเกิดขึ้นแล้ว ทำให้ลูป while สิ้นสุดลง จำลองการเพิ่มค่าตัวนับลูป while c [ i ] += 1 // จำลองการเรียกซ้ำที่ไปถึงกรณีฐานโดยการนำตัวชี้ไปยังค่าที่เทียบเท่ากับกรณีฐานในอาร์เรย์i := 1 มิฉะนั้น// การเรียก permutations(i+1, A) สิ้นสุดลงเนื่องจากลูป while สิ้นสุดลง รีเซ็ตสถานะและจำลองการดึงสแต็กโดยการเพิ่มค่าตัวชี้c [ i ] := 0 i += 1 สิ้นสุดเงื่อนไขสิ้นสุดลูป while

ในการพิสูจน์นี้ เราจะใช้การใช้งานด้านล่างนี้เป็นอัลกอริธึมของฮีป เนื่องจากทำให้การวิเคราะห์ง่ายขึ้น และสามารถแสดงรูปแบบบางอย่างได้อย่างชัดเจน แม้ว่าจะไม่เหมาะสมที่สุด (ไม่ได้ลดจำนวนการเคลื่อนย้ายให้น้อยที่สุด ซึ่งจะอธิบายในส่วนถัดไป) แต่การใช้งานนี้ถูกต้องและจะสร้างการเรียงสับเปลี่ยนทั้งหมดได้

// แสดงผลลัพธ์การเรียงสับเปลี่ยน k! ครั้งของ A โดยที่องค์ประกอบ k ตัวแรกถูกเรียงสับเปลี่ยนในทุกวิธี// หากต้องการรับการเรียงสับเปลี่ยนทั้งหมดของ A ให้ใช้ k := ความยาวของ A // // ถ้า k > ความยาวของ A จะพยายามเข้าถึง A นอกขอบเขต// ถ้า k <= 0 จะไม่มีผลลัพธ์ (อาร์เรย์ว่างไม่มีการเรียงสับเปลี่ยน) procedure permutations ( k : integer , A : array of any ) : if k = 1 then output ( A ) else for i := 0 ; i < k ; i += 1 do permutations ( k - 1 , A ) if k is even then swap ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) end ifต่อต่อต่อถ้าหาก

ข้ออ้าง: ถ้าอาร์เรย์ A มีความยาวn ผลลัพธ์ ที่permutations(n, A)ได้คือ A จะไม่เปลี่ยนแปลงหากnเป็นจำนวนคี่ หรือหากnเป็นจำนวนคู่ A จะถูกหมุนไปทางขวา 1 ตำแหน่ง (องค์ประกอบสุดท้ายจะเลื่อนไปอยู่ด้านหน้าองค์ประกอบอื่นๆ)

หลักการพื้นฐาน: ถ้าอาร์เรย์Aมีความยาว 1 โปรแกรมpermutations(1, A)จะแสดงผล A ออกมาแล้วหยุดทำงาน ดังนั้น A จึงไม่เปลี่ยนแปลง เนื่องจาก 1 เป็นจำนวนคี่ ซึ่งตรงกับสิ่งที่กล่าวอ้าง ดังนั้นข้อกล่าวอ้างนี้จึงเป็นจริงสำหรับอาร์เรย์ที่มีความยาว 1

การอุปมาน: ถ้าข้อความดังกล่าวเป็นจริงสำหรับอาร์เรย์ที่มีความยาวl ≥ 1 แล้ว เราจะแสดงให้เห็นว่าข้อความดังกล่าวเป็นจริงสำหรับอาร์เรย์ที่มีความยาวl + 1 (เมื่อรวมกับกรณีพื้นฐานแล้ว จะพิสูจน์ได้ว่าข้อความดังกล่าวเป็นจริงสำหรับอาร์เรย์ทุกความยาว) เนื่องจากข้อความดังกล่าวขึ้นอยู่กับว่าlเป็นจำนวนคี่หรือจำนวนคู่ เราจึงพิสูจน์แต่ละกรณีแยกกัน

ถ้าlเป็นจำนวนคี่ ตามสมมติฐานการอุปมาน สำหรับอาร์เรย์ A ที่มีความยาวlการpermutations(l, A)กระทำจะไม่เปลี่ยนแปลง A และเพื่อให้ข้ออ้างนี้เป็นจริงสำหรับอาร์เรย์ที่มีความยาวl + 1 (ซึ่งเป็นจำนวนคู่) เราต้องแสดงให้เห็นว่าการกระทำนั้นpermutations(l+1, A)หมุน A ไปทางขวา 1 ตำแหน่ง การกระทำนี้permutations(l+1, A)จะทำก่อนpermutations(l, A)(โดยที่ A ไม่เปลี่ยนแปลงเนื่องจากlเป็นจำนวนคี่) จากนั้นในแต่ละรอบiของลูป for จะสลับองค์ประกอบในตำแหน่งiและl (ตำแหน่งสุดท้าย) ใน A การสลับครั้งแรกจะวางองค์ประกอบl (องค์ประกอบสุดท้าย) ในตำแหน่ง 0 และองค์ประกอบ 0 ในตำแหน่งlการสลับครั้งต่อไปจะวางองค์ประกอบในตำแหน่งl (ซึ่งรอบก่อนหน้าวางองค์ประกอบ 0 เดิมไว้) ในตำแหน่ง 1 และองค์ประกอบ 1 ในตำแหน่งlในรอบสุดท้าย การสลับจะวางองค์ประกอบl - 1 ในตำแหน่งlและองค์ประกอบในตำแหน่งl (ซึ่งรอบก่อนหน้าวางองค์ประกอบl - 2 เดิมไว้) ในตำแหน่งl - 1 เพื่อแสดงให้เห็นข้างต้น โปรดดูด้านล่างสำหรับกรณีn = 4

1,2,3,4 ... อาร์เรย์ดั้งเดิม 1,2,3,4 ... การวนซ้ำครั้งที่ 1 (สลับตำแหน่งของซับอาร์เรย์) 4,2,3,1 ... รอบที่ 1 (สลับองค์ประกอบแรกไปไว้ในตำแหน่งสุดท้าย) 4,2,3,1 ... การวนซ้ำครั้งที่ 2 (สลับตำแหน่งของซับอาร์เรย์) 4,1,3,2 ... รอบที่ 2 (สลับองค์ประกอบที่ 2 ไปไว้ในตำแหน่งสุดท้าย) 4,1,3,2 ... การวนซ้ำครั้งที่ 3 (สลับตำแหน่งของซับอาร์เรย์) 4,1,2,3 ... รอบที่ 3 (สลับองค์ประกอบที่ 3 ไปไว้ในตำแหน่งสุดท้าย) 4,1,2,3 ... การวนซ้ำครั้งที่ 4 (สลับตำแหน่งของซับอาร์เรย์) 4,1,2,3 ... การวนซ้ำครั้งที่ 4 (สลับองค์ประกอบที่ 4 ไปไว้ในตำแหน่งสุดท้าย) อาร์เรย์ที่ปรับเปลี่ยนแล้วเป็นเวอร์ชันที่หมุนแล้วของอาร์เรย์ดั้งเดิม 

ถ้าlเป็นจำนวนคู่ ตามสมมติฐานการอุปมาน สำหรับอาร์เรย์ A ที่มีความยาวl การหมุน A จะpermutations(l, A)หมุนไปทางขวา 1 ตำแหน่ง และเพื่อให้ข้ออ้างนี้เป็นจริงสำหรับอาร์เรย์ที่มีความยาวl + 1 (ซึ่งเป็นจำนวนคี่) เราต้องแสดงว่าpermutations(l+1, A)การหมุน A จะไม่เปลี่ยนแปลง การหมุนpermutations(l+1, A)ในแต่ละรอบiของลูป for จะทำการ หมุนองค์ประกอบ lpermutations(l, A)ตัวแรกของ A ก่อน ( เนื่องจากlเป็นจำนวนคู่) จากนั้นสลับองค์ประกอบในตำแหน่งที่ 0 และl (ตำแหน่งสุดท้าย) ใน A การหมุน องค์ประกอบ l ตัวแรก แล้วสลับองค์ประกอบตัวแรกและตัวสุดท้ายเทียบเท่ากับการหมุนอาร์เรย์ทั้งหมด เนื่องจากจำนวนรอบของลูปเท่ากับจำนวนองค์ประกอบในอาร์เรย์ อาร์เรย์ทั้งหมดจะถูกหมุนจนกว่าแต่ละองค์ประกอบจะกลับไปยังตำแหน่งเริ่มต้น เพื่อให้เห็นภาพข้างต้น โปรดดูตัวอย่างด้านล่างสำหรับกรณีn = 5

1,2,3,4,5 ... อาร์เรย์ดั้งเดิม 4,1,2,3,5 ... การวนซ้ำครั้งที่ 1 (สลับตำแหน่งของซับอาร์เรย์ ซึ่งจะหมุนซับอาร์เรย์) 5,1,2,3,4 ... รอบที่ 1 (สลับ) 3,5,1,2,4 ... การวนซ้ำครั้งที่ 2 (สลับตำแหน่งของซับอาร์เรย์ ซึ่งจะหมุนอาร์เรย์) 4,5,1,2,3 ... รอบที่ 2 (สลับ) 2,4,5,1,3 ... การวนซ้ำครั้งที่ 3 (สลับตำแหน่งของซับอาร์เรย์ ซึ่งจะหมุนซับอาร์เรย์) 3,4,5,1,2 ... การวนซ้ำครั้งที่ 3 (สลับ) 1,3,4,5,2 ... การวนซ้ำครั้งที่ 4 (สลับตำแหน่งของซับอาร์เรย์ ซึ่งจะหมุนอาร์เรย์) 2,3,4,5,1 ... รอบที่ 4 (สลับ) 5,2,3,4,1 ... การวนซ้ำครั้งที่ 5 (สลับตำแหน่งของซับอาร์เรย์ ซึ่งจะหมุนซับอาร์เรย์) 1,2,3,4,5 ... รอบที่ 5 (สลับ) ลำดับสุดท้ายของอาร์เรย์จะเหมือนกับลำดับเดิม 

การพิสูจน์โดยการอุปมานสำหรับข้อกล่าวอ้างนั้นเสร็จสมบูรณ์แล้ว ซึ่งจะนำไปสู่เหตุผลว่าทำไมอัลกอริทึมของฮีปจึงสร้างการเรียงสับเปลี่ยนทั้งหมดของอาร์เรย์Aได้ อีกครั้งหนึ่ง เราจะพิสูจน์ความถูกต้องของอัลกอริทึมของฮีปโดยการอุปมาน

หลักการ: อัลกอริทึมของฮีปสามารถ สลับ ตำแหน่งอาร์เรย์Aที่มีขนาด1 ได้อย่างง่ายดาย เนื่องจากผลลัพธ์Aคือการสลับตำแหน่งเพียงหนึ่งเดียวของA

การอุปมาน: สมมติว่าอัลกอริทึมของฮีปทำการสลับตำแหน่งของอาร์เรย์ขนาดiโดยใช้ผลลัพธ์จากการพิสูจน์ก่อนหน้านี้ ทุกองค์ประกอบของAจะอยู่ใน "บัฟเฟอร์" หนึ่งครั้งเมื่อ ทำการสลับตำแหน่งองค์ประกอบ i ตัวแรก เนื่องจากการสลับตำแหน่งของอาร์เรย์สามารถทำได้โดยการเปลี่ยนแปลงอาร์เรย์Aโดยการลบองค์ประกอบx ออก จากAแล้วเพิ่มxเข้าไปในการสลับตำแหน่งแต่ละครั้งของอาร์เรย์ที่เปลี่ยนแปลงแล้ว ดังนั้นจึงสรุปได้ว่าอัลกอริทึมของฮีปทำการสลับตำแหน่งของอาร์เรย์ขนาด i เนื่องจาก "บัฟเฟอร์" นั้นโดยพื้นฐานแล้วเก็บองค์ประกอบที่ถูกลบออกไป โดยถูกเพิ่มเข้าไปในการสลับตำแหน่งของซับอาร์เรย์ขนาดiเนื่องจากการทำงานแต่ละรอบของอัลกอริทึมของฮีปจะมีองค์ประกอบA ที่แตกต่างกันอยู่ ในบัฟเฟอร์เมื่อทำการสลับตำแหน่งของซับอาร์เรย์ การสลับตำแหน่งแต่ละครั้งจึงถูกสร้างขึ้น เนื่องจากทุกองค์ประกอบของAมีโอกาสที่จะถูกเพิ่มเข้าไปในการสลับตำแหน่งของอาร์เรย์Aที่ไม่มีองค์ประกอบในบัฟเฟอร์ ${\displaystyle i+1}$

การลดความซับซ้อนของเวอร์ชันแบบเรียกซ้ำที่กล่าวมาข้างต้นโดยการลดจำนวนครั้งของการเรียกซ้ำนั้นเป็นเรื่องที่น่าสนใจ ตัวอย่างเช่น ดังนี้:

ขั้นตอนการทำงานpermutations ( k : จำนวนเต็ม, A : อาร์เรย์ของจำนวนใดๆ) : ถ้าk = 1 แล้วให้แสดงผล( A ) มิฉะนั้น// เรียกซ้ำหนึ่งครั้งสำหรับแต่ละ k สำหรับi := 0 ; i < k ; i += 1 ทำpermutations ( k - 1 , A ) // ตัวเลือกการสลับขึ้นอยู่กับความเป็นคู่หรือคี่ของ k (คู่หรือคี่) ถ้าk เป็นคู่แล้ว// ไม่ทำอะไรเลย เมื่อ i == k-1 สลับ( A [ i ] , A [ k - 1 ]) มิฉะนั้น// XXX สลับเพิ่มเติมที่ไม่ถูกต้อง เมื่อ i==k-1 สลับ( A [ 0 ] , A [ k - 1 ]) สิ้นสุดifต่อต่อต่อถ้าหาก

การใช้งานนี้จะสร้างการเรียงสับเปลี่ยนทั้งหมดได้สำเร็จ แต่ไม่ได้ลดการเคลื่อนไหวให้น้อยที่สุด เมื่อสแต็กการเรียกซ้ำ คลายตัว ลง จะส่งผลให้มีการสลับเพิ่มเติมในแต่ละระดับ ครึ่งหนึ่งของการสลับเหล่านี้จะไม่มีผลใดๆแต่เมื่อค่าเป็นเลขคี่ จะส่งผลให้มีการสลับเพิ่มเติมระหว่างกับองค์ประกอบ ${\displaystyle A[i]}$${\displaystyle A[k-1]}$${\displaystyle i==k-1}$${\displaystyle k}$${\displaystyle kth}$${\displaystyle 0th}$

${\displaystyle n}$	${\displaystyle n!-1}$	การแลกเปลี่ยน	เพิ่มเติม = การแลกเปลี่ยน${\displaystyle -(n!-1)}$
1	0	0	0
2	1	1	0
3	5	6	1
4	23	27	4
5	119	140	21
6	719	845	126
7	5039	5922	883
8	40319	47383	7064
9	362879	426456	63577

การสลับตำแหน่งเพิ่มเติมเหล่านี้ทำให้ลำดับขององค์ประกอบคำนำหน้า เปลี่ยนแปลงไปอย่างมาก${\displaystyle k-1}$

สามารถหลีกเลี่ยงการสลับค่าเพิ่มเติมได้โดยการเพิ่มการเรียกซ้ำอีกครั้งก่อนลูปและจำนวนครั้งในการวนซ้ำ (ดังที่กล่าวมาข้างต้น) หรือ จำนวนครั้ง ในการวนซ้ำและตรวจสอบว่าน้อยกว่า ดังเช่นในตัวอย่างนี้: ${\displaystyle k-1}$${\displaystyle k}$${\displaystyle i}$${\displaystyle k-1}$

ขั้นตอนการทำงานpermutations ( k : จำนวนเต็ม, A : อาร์เรย์ของจำนวนใดๆ) : ถ้าk = 1 แล้วให้แสดงผล( A ) มิฉะนั้น// เรียกซ้ำหนึ่งครั้งสำหรับแต่ละ k สำหรับi := 0 ; i < k ; i += 1 ทำpermutations ( k - 1 , A ) // หลีกเลี่ยงการสลับเมื่อ i==k-1 ถ้า( i < k - 1 ) // การเลือกสลับขึ้นอยู่กับความเป็นคู่หรือคี่ของ k ถ้าk เป็นเลขคู่ให้สลับ( A [ i ] , A [ k - 1 ]) มิฉะนั้น ให้สลับ( A [ 0 ] , A [ k - 1 ]) จบเงื่อนไขจบเงื่อนไขจบสำหรับจบเงื่อนไข

การเลือกนั้นขึ้นอยู่กับความสวยงามเป็นหลัก แต่การเลือกแบบหลังส่งผลให้ต้องตรวจสอบค่าบ่อยขึ้นเป็นสองเท่า ${\displaystyle i}$

• อัลกอริธึมของสไตน์เฮาส์–จอห์นสัน–ทรอตเตอร์