Новый конкурс программистов

[Nataly-Mak]

dimkadimon в сообщении #602138 писал(а):

Вот мои оригинальные решения для C4N18.

Посмотрела. Хорошие решения.
Интересен факт: во всех трёх решениях все 4 цвета распределены абсолютно равномерно, каждый цвет занимает 81 ячейку.

[Pavlovsky]

Вот такая идея, построения решений С+1, С+2.
Строим ортогональный массив degree С, strength 2, and index 2. Находим все полупрямоугольники и уничтожаем их вставкой символа С+1 (С+2). В крайнем случае удаляем трудные строки.

[Nataly-Mak]

Посмотрела свою статью. Весьма любопытно

Цитата:

Вот только интересный вопрос: как Холл придумал исходные матрицы P0 для построения ортогональных массивов?

[Pavlovsky]

Неожиданно все направления исследований зашли в тупик. Остается радоваться успехам других.

[whitefox]

Nataly-Mak в сообщении #602141 писал(а):

Поясните, пожалуйста, что такое "ортогональная таблица" по Холлу.

Холл писал(а):

Определение. Ортогональной таблицей $ОА(n, s)$
порядка $n$ и высоты $s$ называется матрица с $s$ строками
и $n^2$ столбцами, элементы которой — числа $1, ..., n$, а
каждая пара строк ортогональна.

[Nataly-Mak]

whitefox в сообщении #602139 писал(а):

В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lfloor N/C\rfloor\times C$, в которых последняя строка, может быть, заполнена не полностью.

Да, всё верно.
Вот 6-сильно окрашенный прямоугольник 31х6:

1 2 3 4 5 6 
1 3 1 1 1 1 
1 4 2 2 2 2 
1 5 4 3 3 3 
1 6 5 5 4 4 
1 1 6 6 6 5
2 1 1 2 3 4 
2 3 2 3 4 5 
2 4 3 5 6 1 
2 5 5 6 5 2 
2 6 6 4 1 3 
3 1 2 5 5 3 
3 2 4 6 1 4 
3 4 5 4 3 5 
3 5 6 1 2 6 
3 6 1 3 6 2 
4 1 5 3 1 6 
4 2 6 2 4 1 
4 3 3 6 2 3 
4 5 2 4 6 4 
4 6 4 1 5 5 
5 1 3 1 4 2 
5 2 1 5 2 5 
5 3 4 2 6 6 
5 4 6 3 5 4 
5 6 2 6 3 1 
6 1 4 4 2 1 
6 2 5 1 6 3 
6 3 6 5 3 2 
6 4 1 6 4 6 
6 5 3 2 1 5

Из этого прямоугольника получается 6 попарно ортогональных прямоугольников 5х6, в которых последняя строка не вся заполнена.
Я, кажется, выкладывала выше этот набор прямоугольников, только там назвала их обобщёнными попарно ортогональными ЛК, тоже неполными, одна строка не вся заполнена.

Стоп!
Не так. У меня действительно 6 попарно ортогональных обобщённых ЛК, в которых в последнем столбце не хватает 5 чисел.
То есть прямоугольники 5х6, по вашему тексту, у меня не получаются.
Что я делаю не так?

Вот мои попарно ортогональные обобщённые ЛК 6-го порядка, полученные из этой 6-сильной раскраски:

1   1   1   1   1   1
2   2   2   2   2   
3   3   3   3   3   
4   4   4   4   4   
5   5   5   5   5   
6   6   6   6   6   

2   3   4   5   6   1
1   3   4   5   6   
1   2   4   5   6   
1   2   3   5   6   
1   2   3   4   6   
1   2   3   4   5   

3   1   2   4   5   6
1   2   3   5   6   
2   4   5   6   1   
5   6   3   2   4   
3   1   4   6   2   
4   5   6   1   3   

4   1   2   3   5   6
2   3   5   6   4   
5   6   4   1   3   
3   2   6   4   1   
1   5   2   3   6   
4   1   5   6   2   

5   1   2   3   4   6
3   4   6   5   1   
5   1   3   2   6   
1   4   2   6   5   
4   2   6   5   3   
2   6   3   4   1   

6   1   2   3   4   5
4   5   1   2   3   
3   4   5   6   2   
6   1   3   4   5   
2   5   6   4   1   
1   3   2   6   5

[dimkadimon]

Nataly-Mak в сообщении #602157 писал(а):

dimkadimon в сообщении #602138 писал(а):

Вот мои оригинальные решения для C4N18.

Посмотрела. Хорошие решения.
Интересен факт: во всех трёх решениях все 4 цвета распределены абсолютно равномерно, каждый цвет занимает 81 ячейку.

Для этого факта есть очень простое объяснение: каждый цвет C это цвет C-1 повернутый на 90 градусов. Поэтому каждый цвет занимает ровно 18х18/4=81 ячейку.

[whitefox]

Уточнение.

Нужно читать так:
В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lceil N/C\rceil\times C$, в которых последняя строка, может быть, заполнена не полностью. (А также комплекту из $M$ попарно ортогональных прямоугольников $C\times \lceil N/C\rceil$, в которых последний столбец, может быть, заполнен не полностью.)

[Nataly-Mak]

whitefox в сообщении #602174 писал(а):

Холл писал(а):

Определение. Ортогональной таблицей $ОА(n, s)$
порядка $n$ и высоты $s$ называется матрица с $s$ строками
и $n^2$ столбцами, элементы которой — числа $1, ..., n$, а
каждая пара строк ортогональна.

Спасибо.

Так это и есть ортогональный массив, насколько я понимаю. Или нет?

Цитата:

