Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.04.2011, 03:45
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

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

Пример:

Пускай будет 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
* и не должны образовываться тройки, как в строках, так и в столбцах.

---
У меня получается монстроидальные циклы, пригодные для бенчмарков процессора.
  #2  
Старый 02.04.2011, 12:23
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Какой размер матриц будет?
Если не слишком большой, то можно попробовать нагенерировать валидных строк (их будет существенно меньше, чем C(N, 5)) и из них поиском с возвратом лепить матрицу.
  #3  
Старый 03.04.2011, 21:03
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Сообщение от 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}

затем их них формировать матрицы с проверкой на тройки по столбцам?
  #4  
Старый 06.04.2011, 05:04
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

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

Общая матрица будет составная.
А ключевая должная быть 10x20
Но! В матрице не должно быть более 100 единиц !
  #5  
Старый 06.04.2011, 06:19
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Так у тебя предопределено количество единичных в каждой строке, как в первом посте, или во всей матрице?
  #6  
Старый 07.04.2011, 04:31
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Сообщение от 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 строки. Выходит не намного быстрее.
Более помогает менять первые две и перебрать заново.

----

Последний раз редактировалось pavlinux, 07.04.2011 в 23:11.
  #7  
Старый 07.04.2011, 09:50
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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

Пример, полученный для 20 строк
Код:
1100101001
0011011010
0110010110
0001101101
1010011010
1100110001
0101100101
1010011010
1010011001
0101100011
1101100100
1000011011
0101001011
1010110100
1011001100
0001101011
1010010101
1001101010
0011001011
0100110101
  #8  
Старый 07.04.2011, 23:22
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Сообщение от 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,.....

Последний раз редактировалось pavlinux, 08.04.2011 в 00:15.
  #9  
Старый 08.04.2011, 06:45
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Закономерность не нашел?
Нет, навскидку не увидел.
Эта часть алгоритма некритичная, так что просто сочетания из 10 по 5 перечислял, выбирая подходящие.
  #10  
Старый 08.04.2011, 09:15
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Рекурсивная генерация несложно вышла:
Код:
  
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;
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Генерация простых многоугольников vmyrik Вычислительная геометрия 10 07.12.2010 01:43
Обращение разреженной матрицы _2 гость Математические алгоритмы (другое) 3 14.11.2009 12:09
Генерация перестановок длины n Pahan Математические алгоритмы 12 14.01.2009 09:46
генерация планарного графа. Omnislash Графы 6 12.03.2007 00:14
генерация текста как? незарегистрированный Реализация, исходники, языки 0 20.11.2006 11:20