anagramaton

แอนนาแกรมตัน

ห้องสมุดสำหรับสร้างและจัดการแอนนาแกรม

เซอิโนสซิตตู | UT TENSIO, SIC UIS

• โรเบิร์ต ฮุค, เดอ โพเทนเทีย เรสติติวา

การใช้งาน

 (ต้องการ '[d4hines/anagramaton.core :as a]);; ไลบรารีต้องใช้พจนานุกรมเป็นอินพุต ในรูปแบบของสตริงอาร์เรย์ นี่คือตัวอย่าง (def word (str/split (slurp "/usr/share/dict/words") #"n");; ต่อไปเราต้องดำเนินการบางอย่างล่วงหน้าในพจนานุกรม(def word-map (a/dict->word-map word));; ตอนนี้คุณสามารถเริ่มสร้างแอนนาแกรมได้แล้ว!(a/anagrams word-map "read")
=> #{["เรียน"]
     ["กล้า"]
     ["อ่าน"]
     ["เอ" "แดง"]
     ["โฆษณา" "เรื่อง"]}

พื้นหลัง

นักวิจัยด้านจิตวิทยากำลังตรวจสอบความสามารถของอาสาสมัครในการแก้แอนนาแกรม ด้วยเหตุนี้ พวกเขาต้องการวิธีสร้างและตรวจสอบคำตอบของแอนนาแกรม

คำจำกัดความ

เพื่อวัตถุประสงค์ของโครงการนี้ ให้ใช้คำจำกัดความต่อไปนี้:

• Word: หนึ่งในชุดคำมาตรฐาน Unix

• แอนนาแกรม: คำหรือลำดับของคำที่เกิดจากการจัดเรียงตัวอักษรของสตริงอื่น เช่น คำโวยวาย ที่เกิดขึ้นจาก ช่างไม้

• ปริศนาแอนนาแกรม: สตริงที่ไม่ใช่คำ แต่เป็นแอนนาแกรม

• โซลูชันแอนนาแกรม: คำที่ประกอบด้วยตัวอักษรตัวเดียวกันของแอนนาแกรมที่กำหนด

• แอนนาแกรมที่แก้ไม่ได้: สตริงที่ไม่ใช่ทั้งคำหรือแอนนาแกรม (เรียกชื่อผิดนิดหน่อยใช่มั้ย?)

ความต้องการ

วิธีแก้ปัญหาจะต้อง:

• เป็นห้องสมุด Clojure...

• ที่สามารถสร้างปริศนาแอนนาแกรมได้..

• ที่มีความยากต่างกัน...

• และตรวจสอบว่าคำที่กำหนดเป็นคำตอบของแอนนาแกรมที่กำหนด...

• ในขณะที่เร็วพอที่จะใช้งานแบบโต้ตอบที่ REPL

ก่อนศิลปะ

อินเทอร์เน็ตเซิร์ฟเวอร์แอนนาแกรมโดย Wordsmith

บริการของ Wordsmith มีจำนวนปุ่มที่น่าประทับใจซึ่งคุณสามารถหมุนเพื่อสร้างแอนนาแกรมที่ยอดเยี่ยมได้ สิ่งนี้ยอดเยี่ยมมาก อยากจะลองสร้างไลบรารี่ไคลเอนต์สำหรับ api ของพวกเขาแล้วทำมันให้เสร็จ...

ดิ้นรน

https://en.wikipedia.org/wiki/Scrabble_letter_distributions ใครจะเคยคิด

พจนานุกรมแอนนาแกรม https://en.wikipedia.org/wiki/Anagram_dictionary

คำชมเชยอื่น ๆ

http://norvig.com/mayzner.html - คำอธิบายที่ดีจริงๆ อัปเดตตาราง bigram https://stackoverflow.com/a/12477976 - อัลกอริทึมพื้นฐานสำหรับการค้นหาแอนนาแกรมคำเดียว http://pi.math.cornell.edu /~mec/2003-2004/cryptography/subs/digraphs.html - ตาราง Bigram ที่ฉันใช้ https://web.stanford.edu/class/cs9/sample_probs/Anagrams.pdf - คำอธิบายที่ดีของอัลกอริทึม http://www.ssynth.co.uk/~gay/anagabout.html - การนำไปปฏิบัติ แต่มีรายละเอียดต่ำ

https://stackoverflow.com/a/881367 - แรงบันดาลใจ

ขอบคุณ @seancorfield, @dpsutton และ @porkostomus สำหรับความช่วยเหลือเกี่ยวกับอัลกอริทึมแอนนาแกรมบางส่วน!

คำถามและคำตอบ

• เราจะจัดการกับวลีแอนนาแกรม (แอนนาแกรมหลายคำ) หรือไม่?

• ทุกคำจำกัดความที่ฉันเคยอ่านมา นิยามแอนนาแกรมเป็น "คำ วลี หรือชื่อ" แม้ว่าฉันจะไม่ตื่นเต้นกับความซับซ้อนที่เพิ่มเข้ามาของแอนนาแกรมหลายคำ (ลำดับความสำคัญมากกว่า) ฉันคิดว่าพวกเขาจะต้องได้รับการจัดการเพื่อให้คงความเป็นจริงของปัญหา

• เราจะทำอย่างไรเพื่อเพิ่มประสิทธิภาพความเร็ว?

• ให้น้อยที่สุดเท่าที่จะเป็นไปได้ การเพิ่มประสิทธิภาพก่อนกำหนดและทั้งหมดนั้น

• เราจะวัด "ความยากลำบาก" ได้อย่างไร?

• ดูหัวข้อถัดไป

ความยากกับความยาก

คุณวัดความยากของแอนนาแกรมได้อย่างไร? ปรากฎว่านี่เป็นหัวข้อของการวิจัยและการถกเถียงทางวิชาการมากมาย

นี่คือบทสรุปที่รวดเร็วและสกปรกของการวิจัยของฉัน:

• ดูเหมือนว่า Mayzner และ Tresselt จะเป็นผู้มีอำนาจทางประวัติศาสตร์ในเรื่องนี้ และได้รับการอ้างถึงจากการศึกษาหลายชิ้นในลักษณะนี้

• พวกเขามีการศึกษามากมายที่ตรวจสอบผลกระทบของการศึกษาต่างๆ เช่น การศึกษานี้

• มีเรื่องมากมายเกิดขึ้นในหัวของฉัน แต่ดูเหมือนว่าความถี่บิ๊กแกรมจะเป็นหนึ่งในนั้น