как сгенерировать все возможные комбинации матрицы 14x10, содержащей только 1 и 0

Question

Я работаю над проблемой, и одно решение потребовало бы ввода каждой матрицы 14x10, которую можно составить из 1 и 0 ... как я могу сгенерировать их так, чтобы я мог ввести каждую возможную матрицу 14x10 вдругая функция?Спасибо!

Добавлено 21 марта: Похоже, я не написал слова должным образом.Сожалею.То, что я пытаюсь сделать, это оптимизировать производительность 10 различных производственных единиц (с учетом разных скоростей и количества простоев) для нескольких сценариев.Моя цель - разместить блоки простоя, чтобы свести к минимуму разницу в производительности на ежедневной основе.Дается время простоя и частота каждого устройства.В настоящее время я пытаюсь оценить трехнедельный цикл, то есть каждые три недели каждая производственная единица отключается на определенное количество часов.Я просил компьютер определить порядок, в котором единицы будут сняты, исходя из ограничения, что линии отключаются только один раз каждые 3 недели, а разница в суточной добыче минимальна.Мой первый подход состоял в том, чтобы использовать Excel (как я пытался описать выше), и он не работал (нет ничего удивительного) ... где 1 - работает, 0 - выключен и когда они суммируются для расчета производства.Расчетное производство вычитается из заданного максимального суточного производства.Затем эти различия сравнивались по понедельникам, вторникам, вторникам и т. Д. За три недели и минимизировались с помощью решателя.Мой следующий подход состоял в том, чтобы написать код Matlab, в котором входные данные были допустимыми (установить допустимые вариации изо дня в день).Есть ли программа, которая уже делает это или подход, чтобы сделать это проще всего?Это кажется достаточно простым, но я все еще обдумываю разные способы сделать это.Любое понимание будет высоко ценится.

Answer 1

Реальная реализация сильно зависит от того, как вы хотите представить матрицы ... Но при условии, что матрица может быть представлена ​​списком элементов 14 * 10 = 140:

from itertools import product
for matrix in product([0, 1], repeat=140):
    # ... do stuff with the matrix ...

Конечно, как отмечали другие авторы, это, вероятно, не то, что вы хотите сделать ... Но если это действительно то, что вы хотите сделать, это лучший код (с учетом ваших требований), чтобы это сделать.

Answer 2

Это абсолютно невозможно!Количество возможных матриц составляет 2 ¹⁴⁰ , что составляет около 1,4e42.Однако учтите следующее ...

• Если бы вы генерировали две матрицы размером 14 на 10 в случайном порядке, вероятность того, что они будут одинаковыми, равна 1 в 1,4e42.
• Если бы вы сгенерировали 1 миллиард уникальных матриц 14 на 10, то вероятность того, что следующая сгенерированная вами матрица будет такой же, как и у одной из них, будет чрезвычайно мала: 1 в 1,4e33.
• Поток случайных чисел по умолчанию в MATLAB использует алгоритм Mersenne twister с периодом 2 ¹⁹⁹³⁶ -1.Поэтому генератор случайных чисел не должен начинать повторяться в любое время в этот эон.

Ваш подход должен быть таким:

• Найдите компьютер, который никто никогда не хочет использоватьснова.
• Дайте ему как можно больше места для хранения ваших результатов.
• Установите на него MATLAB и запустите его.

• Начните вычислять матрицы случайным образомвот так:

  while true
    newMatrix = randi([0 1],14,10);
    %# Process the matrix and output your results to disk
  end
  

• Уход

Поскольку комбинаций так много, вам не нужно сравнивать newMatrix с любой из предыдущих матриц, посколькуотрезок времени, прежде чем повторение может произойти, астрономически велик.Скорее всего, ваша обработка будет остановлена ​​в первую очередь по другим причинам, таким как (в порядке вероятности):

• Недостаточно места на диске для хранения результатов.
• Естьперебои в подаче электроэнергии.
• В вашем компьютере произошел смертельный аппаратный сбой.
• Вы скончались.
• Земля ушла.
• Вселенная медленно умирает тепловая смерть .

---

ПРИМЕЧАНИЕ: Хотя я и добавил немного юмора в приведенный выше ответ, я думаю, что проиллюстрировал одну полезную альтернативу.Если вы просто хотите отобрать небольшое подмножество возможных комбинаций (где даже 1 миллиард можно считать «маленьким» из-за большого количества комбинаций), вам не нужно проходить дополнительное время- и занимающие много памяти этапы сохранения всех уже обработанных матриц и сравнения с ними новых, чтобы убедиться, что вы не повторяете матрицы.Поскольку шансы на повторение комбинации очень малы, вы можете смело делать это:

