Вот один из способов сделать то, что вы хотите. Сначала идея алгоритма, потом его реализация в R
.
Идея двухэтапного алгоритма
Вам нужна матрица из 0 и 1, где сумма каждой строки равна 10, а сумма каждого столбца равна 10.
Шаг 1. Сначала создайте тривиальное решение следующим образом: первые 10 строк содержат 1 для первых 10 элементов, затем 190 нулей. Второй набор из десяти строк содержит единицы с 11-го по 20-й элемент и так далее. Другими словами, возможное решение состоит в том, чтобы иметь матрицу 200x200, состоящую из всех нулей, с плотными матрицами 10x10 1, вложенными по диагонали 20 раз.
Шаг 2. Перемешайте целые строки и столбцы. В этом перетасовке сохраняются rowSum и columnSums.
Реализация в R
Я использую меньшую матрицу 16x16 для демонстрации. В этом случае, предположим, мы хотим, чтобы каждая строка и каждый столбец в сумме давали 4. (Этот столбец должен быть целым числом, кратным большему размеру квадратной матрицы.)
n <- 4 #size of the smaller square
i <- c(1,1,1,1) #dense matrix of 1's
z <- c(0,0,0,0) #dense matrix of 0's
#create a feasible solution to start with:
m <- matrix(c(rep(c(i,z,z,z),n),
rep(c(z,i,z,z),n),
rep(c(z,z,i,z),n),
rep(c(z,z,z,i),n)), 16,16)
#shuffle (Run the two lines following as many times as you like)
m <- m[sample(16), ] #shuffle rows
m <- m[ ,sample(16)] #shuffle columns
#verify that the sum conditions are not violated
colSums(m); rowSums(m)
#solution
print(m)
Надеюсь, это поможет вам продвинуться вперед с вашим двудольным графом.
person
Ram Narasimhan
schedule
20.08.2015