การกรองสิ่งที่เชื่อมโยงทั้งทางตรงและทางอ้อมจากรายการ

หากคุณมีฟังก์ชัน "test a b" ซึ่งคืนค่าเป็นจริงหาก a และ b เชื่อมต่อกันโดยตรง และหากคุณมีรายการสิ่งต่าง ๆ ที่ไม่เรียงลำดับ อะไรจะเป็นวิธีแก้ปัญหาที่หรูหราและรวดเร็วในการกรองสิ่งที่เชื่อมต่อทั้งหมดจากรายการที่กำหนด

ตัวอย่าง:

let test a b = let diff = a - b in diff == 0 ;;

let lst = [4;1;7;3;8;9;2;0] ;;

filter_connected 2 lst ;;

-> [4;1;3;2;0]

มีคำแนะนำอะไรบ้าง?

อืม ฉันจะพยายามปรับแต่งคำถามของฉัน...

  1. มีรายการสิ่งต่าง ๆ ที่ไม่ได้เรียงลำดับ pE "ให้ lst = [a;b;c;d;e;f;g;h];;" ด้วยรายการประเภท val a'
  2. นอกจากนี้ยังมีฟังก์ชั่นที่ตัดสินว่าสองสิ่งเชื่อมต่อกันโดยตรงหรืออีกนัยหนึ่งถ้าทั้งสองสิ่งเป็นเพื่อนบ้านโดยตรง: val test : a' -> a' -> bool
  3. สิ่งที่ฉันต้องการคือฟังก์ชันที่มีสามอาร์กิวเมนต์ อันแรกคือสิ่งที่เฉพาะเจาะจง อันที่สองคือรายการที่ไม่ได้เรียงลำดับของสิ่งต่าง ๆ ตามที่แนะนำข้างต้น อันสุดท้ายคือฟังก์ชันทดสอบที่อธิบายไว้ข้างต้น: val filter_connected : a' -> a ' รายการ -> (a' -> a' -> บูล) -> รายการ a'

ถ้า a ‹-> b เป็นเพื่อนบ้านโดยตรง และ b ‹-> c เป็นเพื่อนบ้านโดยตรง ดังนั้น [a;b;c] จะเชื่อมต่อกัน

"List.filter () lst" ที่แนะนำไม่ได้ช่วยในที่นี้ เนื่องจากจะกรองเฉพาะเพื่อนบ้านที่กำหนดเท่านั้น

ในตัวอย่างข้างต้น โดยให้ ‹-> b และ b ‹-> c เป็นเพื่อนบ้านโดยตรงในกรณีของฟังก์ชันทดสอบ และอื่นๆ ทั้งหมดที่ไม่ใช่ การเรียก "filter_connected" จะเป็น:

"filter_connected b lst (ทดสอบ);;"

และจะกลับมา: [a;b;c]

หวังว่าคงจะสะอาดกว่านี้นะ...


list filter components ocaml
person Andreas Romeyke    schedule 15.03.2010    source แหล่งที่มา
comment
ฉันค่อนข้างแน่ใจว่าคุณหมายถึง diff = 0 ที่คุณเขียน diff == 0 หากเพียงเพราะพวกเขาทำสิ่งเดียวกันในการใช้งานปัจจุบัน แต่ขอย้ำอีกครั้งว่า ถ้า test เป็นตัวอย่างของสิ่งที่คุณหมายถึงโดยการเชื่อมต่อ ทำไมคุณไม่ส่งต่อมันไปที่ filter_connected และที่สำคัญกว่านั้น คำจำกัดความของความเชื่อมโยงนั้นไม่ใช่เพียงความเท่าเทียมกันเท่านั้น และจะใช้อย่างไรเพื่อให้ได้ [4;1;3;2;0]   -  person Pascal Cuoq    schedule 15.03.2010
comment
วางโค้ดของคุณและโปรดจัดรูปแบบเพื่อให้ได้คำตอบที่ดีกว่า (หากมีคำตอบที่ดีกว่าของ Pascal)   -  person LB40    schedule 16.03.2010

คำตอบ (1)


arrow_upward
3
arrow_downward

ฉันจะถือว่าคุณต้องการได้องค์ประกอบของรายการดั้งเดิมที่มีระยะห่างน้อยกว่า 2 จาก 2

        Objective Caml version 3.11.1

# let test x = abs (x - 2) <= 2 ;;
val test : int -> bool = <fun>
# List.filter test [4;1;7;3;8;9;2;0] ;;
- : int list = [4; 1; 3; 2; 0]
#

List.filter เป็นฟังก์ชันจากไลบรารีมาตรฐาน List.filter f l สร้างรายการองค์ประกอบ l โดยที่ f คำตอบ true

การได้รับฟังก์ชันที่ตัดสินใจว่าแต่ละองค์ประกอบควรอยู่ในรายการผลลัพธ์นั้นตั้งฉากกับปัญหาในการกรองรายการเมื่อคุณมีฟังก์ชันนี้แล้ว ดังนั้นคุณควรดำเนินการดังกล่าวก่อน

หากคุณต้องการใช้สำหรับ f ฟังก์ชันที่เป็นการปิดสกรรมกริยาของความสัมพันธ์ที่คุณมี คุณสามารถใช้ไลบรารี ocamlgraph เพื่อให้ได้การปิดสกรรมกริยานั้น โดยเฉพาะ ฟังก์ชันเหล่านี้ ให้ใช้ add_vertex สำหรับชิ้นส่วนปริศนาแต่ละชิ้น add_edge สำหรับชิ้นส่วนปริศนาแต่ละชิ้น ความสัมพันธ์ที่คุณมี จากนั้นใช้ฟังก์ชัน transitive_closure เพื่อให้ได้กราฟใหม่ g ซึ่งคุณสามารถถามว่ามีเส้นแบ่งระหว่างสององค์ประกอบ e1 และ e2 กับ mem_edge g e1 e2 หรือไม่ ฟังก์ชันที่ใช้บางส่วน mem_edge g e1 สามารถส่งผ่านไปยัง List.filter ได้

person Pascal Cuoq    schedule 15.03.2010
comment
+1: สำหรับการกล่าวถึง ocamlgraph ชอบ lib นี้ แต่ฉันต้องใช้เวลาสักพักกว่าจะเข้าใจ :-) - person LB40; 16.03.2010