ปัญหาการจัดหมวดหมู่ใดที่ปรากฏในส่วนเกมลอจิกของ LSAT

เอาล่ะ เท่าที่ฉันเห็น มีสองวิธีในการแก้ไขปัญหานี้:

1. ไปเกี่ยวกับการเขียนโปรแกรมที่จะแก้ไขปัญหานี้ก่อน นี่จะเป็นเรื่องยาก

2. แต่การเรียงสับเปลี่ยนสอนเราว่าวิธีที่ง่ายกว่าคือนับการเรียงสับเปลี่ยนทั้งหมดแล้วลบอันที่ไม่เป็นไปตามข้อจำกัดของคุณ

ฉันจะไปกับหมายเลข 2

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

def L_before_O(s):
    return (s.index('L') - s.index('O') == 1)

def N_after_L(s):
    return (s.index('L') < s.index('N'))

def G_and_P(s):
    return (abs(s.index('G') - s.index('P')) == 2)

def all_perms(s):    #this is from the link
    if len(s) <=1:
        yield s
    else:
        for perm in all_perms(s[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + s[0:1] + perm[i:]

def get_the_answer():
    permutations = [i for i in all_perms('GHLOPSN')] #N is the news tape
    a = [i for i in permutations if L_before_O(i)]
    b = [i for i in a if N_after_L(i)]
    c = [i for i in b if G_and_P(i)]
    return c

ฉันยังไม่ได้ทดสอบสิ่งนี้ แต่นี่เป็นแนวคิดทั่วไปว่าฉันจะเขียนโค้ดคำถามดังกล่าวอย่างไร

หวังว่านี่จะช่วยได้

นี่เป็นเรื่องง่ายที่จะแก้ไข (โค้ดไม่กี่บรรทัด) ในฐานะโปรแกรมจำนวนเต็ม การใช้เครื่องมือเช่น GNU Linear Programming Kit คุณจะระบุข้อจำกัดของคุณในลักษณะที่ประกาศและ ให้นักแก้ปัญหาคิดหาทางออกที่ดีที่สุด ต่อไปนี้คือตัวอย่างของโปรแกรม GLPK

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

แก้ไข: เพื่อตอบคำถามของ Merjit:

กำหนด:

1. เมทริกซ์ Y โดยที่ Y_(ij) = 1 หากเล่นเทป i ก่อนเทป j และ 0 มิฉะนั้น
2. เวกเตอร์ C โดยที่ C_i ระบุช่วงเวลาเมื่อฉันเล่น (เช่น 1,2,3,4,5,6,7)
3. ค่าคงที่ขนาดใหญ่ M (ค้นหาคำว่า "big M" ในตำราการปรับให้เหมาะสม)

ลดผลรวมของเวกเตอร์ C ให้เหลือน้อยที่สุดตามข้อจำกัดต่อไปนี้:

Y_(ij) != Y_(ji) // If i is before j, then j must not be before i
C_j < C_k + M*Y_(kj) // the time slot of j is greater than the time slot of k only if Y_(kj) = 1
C_O - C_L = 1 // L must be played immediately before O
C_N > C_L // news tape must be played at some time after L
|C_G - C_P| = 2 // You will need to manipulate this a bit to make it a linear constraint

นั่นน่าจะพาคุณไปได้ไกลที่สุด คุณต้องการเขียนข้อจำกัดข้างต้นในไวยากรณ์ของภาษา MathProg (ดังที่แสดงในลิงก์) และตรวจสอบให้แน่ใจว่าฉันไม่ได้ละทิ้งข้อจำกัดใดๆ จากนั้นเรียกใช้โปรแกรมแก้ปัญหา GLPK บนข้อจำกัดแล้วดูว่าเกิดอะไรขึ้น