Kategori masalah kombinatorial apa yang muncul di bagian permainan logika LSAT?

EDIT: Lihat Memecahkan Siapa pemilik Zebra secara terprogram? untuk kelas masalah serupa

Ada kategori masalah logika di LSAT yang berbunyi seperti ini:

Tujuh slot waktu berturut-turut untuk suatu siaran, diberi nomor urut kronologis I sampai 7, akan diisi oleh enam kaset lagu-G, H, L, O, P, S-dan tepat satu kaset berita. Setiap kaset akan ditempatkan pada slot waktu yang berbeda, dan tidak ada kaset yang lebih panjang dari kaset lainnya. Siaran ini tunduk pada batasan berikut:
L harus diputar segera sebelum O.
Kaset berita harus diputar beberapa waktu setelah L.
Harus ada tepat dua slot waktu antara G dan P, terlepas dari apakah G muncul sebelum P atau apakah G muncul setelah P.

Saya tertarik untuk membuat daftar permutasi yang memenuhi kondisi sebagai cara belajar untuk ujian dan sebagai tantangan pemrograman. Namun, saya tidak yakin kelas masalah permutasi apa ini. Saya telah menggeneralisasi masalah tipe sebagai berikut:

Diberikan array dengan panjang n A:

  1. Berapa banyak cara himpunan n benda unik dapat disusun dalam A? Misalnya. Ada berapa cara untuk menyusun ulang ABCDEFG?
  2. Jika panjang himpunan item-item unik lebih kecil dari panjang A, berapa banyak cara himpunan tersebut dapat disusun dalam A jika item-item dalam himpunan tersebut dapat muncul lebih dari satu kali? Misalnya. ABCDEF => AABCDEF; ABCCDEF, dll.
  3. Berapa banyak cara himpunan item unik dapat disusun dalam A jika item himpunan tersebut tunduk pada "kondisi pemblokiran"?

Pikiran saya adalah menyandikan batasan dan kemudian menggunakan sesuatu seperti itertools Python untuk menghasilkan permutasi. Pikiran dan saran dipersilakan.


python combinations puzzle combinatorics
person Merjit    schedule 25.04.2010    source sumber
comment
Apa itu LSAT? Menurut Google, ini adalah Tes Masuk Sekolah Hukum, tapi sepertinya hal itu tidak mungkin terjadi dalam konteks ini. Harap jangan menggunakan akronim yang tidak jelas tanpa menjelaskannya atau memberikan URL.   -  person Dave Kirby    schedule 25.04.2010
comment
LSAT yang saya maksud memang adalah Tes Masuk Sekolah Hukum. Satu bagian di dalamnya terdiri dari permainan logika seperti yang saya referensikan di atas - tujuan saya adalah menentukan jumlah kemungkinan solusi untuk setiap teka-teki.   -  person Merjit    schedule 25.04.2010

Jawaban (2)


arrow_upward
0
arrow_downward

Oke, menurut saya, ada dua cara untuk mengatasi masalah ini:

  1. Mulailah menulis program yang akan mengatasi masalah ini terlebih dahulu. Ini akan sulit.

  2. Namun kombinatorik mengajarkan kita bahwa cara yang lebih mudah untuk melakukan hal ini adalah dengan menghitung semua permutasi dan mengurangi permutasi yang tidak memenuhi batasan Anda.

Saya akan memilih nomor 2.

Anda dapat menemukan semua permutasi string atau daftar tertentu dengan menggunakan algoritme ini. Dengan menggunakan algoritma ini, Anda bisa mendapatkan daftar semua permutasi. Anda sekarang dapat menerapkan sejumlah filter pada daftar ini dengan memeriksa berbagai batasan masalah.

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

Saya belum mengujinya, tetapi ini adalah gambaran umum tentang bagaimana saya akan mengkodekan pertanyaan seperti itu.

Semoga ini membantu