for iLoop = 1:whateverBigNumberYouWant
  newMatrix = randi([0 1],14,10);  %# Generate a new matrix
  %# Process the matrix and save your results
end

Answer 3

Генерация Каждая возможная матрица из 1 и 0 для 14*10 будет генерировать 2**140 матрицы. Я не верю, что у тебя будет достаточно жизни для этого. Я не знаю, будет ли солнце еще светить до того, как вы закончите это. Вот почему невозможно сгенерировать все эти матрицы. Вы должны искать какое-то другое решение, это похоже на грубую силу.

Answer 4

Вы уверены хотите ли вы каждую возможную матрицу 14x10?В каждой матрице 140 элементов, и каждый элемент может быть включен или выключен.Поэтому существует 2^140 возможных матриц.Я предлагаю вам пересмотреть то, что вы действительно хотите.

Редактировать: Я заметил, что вы упомянули в комментарии, что вы пытаетесь минимизировать что-то.Существует целое математическое поле под названием оптимизация , предназначенное для подобных вещей.Причина, по которой это поле существует, заключается в том, что довольно часто невозможно исчерпывающе изучить каждое решение в чем-то, напоминающем разумное количество времени.

Answer 5

Попытка сделать это:

import numpy
for i in xrange(int(1e9)): a = numpy.random.random_integers(0,1,(14,10))

(что намного, намного, намного меньше, чем то, что вам требуется) должно быть достаточно, чтобы убедить вас, что это невозможно.Также показано, как рассчитать одну или несколько таких случайных матриц, даже до миллиона, довольно быстро).

РЕДАКТИРОВАТЬ: изменено на xrange для «улучшения требований к скорости и памяти»:)

Answer 6

В зависимости от того, чего вы хотите добиться с помощью сгенерированных матриц, вам может быть лучше сгенерировать случайную выборку и запустить ряд симуляций. Что-то вроде:

matrix_samples = []
# generate 10 matrices
for i in range(10):
    sample = numpy.random.binomial(1, .5, 14*10)
    sample.shape = (14, 10)
    matrix_samples.append(sample)

Вы можете сделать это несколько раз, чтобы увидеть, как результаты варьируются в зависимости от моделирования. Конечно, вы также можете изменить код, чтобы убедиться, что в наборе образцов нет повторов, опять же, в зависимости от того, что вы пытаетесь выполнить.

Answer 7

Вам не нужно повторять это:

def everyPossibleMatrix(x,y):
    N=x*y
    for i in range(2**N):
        b="{:0{}b}".format(i,N)
        yield '\n'.join(b[j*x:(j+1)*x] for j in range(y))

Answer 8

Вот эффективный способ начать работу с Matlab:

Сначала сгенерируйте все 1024 возможных ряда длиной 10, содержащих только нули и единицы:

dec2bin(0:2^10-1)

Теперь у вас есть все возможные ряды, и вы можете выбирать из них по своему желанию. Например, вызвав следующую строку несколько раз:

randperm(1024,14)

Answer 9

На самом деле я был гораздо более пессимистичен, но подумайте:

from math import log, e

def timeInYears(totalOpsNeeded=2**140, currentOpsPerSecond=10**9, doublingPeriodInYears=1.5):
    secondsPerYear = 365.25 * 24 * 60 * 60
    doublingPeriodInSeconds = doublingPeriodInYears * secondsPerYear
    k = log(2,e) / doublingPeriodInSeconds  # time-proportionality constant
    timeInSeconds = log(1 + k*totalOpsNeeded/currentOpsPerSecond, e) / k
    return timeInSeconds / secondsPerYear

, если предположить, что вычислительная мощность компьютера продолжает удваиваться каждые 18 месяцев, и в настоящее время вы можете делать миллиард комбинаций в секунду (оптимистично, но ради аргумента) и вы начнете сегодня, ваш расчет будет завершен 29 апреля 2137 года или около него.

Answer 10

Вместо того, чтобы просто предполагать, что это невозможно, я бы предложил рассмотреть схему, которая отбирает важные подмножества всех возможных комбинаций, вместо того, чтобы применять метод грубой силы.Как один из ваших ответов предложил, вы делаете минимизацию.Для этого существуют численные методы, такие как имитационный отжиг, отбор проб Монте-Карло, а также традиционные алгоритмы минимизации.Возможно, вы захотите выяснить, подходит ли вам это в вашем случае.