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

'''ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์''' ({{langx|en|Steinhaus–Johnson–Trotter algorithm}}) คือ ขั้นตอนวิธีสร้างวิธี[[การเรียงสับเปลี่ยน]]โดยอาศัยการสลับที่ของตัวเลข

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

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

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

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

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

== ขั้นตอนวิธี ==

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

=== แสดงตามขั้นตอนวิธี ===
: มีเลขจำนวน 3 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 6 วิธี<br />
# <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>
: ขั้นตอนวิธีนี้สิ้นสุดลงเนื่องจากไม่มีตัวเลขที่สามารถเปลี่ยนที่ได้อีกแล้ว<br />
: <2 เปลี่ยนที่ไม่ได้ เนื่องจากอยู่ทางซ้ายสุดและมีทิศทางซ้าย<br />
: <1 เปลี่ยนที่ไม่ได้ เนื่องจากเลขที่อยู่ทางซ้ายมือของ 1 มีค่าไม่น้อยกว่า 1<br />
: 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><br />

== ประสิทธิภาพการทำงาน ==
ขั้นตอนวิธีนี้มีเวลาในการทำงานเป็น Θ(n!)<ref>{{Cite web |url=http://itd.htc.ac.th/st_it50/it5012/P_2/Data%20Structure%20and%20Algorithm/images/B8.htm |title=การวิเคราะห์ Algorithm |access-date=2011-09-29 |archive-date=2011-09-25 |archive-url=https://web.archive.org/web/20110925073845/http://itd.htc.ac.th/st_it50/it5012/P_2/Data%20Structure%20and%20Algorithm/images/B8.htm |url-status=dead }}</ref> เมื่อ n คือจำนวนตัวเลขที่ต้องการหาวิธีการเรียงสับเปลี่ยน เนื่องจากจำนวนวิธีการเรียงสับเปลี่ยนคือ <math>n!</math> เพราะฉะนั้นการใช้ขั้นตอนวิธีในการแจกแจงวิธีการเรียงสับเปลี่ยนจึงต้องใช้ <math>n!</math> ด้วย

== ตัวอย่างการประยุกต์ใช้งาน ==
ใน[[ปริศนาควีนแปดตัว]]<ref>[http://allisons.org/ll/AlgDS/Recn/Queens/ N-Queens]</ref>สามารถนำขั้นตอนวิธีนี้ไปใช้ในการเลือกตำแหน่งการวางควีน เนื่องจากควีนไม่สามารถอยู่ในแถวหรือหลักเดียวกันได้มากกว่าหนึ่งตัว จึงไม่ทำให้เกิดเลขซ้ำกัน การใช้วิธีการเรียงสับเปลี่ยนจึงเป็นทางเลือกหนึ่งสำหรับการแก้ปัญหาประเภทนี้

== อ้างอิง ==
* The American Mathematical Monthly, Vol. 83, No. 8, Oct., 1976, [http://www.jstor.org/pss/2319890 หน้า 629]
* [https://tropenhitze.wordpress.com/2010/01/25/steinhaus-johnson-trotter-permutation-algorithm-explained-and-implemented-in-java/ Tropenhitze] {{Webarchive|url=https://web.archive.org/web/20111022002251/http://tropenhitze.wordpress.com/2010/01/25/steinhaus-johnson-trotter-permutation-algorithm-explained-and-implemented-in-java/ |date=2011-10-22 }} Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java
{{รายการอ้างอิง}}

== แหล่งข้อมูลอื่น ==
{{รายการอ้างอิง}}

* [http://www.bearcave.com/random_hacks/permute.html Calculating Permutations and Job Interview Questions]
* [http://www.theory.csc.uvic.ca/~cos/inf/perm/PermInfo.html Information on Permutations] {{Webarchive|url=https://web.archive.org/web/20110927112721/http://www.theory.csc.uvic.ca/%7Ecos/inf/perm/PermInfo.html |date=2011-09-27 }}
* [http://www.cut-the-knot.org/do_you_know/permutation.shtml Permutations]


[[หมวดหมู่:ขั้นตอนวิธี]]