person inspectorG4dget    schedule 25.04.2010
comment
Ini adalah jawaban yang bagus untuk pertanyaan 1 dan 3, dan cara yang elegan untuk mengkodekan batasan permainan! Meskipun demikian, saya masih belum mengetahui cara menghitung permutasi dalam kasus pertanyaan 2 - di mana Anda diizinkan menggandakan variabel untuk mengisi jumlah tempat yang tersedia dalam matriks. - person Merjit; 25.04.2010
comment
Nah, secara terprogram, Anda bisa melakukan len(c). Itu akan mengembalikan jumlah permutasi yang valid. Namun, jika pertanyaan Anda adalah bagaimana cara melakukannya dengan tangan, saya tahu caranya, tetapi saya tidak tahu cara menuliskannya di sini. Kirimkan komentar untuk memberi tahu saya jika ini yang Anda inginkan, dan dalam hal ini, saya akan melakukannya dengan tangan di atas kertas dan memindainya dan meletakkannya di situs web saya dan memposting tautan di sini. - person inspectorG4dget; 26.04.2010
comment
Itulah yang saya cari. Saya menggunakan ini sebagai kesempatan untuk mempelajari bidang matematika yang sebelumnya tidak banyak saya ketahui, jadi informasi tambahan apa pun akan berguna. Saya sangat tertarik dengan soal 2 karena soal ini sering muncul sebagai teka-teki LSAT. Terima kasih! - person Merjit; 27.04.2010
comment
Maaf sudah lama sekali. Saya belum melupakan masalahnya. Saya telah menyelesaikannya dan sekarang mencari pemindai yang dapat saya gunakan. Mudah-mudahan saya bisa mengunggah ini pada hari Senin - person inspectorG4dget; 02.05.2010
comment
Terima kasih! Saya sangat menghargainya. - person Merjit; 03.05.2010
comment
Saya menulis jawabannya pada dua lembar kertas dan dapat ditemukan di: individu. utoronto.ca/ashtopgun/Hobbyism/StackOverflow/ Ini adalah situs pribadi saya dan saya akan menghargai beberapa hasil jika tidak meminta terlalu banyak. - person inspectorG4dget; 04.05.2010

arrow_upward
1
arrow_downward

Ini mudah diselesaikan (beberapa baris kode) sebagai program integer. Dengan menggunakan alat seperti GNU Linear Programming Kit, Anda menentukan batasan Anda secara deklaratif dan biarkan pemecah masalah memberikan solusi terbaiknya. Berikut contoh program GLPK.

Anda dapat membuat kode ini menggunakan bahasa pemrograman tujuan umum seperti Python, tetapi ini adalah jenis hal yang akan Anda lihat di beberapa bab pertama buku teks pemrograman bilangan bulat. Algoritme yang paling efisien telah dikembangkan oleh orang lain.

EDIT: untuk menjawab pertanyaan Merjit:

Mendefinisikan:

  1. matriks Y dimana Y_(ij) = 1 jika tape i diputar sebelum tape j, dan 0 sebaliknya.
  2. vektor C, dimana C_i menunjukkan slot waktu ketika i dimainkan (misalnya 1,2,3,4,5,6,7)
  3. Konstanta M besar (cari istilah "M besar" di buku teks optimasi)

Minimalkan jumlah vektor C dengan batasan berikut:

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

Itu akan membawa Anda sejauh mungkin ke sana. Anda ingin menuliskan batasan di atas dalam sintaks bahasa MathProg (seperti yang ditunjukkan di tautan), dan pastikan saya tidak melewatkan batasan apa pun. Kemudian jalankan pemecah GLPK pada batasannya dan lihat hasilnya.

person RexE    schedule 25.04.2010
comment
Saya pikir pemrograman bilangan bulat mungkin merupakan cara terbaik untuk membuat serangkaian solusi umum untuk masalah seperti ini, tapi saya tidak yakin bagaimana cara menyandikan permainan penyortiran linier seperti ini sebagai masalah optimasi. Di mana/bagaimana saya menempatkan koefisien nilai? - person Merjit; 25.04.2010