LSAT的逻辑博弈部分显示什么类别的组合问题？ [英] What category of combinatorial problems appear on the logic games section of the LSAT?

问题描述

编辑：请参见解决谁拥有斑马的问题;

在LSAT上有一类逻辑问题是这样的：
p>

广播的七个连续时隙，按时间顺序I到7编号，将由六个歌曲磁带-G，H，L， O，P，S-以及一则新闻录像带。每个磁带将分配给不同的时隙，并且任何磁带都不比其他任何磁带长。广播受到以下限制：

必须在O.之前立即播放L。

新闻带必须在L.之后播放。

无论G是在P之前还是G在P之后，G和
P之间肯定有两个时隙。

我有兴趣生成满足条件的排列列表，作为学习测试和编程挑战的一种方式。但是，我不确定这是哪种排列问题。我将类型问题概括如下：

给出一个n长度数组A：

1. 在A内可以通过几种方式排列一组n个唯一项？例如。


2. 如果唯一项集合的长度小于A的长度，那么如果A中的项在A中可以排列多少种方式，则可以重新排列ABCDEFG？该集合可能会出现多次？例如。 ABCDEF => AABCDEF; ABBCDEF等。


3. 如果一组唯一项受阻止条件的约束，可以在A内排列一组唯一项吗？

我的想法是对限制进行编码，然后使用类似Python的itertools的方法来生成排列。欢迎提出想法和建议。

解决方案

好的，以我的看法，有两种方法可以解决此问题：

1. 开始编写一个首先解决该问题的程序。这将很困难。




2. 但是combinatorics告诉我们，更简单的方法是计算所有排列并减去不满足的排列您的约束。

我会选择数字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）：如果len ：
 yield s 
其他：
用于all_perms中的烫发（s [1：]）：
 for i在范围内（len（perm）+1）：
个收益perm [：i] + s [0：1] +烫发[i：] 
 
 def get_the_answer（）：
排列= [i for all_perms（'GHLOPSN'）中的i] #N是新闻录像带
a = [如果L_before_O（i），则表示i中的i] 
b = [如果i_N_after_L（i），表示i中的i]] 
c = [如果g_and_P（i），则i中的i ] 
 return c 
  

我还没有测试过，但这是关于如何我会去

希望这会有所帮助

EDIT: See Solving "Who owns the Zebra" programmatically? for a similar class of problem

There's a category of logic problem on the LSAT that goes like this:

Seven consecutive time slots for a broadcast, numbered in chronological order I through 7, will be filled by six song tapes-G, H, L, O, P, S-and exactly one news tape. Each tape is to be assigned to a different time slot, and no tape is longer than any other tape. The broadcast is subject to the following restrictions:
L must be played immediately before O.
The news tape must be played at some time after L.
There must be exactly two time slots between G and P, regardless of whether G comes before P or whether G comes after P.

I'm interested in generating a list of permutations that satisfy the conditions as a way of studying for the test and as a programming challenge. However, I'm not sure what class of permutation problem this is. I've generalized the type problem as follows:

Given an n-length array A:

1. How many ways can a set of n unique items be arranged within A? Eg. How many ways are there to rearrange ABCDEFG?
2. If the length of the set of unique items is less than the length of A, how many ways can the set be arranged within A if items in the set may occur more than once? Eg. ABCDEF => AABCDEF; ABBCDEF, etc.
3. How many ways can a set of unique items be arranged within A if the items of the set are subject to "blocking conditions"?

My thought is to encode the restrictions and then use something like Python's itertools to generate the permutations. Thoughts and suggestions are welcome.

解决方案

Okay, so the way I see it, there are two ways to approach this problem:

1. Go about writing a program that will approach this problem head first. This is going to be difficult.

2. But combinatorics teaches us that the easier way to do this is to count all permutations and subtract the ones that don't satisfy your constraints.

I would go with number 2.

You can find all permutations of a given string or list by using this algorithm. Using this algorithm, you can get a list of all permutations. You can now apply a number of filters on this list by checking for the various constraints of the problem.

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

I haven't tested this, but this is general idea of how I would go about coding such a question.

Hope this helps

这篇关于LSAT的逻辑博弈部分显示什么类别的组合问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！