Генерация разрежённой матрицы

pavlinux · #1 02.04.2011, 02:45

Нужен алгоритм генерации разряжённой матрицы,
состоящей только из единиц и, естественно, нулей.

Пример:

Пускай будет 10x10

$\begin{matrix}0&1&0&1&1&0&0&1&0&1\\1&0&1&0&0&1&1&0&1&0\\1&0&1&0&1&0&1&1&0&1\\0&1&0&1&1&0&0&1&0&1\\1&0&1&0&0&1&1&0&1&0\\1&0&1&0&1&0&1&1&0&1\\0&1&0&1&1&0&0&1&0&1\\1&0&1&0&0&1&1&0&1&0\\1&0&1&0&1&0&1&1&0&1\\0&1&0&1&1&0&0&1&0&1\\\end{matrix}$

Только два условия:
* количество не нулевых элементов в строке равно 5
* и не должны образовываться тройки, как в строках, так и в столбцах.

---
У меня получается монстроидальные циклы, пригодные для бенчмарков процессора.

MBo · #2 02.04.2011, 11:23

Какой размер матриц будет?
Если не слишком большой, то можно попробовать нагенерировать валидных строк (их будет существенно меньше, чем C(N, 5)) и из них поиском с возвратом лепить матрицу.

pavlinux · #3 03.04.2011, 20:03

Сообщение от MBo

Какой размер матриц будет?

столбцы - кратные 10, потом их склеивать буду.
А вот строк до...хя. Для начала просили 200.

Цитата:

Если не слишком большой, то можно попробовать нагенерировать валидных строк (их будет существенно меньше, чем C(N, 5)) и из них поиском с возвратом лепить матрицу.

Тоже была мысля, ещё не пробовал.

Как я понял, ты имеешь в виду набор строк

$\begin{matrix} a = 1&1&0&1&1&0&0&0&0&1\\ b = 1&1&0&1&1&0&0&0&1&0\\ ...\\ n = 1&0&0&0&1&1&0&0&1&1\\ \end{matrix}$

затем их них формировать матрицы с проверкой на тройки по столбцам?

pavlinux · #4 06.04.2011, 04:04

Ещё уточнения:

Общая матрица будет составная.
А ключевая должная быть 10x20
Но! В матрице не должно быть более 100 единиц !

MBo · #5 06.04.2011, 05:19

Так у тебя предопределено количество единичных в каждой строке, как в первом посте, или во всей матрице?

pavlinux · #6 07.04.2011, 03:31

Сообщение от MBo

Так у тебя предопределено количество единичных в каждой строке, как в первом посте, или во всей матрице?

Да, 5 в строке и 100 во всей матрице. (cобственно это одно и тоже, ибо матрица 10x20)

Испробовал метод с фиксированными строками и перебором с возвратом,
первые 16 строк за 10000 циклов подбираются, далее до миллиона,
а последняя ваще, полчаса.

Я как делаю:

1. Беру случайную, из готовых, строку, назначаю её первой.
2. Беру вторую строку.
3. Не проверяю, ибо нет смысла.
Цикл: пока N < 20
4. Беру N строку.
5. Проверяю на тройки в столбцах.
6. Если есть тройки GOTO Цикл
7. N++
8 GOTO Цикл

Далее я заметил, что могут существовать комбинации строк, что такой матрицы
может вообще не существовать. По этому ввел глобальный счётчик, который
после миллиона циклов прерывает его и меняет N-1 строку. Это спасает,
но не намного. Далее, можно менять N-2, ..., 2, 1 строки. Выходит не намного быстрее.
Более помогает менять первые две и перебрать заново.

----

MBo · #7 07.04.2011, 08:50

Что-то у тебя не так сложилось.
Я попробовал использовать подобный алгоритм, и он генерирует матрицу 10x1000 махом.
Матрица - массив слов Word (UInt16)
1. Сгенерировать список всех 16-разрядных слов с 5 установленными битами из младших 10, так что троек нет. Их получается 126.
2. Два первых слова случайно выбираю.
3. Пока IterationCnt < 100
Генерация случайного индекса из списка
Взятие слова W по нему
Проверка на тройки в столбцах - поразрядное AND предыдущих двух строк и W.
Если AND дает 0, рекурсивный вызов для выбора следующей строки
4. Если не вышло, goto 2

Пример, полученный для 20 строк

Код:

pavlinux · #8 07.04.2011, 22:22

Сообщение от MBo

список всех 16-разрядных слов с 5 установленными битами из младших 10, так что троек нет.

Закономерность не нашел?
Как бы обобщить на числа по основанию два не имеющих 111 (троек).

В десятичном виде вот такой ряд получается:

91,
109, 155, 171, 173, 181,
203, 205, 211, 214, 217, 283,
301, 307, 309, 310, 339, 342, 345, 346,
419, 421, 425, 426, 428, 433, 434, 436,.....

MBo · #9 08.04.2011, 05:45

>Закономерность не нашел?
Нет, навскидку не увидел.
Эта часть алгоритма некритичная, так что просто сочетания из 10 по 5 перечислял, выбирая подходящие.

MBo · #10 08.04.2011, 08:15

Рекурсивная генерация несложно вышла:

Код:

  
procedure GenCombWithout111(N, K, Place, Ones: Integer; Comb: Word);
  var
    i: Integer;
  begin
    if K = 0 then 
      вывести Comb;
    else
      for i := Place + Ord(Ones = 2) to N - K do
        GenCombWithout111(N, K - 1, i + 1, Ord(i  = Place) * Ones + 1, Comb or (1 shl i));
  end;

	Добро пожаловать, гость

	Запомнить?