IQ Sort

Computer Science Level 5

In a remedial math class, the teacher decides to seat the students in an IQ order. The seats are setup in a way that they appear in a horizontal line.

The order is such that when a hypothetical person X is to the left of a hypothetical person Y, and X is not more than 8 IQ points higher than Y .

For Example, Say that in the math class, there are five students that have IQs of $60, 65, 70, 75, 80$ . The students could be put in an order of $60, 70, 65, 80, 75$ .

If the class had 20 students with IQ scores: 20, 25, 30, 35, 40, 45, 50, 55, 60, 64, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110 , in how many ways could the students be seated in the order defined above?

Note:

There is someone of IQ 64 .
This problem can also be solved using a computer.

Thank You, axas bit for sharing this. Shame on you for never replying to my email though.

The answer is 23322.

1 solution

Agnishom Chattopadhyay
Dec 22, 2014

Dynamic Programming Approach:

def iqsort(arr):
    if len(arr) == 1:
            yield arr
    else:
            for i in xrange(len(arr)):
                    for j in arr:
                            if arr[i] - j > 8:
                                    break
                    else:
                            s = iqsort(arr[:i]+arr[i+1:])
                            for k in s:
                                    yield [arr[i]] + k

a = [] 
for i in iqsort([20,25,30,35,40,45,50,55,60,64,65,70,75,80,85,90,95,100,105,110]):
    if not i in a:
        a.append(i)
print len(a)

Mathematical Approach:

See Page 23 of this document

IQ Sort

Thank You, axas bit for sharing this. Shame on you for never replying to my email though.

The answer is 23322.

1 solution

0 pending reports