Алгоритм возврата с питоном
-
27-10-2019 - |
Вопрос
Я пытаюсь внедрить алгоритм, который принимает два ints n и k, где n - это количество мест подряд, а k - это количество студентов, пытающихся сидеть в этом ряду. Дело в том, что каждый ученик должен быть как минимум два места друг от друга с обеих сторон. Что у меня есть, так это функция, которая генерирует все подмножества (массив из 0 или 1 с, 1, означающий, что кто -то сидит там), и я отправляю это на функцию, чтобы проверить, является ли это допустимым подмножеством. Это код, который у меня есть для этой функции
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
Код работает для небольших входов K и N, но если я получаю более высокие значения, я по какой -то причине получаю индекс из -за ошибки списка.
Любая помощь будет отличной, спасибо.
O Ввод A - это список, который выглядит примерно так
['1','0','0','1','0'] # a valid subset for n=5 and k=2
['0','0','0','1','1'] # an invalid subset
РЕДАКТИРОВАТЬ:
Код, который вызывает процесс:
'''
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()
Ошибка, которую я получаю, если использую эти номера
if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') ):
IndexError: list index out of range
Решение
Достаточно исключить недопустимые места для сидения, а именно, когда студенты сидят рядом друг с другом ['1', '1']
или когда между ними есть только одно место ['1', '0', '1']
все другие соглашения, которые имеют правильное количество '1'
, а также '0'
действительны, пример:
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']))
Существуют более эффективные алгоритмы для генерации допустимых подмножеств без проверки всех подмножеств, например,
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
Пример
n, k = 5, 2
for s in subsets(n, k):
assert isvalid(s, n, k)
print(s)
Выход
10010
10001
01001
Другие советы
Индексы для массива длины n
из 0
к n-1
. Анкет Таким образом, доступ n
вышел из списка.
Код, который генерирует списки, должен иметь ошибку, если вы не заметили это на меньших значениях.