Backtracking algorithm with Python

Question

I am trying to implement an algorithm that takes in two ints n and k where n is the number of seats in a row, and k is the number of students trying to sit in that row. The thing is that each student must be at least two seats from each other on both side. What I have is a function that generates all subsets (an array of either 0 or 1 s, 1 meaning someone is sitting there) and I send this to a function to check to see if it is a valid subset. This is the code I have for that function

def process(a,num,n):
    c = a.count('1')
    #If the number of students sitting down (1s) is equal to the number k, check the subset
    if(c == num):
        printa = True
        for i in range(0,n):
            if(a[i] == '1'):
                if(i == 0):
                    if( (a[i+1] == '0') and (a[i+2] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == 1):
                    if( (a[i-1] == '0') and (a[i+1] == '0') and (a[i+2] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == (n-1)):
                    if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == n):
                    if( (a[i-2] == '0') and (a[i-1] == '0') ):
                        break
                else:
                    printa = False                    
            else:
                if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') and (a[i+2] == '0') ):
                    break
                else:
                    printa = False
        if(printa):
            print a
    else:
        return

The code works for small inputs of k and n but if I get higher values I get an index out of list error for some reason I can't figure out.
Any help out be great thanks.

O the input a is the list that looks something like this

['1','0','0','1','0'] # a valid subset for n=5 and k=2
['0','0','0','1','1'] # an invalid subset

EDIT:

Code that calls process:

'''
This function will recursivly call itself until it gets down to the leaves then sends that
subset to process function.  It appends
either a 0 or 1 then calls itself
'''
def seatrec(arr,i,n,k):
    if(i==n):
        process(arr,k,n)
        return
    else:
        arr.append("0")
        seatrec(arr,i+1,n,k)
        arr.pop()
        arr.append("1")
        seatrec(arr,i+1,n,k)
        arr.pop()
    return
'''
This is the starter function that sets up the recursive calls
'''
def seat(n,k):
    q=[]
    seat(q,0,n,k)

def main():
    n=7
    k=3
    seat(n,k)

if __name__ == "__main__":
    main()

The error I get if I use these numbers are

if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') ):
IndexError: list index out of range

Please include the specific call to process that leads to an error, including the values of a, num, and n, so that we can reproduce it. Please also post the error message so we know what line it occurred on :-) — David Robinson
– David Robinson, Commented Feb 17, 2012 at 6:50

jfs · Accepted Answer · 2012-02-18 03:18:04Z

It is sufficient to exclude invalid seating arrangements, namely, when the students seat next to each other ['1', '1'] or when there is only one seat between them ['1', '0', '1'] all other arrangements that have correct numbers of '1', and '0' are valid, example:

def isvalid(a, n, k):
    if not isinstance(a, basestring):
       a = ''.join(a) # `a` is a list of '1', '0'
    return (len(a) == n and a.count('1') == k and a.count('0') == (n-k) and
            all(p not in a for p in ['11', '101']))

There are more efficient algorithms to generate valid subsets without checking all subsets e.g.,

def subsets(n, k):
    assert k >= 0 and n >= 0
    if k == 0: # no students, all seats are empty
        yield '0'*n
    elif k == 1 and (n == 1 or n == 2): # the last student at the end of the row
        yield '1' + '0'*(n-1) # either '1' or '10'
        if n == 2: yield '01'
    elif n > 3*(k-1): # there are enough empty seats left for k students
        for s in subsets(n-3, k-1):
            yield '100' + s # place a student
        for s in subsets(n-1, k):
            yield '0' + s   # add empty seat

Example

n, k = 5, 2
for s in subsets(n, k):
    assert isvalid(s, n, k)
    print(s)

Output

10010
10001
01001

btilly · Accepted Answer · 2012-02-17 06:46:23Z

2

The indexes for an array of length n is from 0 to n-1. Thus accessing n is out of list.

The code that generates the lists must have a bug if you haven't noticed this on smaller values.

answered Feb 17, 2012 at 6:46

btilly

47.8k3 gold badges69 silver badges101 bronze badges

2 Comments

David Robinson Over a year ago

Where specifically do you see the array access n? range(0, n) doesn't include n

Shamanu4 Over a year ago

when i == (n-1), a[i+1] is accessed. this is equal to a[n]

Collectives™ on Stack Overflow

Backtracking algorithm with Python

2 Answers 2

Example

Output

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Output

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related