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

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

นิยาม

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

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

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

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

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

ขั้นตอนวิธี 

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

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

ตัวอย่าง เมื่อมีตัวเลขจำนวน 4 ตัว 
 มีเลขจำนวน 4 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 24 วิธี
 <1 <2 <3 <4
 <1 <2 <4 <3
 <1 <4 <2 <3
 <4 <1 <2 <3
 4> <1 <3 <2
 <1 4> <3 <2
 <1 <3 4> <2
 <1 <3 <2 4>
 <3 <1 <2 <4
 <3 <1 <4 <2
 <3 <4 <1 <2
 <4 <3 <1 <2
 4> 3> <2 <1
 3> 4> <2 <1
 3> <2 4> <1
 3> <2 <1 4>
 <2 3> <1 <4
 <2 3> <4 <1
 <2 <4 3> <1
 <4 <2 3> <1
 4> <2 <1 3>
 <2 4> <1 3>
 <2 <1 4> 3>
 <2 <1 3> 4>

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

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

อ้างอิง 
 The American Mathematical Monthly, Vol. 83, No. 8, Oct., 1976, หน้า 629
 Tropenhitze  Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java

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

 Calculating Permutations and Job Interview Questions
 Information on Permutations 
 Permutations

ขั้นตอนวิธี