для любителей нетривиальных задач

← →
шаген (2004-02-27 21:03) [0]

Господа. Вот такое дело. Рассматриваем обекты Bn - n-мерные бинарные вектора (например, {0,0,0,0,1,0,1}).

Дело в том, что есть задачи (у меня такая), где не нужно различать вектора, получаемые друг из друга сдвигом.
То есть, скажем, {0,1,0,1,1} и {1,0,1,1,0} отождествляются.

Количество бинарных векторов длины n, тождественных до сдвига, это, вообще говоря, частный случай задачи об ожерельях - далеко не банальной комбинаторной задачи. Но решение её известно больше века.

Меня другое смущает. Я никак не могу придумать (или найти в книгах или в сети) алгоритм, позволяющий построить множество этих самых тождественных до сдвига векторов.

т.е чтобы строилось что-то типа (для n=5)
{0,0,0,0,1}
{0,0,0,1,1}
{0,0,1,1,1}
{0,1,1,1,1}
{0,1,0,1,0}
И все. Остальные вектора получаются из этих сдвигом.
Если кто-тот знает какой-то подобный алгоритм, я буду ОЧЕНЬ признателен

← →
Defunct (2004-02-27 21:27) [1]

В чем проблема?

Работайте с типом byte, word, dword

операции сдвига - shr, shl
младший разряд для переноса - odd(x)

операция проверки - And

Создайте свой объект TVector, опишите в нем циклический сдвиг.

← →
шаген (2004-02-27 21:49) [2]

Боюсь, что вы не совсем меня поняли.
Я вообще не про это.
Представьте себе, у нас есть векторы пусть даже и ен очень большой длины, скажем 7.

Это, ёлки-палки уже 128 разных векторов. А Тождественных до сдвига всего (навскидку) 18. И нужно найти именно 18 таких, НЕ ПЕРЕБИРАЯ ДЛЯ ЭТОГО ВСЕ.

потому что тупым перебором при N=20 (т.е. мощность Bn будет 2^20) очень большие сомнения, что получится )

с уважением

← →
Defunct (2004-02-27 22:23) [3]

Так тогда подкорректируйте изначальный постинг.
дело в том что из этих векторов:
{0,0,0,0,1}
{0,0,0,1,1}
{0,0,1,1,1}
{0,1,1,1,1}
{0,1,0,1,0}

Вектор {1,0,1,0,1} путем сдвига получить нельзя. Еще раз сформулируйте задачу более четко. Может от этого будет зависеть и решение.

← →
Nikolay M. (2004-02-27 22:40) [4]

Имхо, самое тупое, если длина векторов не более 64 (sizeof(int64) = 8 байт), то можно реализовать что-то вроде решета Эратосфена: создаешь массив со значениями от 1 до 2^64 - 1, начинаешь генерировать начальные значения для последующей прокрутки (операцией shl + перенос старшего бита) и вычеркивания из массива:
1: т.е. 000...001, прокручиваем 63 раза, вычеркиваем из массива значения 2, 4, 8, ... 2^63
2: вычеркнута, пропускаем
3: т.е. 000...011, прокручиваем 63 раза, вычеркиваем из массива значения 6, 12, 24 и тд.
в иттоге в массиве будут только те числа, которые при делении друг на друга не дают 2^k, т.е. то что тебе и нужно.

← →
Defunct (2004-02-27 22:48) [5]

Nikolay M. © (27.02.04 22:40) [4]
Вы себе представляете массив объемом 2^64 пусть даже байт?

← →
Defunct (2004-02-27 22:49) [6]

PS: Все дожно решаться гораздо проще. Там где автор постинга говорит есть 18 ответов - решается за 18 шагов, без доп. массивов и прочих затрат ресурсов.

← →
шаген (2004-02-27 23:07) [7]

Господа. Я тут пообщался с людьми более компетентными, нежели я, в математике.

Они заверили меня, что задача эта очень непростая и, что самое забавное, пока что вроде бы и не вполне решенная - . Более того, меня заверили, что ее решение будет чревато кучей приятностей в области теории кодирования и смежных областях.
Так например, проблема наибольшего расстояния по Хеммингу будет решаться проще.

такие вот дела.

← →
Defunct (2004-02-27 23:47) [8]

Справедливости ради отмечу, что это все же тривиальная задача, которая сводится к зачеркиванию единиц заранее стабильного вектора {1,1,1,1,1,...,1}

Алгортим придумывать описывать не буду, а выполнить на примере вектора с размерностью 6 могу:

два изначально стабильных вектора
{0,0,0,0,0,0}
{1,1,1,1,1,1}

Начинаем поиск:
Первый цикл:
{1,1,1,1,1,0} // Базовый вектор для второго цикла
{1,1,1,1,0,0} // Базовый вектор для третьего цикла
{1,1,1,0,0,0} // Базовый вектор для четвертого цикла
{1,1,0,0,0,0}
{1,0,0,0,0,0}

Второй цикл:
{1,1,1,0,1,0} // Базовый вектор для 5-го цикла
{1,1,0,0,1,0}
{1,0,0,0,1,0}

Третий цикл:
{1,1,0,1,0,0}
{1,0,0,1,0,0}

Четвертый цикл
{1,0,1,0,0,0}

Пятый цикл:
{1,0,1,0,1,0} // Базовый вектор для 5-го цикла

Теперь установите зависимость и пишите программу. Заметьте в каждом цикле зачеркиваются единицы начиная с определенной позиции: позиции первого встретившегося нуля +1. Два последних вектора кадого цикла не являются базовым вектором для нового цикла т.к. нельзя зачеркнуть последнюю единицу.

← →
Defunct (2004-02-27 23:54) [9]

Среди найденных векторов останется только отсеять тождественные как например: вектор четвертого цикла и последний вектор второго цикла. Но согласитесь эта задача уже гораздо проще чем перебор

← →
Defunct (2004-02-28 00:12) [10]

Создайте программу, киньте на форму Memo и Кнопку. Вставьте этот код, это и есть решение вашей задачи:

procedure TForm1.Button1Click(Sender: TObject); Var S:String; Procedure NextVector(Vector:String); Var Position:Integer; S:String; Begin If Length(Vector)>1 Then If (Vector[1]<>"0") And (Vector[2]<>"0") Then Begin Position := Pos("0",Vector)-2; If Position=-2 Then Position := Length(Vector); S := Vector; While Position>1 Do Begin S[Position] := "0"; Memo1.Lines.Add(S); NextVector(S); Dec(Position); End; End; End; begin S:="111111111"; Memo1.Lines.Add(S); NextVector(S); end;

← →
Defunct (2004-02-28 03:12) [11]

> Они заверили меня, что задача эта очень непростая и, что самое забавное, пока что вроде бы и не вполне решенная - . Более того, меня заверили, что ее решение будет чревато кучей приятностей в области теории кодирования и смежных областях.
Так например, проблема наибольшего расстояния по Хеммингу будет решаться проще.

Пришлете пиво по E-Mail ;>

для любителей нетривиальных задач Найти похожие ветки