ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์

ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์ (อังกฤษ: Steinhaus–Johnson–Trotter algorithm) คือ ขั้นตอนวิธีสร้างวิธีการเรียงสับเปลี่ยนโดยอาศัยการสลับที่ของตัวเลข

นิยาม

ทิศทาง

เริ่มจากกำหนดให้ตัวเลขเริ่มต้นจากค่าน้อยและเพิ่มขึ้นตามลำดับไปจนถึงตัวเลขที่ต้องการ และกำหนดทิศทางให้กับตัวเลขแต่ละตัวด้วยทิศทางซ้ายเป็นค่าเริ่มต้น ยกตัวอย่างเช่น

<1 <2 <3 เครื่องหมายน้อยกว่า (<) หน้าตัวเลขแต่ละตัวเป็นการบอกทิศทางของเลขนั้นๆว่าเป็นทิศทางซ้าย ในทางกลับกันเครื่องหมายมากกว่า (>) ที่ตามหลังตัวเลขหมายถึงทิศทางขวา

3> <1 <2 จากตัวอย่างข้างต้นแสดงให้เห็นว่าเลข 3 มีทิศทางขวา

ตัวเลขที่เปลี่ยนที่ได้

ขั้นตอนวิธีนี้จะเรียกตัวเลขซึ่งมีตัวเลขที่อยู่ติดกันในทิศทางที่ระบุไว้มีค่าน้อยกว่าว่า ตัวเลขที่เปลี่ยนที่ได้ ยกตัวอย่างเช่น 3> <1 <2 ในกรณีนี้จะเรียกเลข 2 และเลข 3 ว่าตัวเลขที่เปลี่ยนที่ได้

ถ้าตัวเลขอยู่ทางขวาสุด และมีทิศทางขวา หรือตัวเลขอยู่ทางซ้ายสุดและมีทิศทางซ้าย จะเรียกเลขนั้นว่าตัวเลขที่เปลี่ยนที่ไม่ได้

ขั้นตอนวิธี

1. ขั้นตอนวิธีนี้จะทำงานโดยอาศัยตัวเลขที่มีการเรียงลำดับจากน้อยไปมากและมีการกำหนดทิศทางของตัวเลขแต่ละตัวเป็นทิศทางซ้าย
2. หาตัวเลขที่เปลี่ยนที่ได้ที่มีค่ามากที่สุดแล้วสลับกับตัวเลขที่อยู่ติดกันในทิศทางนั้นๆ ห้ามเปลี่ยนทิศทางของตัวเลขที่สลับกัน
3. ถ้าตัวเลขที่มีค่ามากที่สุดเปลี่ยนที่ไปจนไม่สามารถเปลี่ยนที่ได้แล้ว ให้หาตัวเลขที่เปลี่ยนที่ได้ที่มีค่ารองลงมาแล้วทำการสลับที่เช่นเดียวกัน
4. ในแต่ละรอบที่ทำการสลับที่นั้นให้ตรวจสอบว่ามีตัวเลขที่มีค่ามากกว่าตัวเลขที่สลับที่อยู่หรือไม่ ถ้ามีให้เปลี่ยนทิศทางของตัวเลขที่มีค่ามากกว่า ไม่ว่าจะมีกี่ตัวก็ตาม
5. ขั้นตอนวิธีนี้จะสิ้นสุดลงก็ต่อเมื่อไม่มีตัวเลขที่เปลี่ยนที่ได้แล้ว

แสดงตามขั้นตอนวิธี

มีเลขจำนวน 3 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 6 วิธี

1. <1 <2 <3
2. <1 <3 <2
3. <3 <1 <2 เลข 3 ไม่สามารถเปลี่ยนที่ได้แล้ว เนื่องจากอยู่ทางซ้ายสุดและมีทิศทางซ้าย จึงเปลี่ยนมาทำการสลับที่เลข 2 แทน
4. 3> <2 <1 เลข 3 เปลี่ยนทิศทาง เนื่องจากเมื่อ <2 สลับกับ <1 ขั้นตอนวิธีจะมีการตรวจสอบว่ามีตัวเลขที่มีค่ามากกว่าเลข 2 หรือไม่ ซึ่งก็มีคือเลข 3 จึงเปลี่ยนทิศทางของเลข 3 จากทิศทางซ้ายไปเป็นทิศทางขวา เลข 3 กลับมาเป็นเลขที่มีค่ามากที่สุดที่เปลี่ยนที่ได้
5. <2 3> <1
6. <2 <1 3>

ขั้นตอนวิธีนี้สิ้นสุดลงเนื่องจากไม่มีตัวเลขที่สามารถเปลี่ยนที่ได้อีกแล้ว

<2 เปลี่ยนที่ไม่ได้ เนื่องจากอยู่ทางซ้ายสุดและมีทิศทางซ้าย

<1 เปลี่ยนที่ไม่ได้ เนื่องจากเลขที่อยู่ทางซ้ายมือของ 1 มีค่าไม่น้อยกว่า 1

3> เปลี่ยนที่ไม่ได้ เนื่องจากอยู่ทางขวาสุดและมีทิศทางขวา

ตัวอย่าง เมื่อมีตัวเลขจำนวน 4 ตัว

มีเลขจำนวน 4 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 24 วิธี

1. <1 <2 <3 <4
2. <1 <2 <4 <3
3. <1 <4 <2 <3
4. <4 <1 <2 <3
5. 4> <1 <3 <2
6. <1 4> <3 <2
7. <1 <3 4> <2
8. <1 <3 <2 4>
9. <3 <1 <2 <4
10. <3 <1 <4 <2
11. <3 <4 <1 <2
12. <4 <3 <1 <2
13. 4> 3> <2 <1
14. 3> 4> <2 <1
15. 3> <2 4> <1
16. 3> <2 <1 4>
17. <2 3> <1 <4
18. <2 3> <4 <1
19. <2 <4 3> <1
20. <4 <2 3> <1
21. 4> <2 <1 3>
22. <2 4> <1 3>
23. <2 <1 4> 3>
24. <2 <1 3> 4>
    

ประสิทธิภาพการทำงาน

ขั้นตอนวิธีนี้มีเวลาในการทำงานเป็น Θ(n!) เมื่อ n คือจำนวนตัวเลขที่ต้องการหาวิธีการเรียงสับเปลี่ยน เนื่องจากจำนวนวิธีการเรียงสับเปลี่ยนคือ $n!$ เพราะฉะนั้นการใช้ขั้นตอนวิธีในการแจกแจงวิธีการเรียงสับเปลี่ยนจึงต้องใช้ $n!$ ด้วย

ตัวอย่างการประยุกต์ใช้งาน

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

อ้างอิง

• The American Mathematical Monthly, Vol. 83, No. 8, Oct., 1976, หน้า 629
• Tropenhitze เก็บถาวร 2011-10-22 ที่ เวย์แบ็กแมชชีน Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java

แหล่งข้อมูลอื่น

• Calculating Permutations and Job Interview Questions
• Information on Permutations เก็บถาวร 2011-09-27 ที่ เวย์แบ็กแมชชีน
• Permutations