Блог

У меня есть проблема, для которой я пытаюсь найти алгоритм. Я был бы признателен за любые предложения.

У меня есть n строк длиной m. Строки имеют двоичные (0,1) значения, которые имеют некоторую ожидаемую сумму. 1 может быть помещен в любом месте его строки до тех пор, пока сумма соответствует ожидаемой. Цель состоит в том, чтобы минимизировать вертикальную сумму для каждого столбца длиной m.

Например, если у нас есть 4 строки и 10 столбцы, где ожидаемые суммы равны:

 Row 1: 6  Row 2: 7  Row 3: 4  Row 4: 5  

Потенциальным решением может быть:

 1 1 1 1 1 1 0 0 0 0  1 1 1 0 0 0 1 1 1 1  1 0 0 1 1 1 0 0 0 0   0 1 0 0 0 0 1 1 1 1  

Получение вертикальных сумм:

 3 3 2 2 2 2 2 2 2 2  

В отличие от больших сумм, если бы мы просто разместили все в начале:

 1 1 1 1 1 1 0 0 0 0  1 1 1 1 1 1 1 0 0 0  1 1 1 1 0 0 0 0 0 0  1 1 1 1 1 0 0 0 0 0  

С суммами:

 4 4 4 4 3 2 1 0 0 0  

Итак, я пытаюсь распределить нагрузку. Мое количество строк достигнет миллионов/миллиардов, поэтому я надеюсь на подход линейной алгебры, а не на итеративный. Спасибо!

 def create_min_vert_matrix(num_r, num_c, arr_sum_rows):   res = []   curr = 0   for r in range(num_r):   row = [0]*num_c   while arr_sum_rows[r] gt; 0:   arr_sum_rows[r] -= 1   row[curr] = 1   curr = (curr 1)%num_c   res.append(row)   return res  

Быстрый тест:

 create_min_vert_matrix(4, 10, [6,7,4,5])  [[1, 1, 1, 1, 1, 1, 0, 0, 0, 0],  [1, 1, 1, 0, 0, 0, 1, 1, 1, 1],  [0, 0, 0, 1, 1, 1, 1, 0, 0, 0],  [1, 1, 0, 0, 0, 0, 0, 1, 1, 1]]  

Функция принимает количество строк num_r , количество столбцов num_c и массив, который указывает , какой должна быть сумма единиц в каждой строке ( arr_sum_rows ).

Идея состоит в том, что если мы распределим данные по одному столбцу как можно более равномерно, мы сможем минимизировать суммы столбцов. Чтобы это произошло, мы отслеживаем последний столбец, в который мы вставили единицу curr , и для каждого вставленного увеличиваем его. Если он становится больше, чем количество столбцов, мы устанавливаем его равным нулю: curr = (curr 1)%num_c .

Алгоритм выполняется там O(n*m) , где n и m -это количество строк и столбцов матрицы и O(1) дополнительное пространство, если мы не учитываем дополнительное пространство, необходимое для результата (в противном случае, конечно, также O(n*m) дополнительное пространство).