Под ортогональным массивом ОА(t+2,n) понимается матрица размером (t+2)хn^2, состоящая из элементов 0, 1, 2, … n-1, все строки которой взаимно ортогональны. Взаимная ортогональность строк матрицы определяется следующим образом:
если a = (a1, a2, a3, … an^2), b = (b1, b2, b3, … bn^2) любые две строки матрицы, то каждая пара (x,y) (x, y есть любые элементы из 0, 1, 2, … n-1) встречается ровно один раз среди пар (ai,bi).

[dimkadimon]

Pavlovsky в сообщении #602158 писал(а):

Вот такая идея, построения решений С+1, С+2.
Строим ортогональный массив degree С, strength 2, and index 2. Находим все полупрямоугольники и уничтожаем их вставкой символа С+1 (С+2). В крайнем случае удаляем трудные строки.

Неплохая идея! Боюсь что находить эти ортогональные массивы не легче чем находить C-strong coloring. Вот сайт с набором разных ортогональных массивов: http://www2.research.att.com/~njas/oadir/. Не могу разобраться где у них index и strength?

[Nataly-Mak]

whitefox в сообщении #602181 писал(а):

Уточнение.

Нужно читать так:
В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lceil N/C\rceil\times C$, в которых последняя строка, может быть, заполнена не полностью.

Целая часть другая?

-- Чт авг 02, 2012 10:30:32 --

dimkadimon в сообщении #602187 писал(а):

Боюсь что находить эти ортогональные массивы не легче чем находить C-strong coloring.

Тоже так думаю.

-- Чт авг 02, 2012 10:35:03 --

Цитата:

Строим ортогональный массив degree С, strength 2, and index 2.

А можно популярно объяснить, что означает "ортогональный массив degree С, strength 2, and index 2"?
Ну, примерчик привести что ли...
Чем отличаются ОМ с index 2 от ОМ с index 1?

Вот пример ОМ(5,4) из моей статьи:

0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 1 2 3 3 2 1 0 1 0 3 2 2 3 0 1
0 1 2 3 2 3 0 1 3 2 1 0 1 0 3 2
0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0

Это какой массив? По новой классификации

-- Чт авг 02, 2012 10:42:37 --

dimkadimon в сообщении #602180 писал(а):

Для этого факта есть очень простое объяснение: каждый цвет C это цвет C-1 повернутый на 90 градусов. Поэтому каждый цвет занимает ровно 18х18/4=81 ячейку.

Очень интересное решение!

[whitefox]

Nataly-Mak в сообщении #602188 писал(а):

Целая часть другая?

Да, вместо "пола" должен быть "потолок".
Например, $\lfloor3{,}5\rfloor=3$ в то время как $\lceil3{,}5\rceil=4$

[Pavlovsky]

dimkadimon в сообщении #602187 писал(а):

Боюсь что находить эти ортогональные массивы не легче чем находить C-strong coloring.

Мы ведь уже научились строить сильноокрашенные прямоугольники для С=p^s. То есть строить ортогональные массивы с индексом 1. Почему строить ортогональные массивы с индексом 2 должно быть трудней?!

Вот пример.



Слева взят сильноокрашенный прямоугольник С=6 31х6, построенный диагональным алгоритмом. В нем, для наглядности, переставлены строки. В ячейках помеченных красным раньше было число 6. Число 6 я заменил на числа от 1 до 5. Получился ортоганальный массив с индексом 2. В котором можно заменой чисел на 6, уничтожить все полупрямоугольники.
Справа пример сильноокрашенного прямоуголника С=5 25х6, построенного по стандартной схеме с использованием полей. Пять последних строк добавлены произвольно. Можно ли в нем уничтожить все полупрямоугольники??

-- Чт авг 02, 2012 12:08:11 --

Nataly-Mak в сообщении #602188 писал(а):

А можно популярно объяснить, что означает "ортогональный массив degree С, strength 2, and index 2"?

Понял чем отличается ортогональный массив от ортогональной таблицы. Массив - стоит, таблица - лежит.

degree=С - это диапозон чисел, которыми заполняется массив от 1 до С.

strength, index - означает берем любые strength колонок и в них должно быть не более index одинаковых строк.

Например strength=2 index=1 в любых двух колонках не должно быть одинаковых строк. Другими словами массив должен быть сильноокрашенным прямоугольником.

[whitefox]

Pavlovsky в сообщении #602198 писал(а):

Получился ортоганальный массив с индексом 2.

Формально, полученный массив не соответствует определению ортогонального массива силы 2 индекса 2. Так как по определению любая упорядоченная пара должна встречаться в любых двух столбцах ровно два раза.
Но для Вашего метода достаточно, чтобы она встречалась не более двух раз.

[Nataly-Mak]

Цитата:

Понял чем отличается ортогональный массив от ортогональной таблицы. Массив - стоит, таблица - лежит.

Nataly-Mak в сообщении #602182 писал(а):

whitefox в сообщении #602174 писал(а):

Холл писал(а):

Определение. Ортогональной таблицей $ОА(n, s)$
порядка $n$ и высоты $s$ называется матрица с $s$ строками
и $n^2$ столбцами, элементы которой — числа $1, ..., n$, а
каждая пара строк ортогональна.

Спасибо.

Так это и есть ортогональный массив, насколько я понимаю. Или нет?

Цитата:

Под ортогональным массивом ОА(t+2,n) понимается матрица размером (t+2)хn^2, состоящая из элементов 0, 1, 2, … n-1, все строки которой взаимно ортогональны. Взаимная ортогональность строк матрицы определяется следующим образом:
если a = (a1, a2, a3, … an^2), b = (b1, b2, b3, … bn^2) любые две строки матрицы, то каждая пара (x,y) (x, y есть любые элементы из 0, 1, 2, … n-1) встречается ровно один раз среди пар (ai,bi).

Ничего не понимаю! И в том, и в другом определении речь идёт о n^2 столбцах.