MemoryError и генераторы

Я пытаюсь создать способ решить проблему, где нет таблицы 3x4 с отсутствующими четырьмя углами. Цель состоит в том, чтобы создать алгоритм для заполнения этой таблицы числами от 1 до 8, где ни один из этих чисел не может быть 1 блоком, близким к ячейке его предыдущего номера (например: 2 не может быть близок к 1), как в вертикальном , горизонтально и по диагонали.MemoryError и генераторы

Поскольку я новичок в программировании, я, вероятно, делаю это неправильно, я создаю список всех возможных мест размещения чисел в ячейках. Но с сеткой 3x4-4 это около 8^8 возможных случаев (от [1,2,3,4,5,6,7,8] до [8,7,6,5,4,3,2, 1])

Я делаю это, потому что моя первая идея заключалась в том, чтобы сделать функцию для проверки данных, если она соответствует критериям впоследствии, не требуя генерации чисел каждый раз. Я использую pickle для вывода данных в txt-файл. Но файл 280 Мб, и он замораживает мой компьютер на пару минут, а затем печатает ошибку памяти.

Извините, если это не имеет смысла, я начал программировать месяц назад.

Мой текущий код для создания этого списка является:

for a in xrange(1,9): 
    for b in xrange(1, 9): 
     for c in xrange(1, 9): 
      for d in xrange(1, 9): 
       for e in xrange(1, 9): 
        for f in xrange(1, 9): 
         for g in xrange(1, 9): 
          for h in xrange(1, 9): 
           if a != (b and c and d and e and f and g and h) and b != (
            a and c and d and e and f and g and h) and c != (
            b and a and d and e and f and g and h) and d != (
            b and c and a and e and f and g and h) and e != (
            b and c and d and a and f and g and h) and f != (
            b and c and d and e and a and g and h) and g != (
            b and c and d and e and f and a and h) and h != (b and c and d and e and f and g and a): 
            probs.append((a, b, c, d, e,f,g,h))

источник

2013-12-15 f.rodrigues

И, возможно, вы захотите изучить «itertools», чтобы создать свои конкретные комбинации. –

Вы должны серьезно рассмотреть ['itertools.product'] (http://docs.python.org/2/library/itertools.html#itertools.product) – thefourtheye

Вы создаете массив с элементами 9x9x9x9x9x9x9x9, и эти элементы массивы из 8 чисел. Это огромно. – Barmar

В комментарии предполагают, существуют более эффективные встроенные методы делать свою перестановку, но первая большая ошибка ваша уникальность проверка.

В питона, (7 and 12) просто оценивает до 12, в то время как (7 and 12 and 9) оценивает до 9. Это не происходит, значит «Применить неравенство ко всем этим». Поэтому вы получаете эквивалент , если a! = H и b! = H и ... Существует довольно много комбинаций, где h уникален, а остальные могут быть любыми, что они хотят. Вы добавляете все из них в probs, и это использует много памяти.

Вторая проблема заключается в том, что, насколько я вижу, вы фактически не проверяете правила вызова. Вы не хотите хранить возможности, где 1 находится рядом с 2, потому что даже с проверкой уникальности вы все равно имеете 8! комбинации.

источник

2013-12-15 09:26:33 Josiah

Спасибо за ответ. Я знаю, что первым делом я должен был создать данные, а затем выбрать только те (или одно), которые соответствуют правилам, потому что для меня это очень трудно увидеть впереди. Я посмотрю на тест, я даже не мог увидеть результат, потому что он дал мне ошибку памяти. –

Если у вас есть какие-либо сомнения, вы можете узнать, как интерпретатор python понимает маленькие сновидения, просто введя их. Как только вы начнете оптимизировать его, вам нужно будет использовать пару циклов, но на данный момент вы можете найти тест '(a не в [b, c, d, e, f, g, h])' помогает. Это создает список, содержащий значения более поздних переменных, а затем подтверждает, что предыдущее значение не отображается. Обратите внимание, что если a не является b, b также не является. Поэтому вам нужно только проверить, находится ли b в [c .. h], поскольку это уже было исключено. – Josiah

Итак, я немного изменил код, до сих пор не понял, как работает itertools, и просто изменив инструкции If из одного большого блока в конце циклов For на один в каждом цикле For. Мне удается сократить время вычислений от 1 мин до менее 3 секунд! И я сделал функцию в конце всех этих заявлений и получил ответ! Большое спасибо. –

Я не могу предложить прямой ответ на ваш вопрос, но я недавно наткнулся на веб-странице, которая является очень всеобъемлющим о решении судоку с питоном: http://norvig.com/sudoku.html Ваш вопрос, мне все равно кажется, есть общие черты, сетки, не повторяющимися одна цифра #, правила для # позиции, Распространение ограничений и т. д. ... удачи!

источник

2013-12-15 14:01:56

MemoryError и генераторы

ответ

Смежные вопросы