Комбинаторный подход к перечислению и нумерации двоичных наборов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Кодирующие последовательности

1.1 Определения.

1.2 Конструкции кодирующих последовательностей

2 Циклические (т, п)-нумерации

2.1 Постановка задачи.

2.2 Нижняя оценка с(т, п).

2.3 Явная конструкция циклических (ш, п)-слов.

2.4 Порожденная циклическая (т, п)-нумерация и алгоритм ее вычисления.

2.5 Верхняя оценка длины циклических (т,п)~слов с ограничениями

2.6 Результаты машинных вычислений.

3 Кодирующие последовательности множеств

3.1 Определения и простейшие утверждения.

3.2 Необходимые условия существования кодирующей последовательности множеств с предписанными расстояниями

3.3 Кодирующие последовательности множеств с периодом

3.4 Гамильтоновость обобщенных гиперкубов.

В дискретной математике нередко возникает задача такого перечисления всех объектов некоторого множества Л4, при котором каждый объект встречается в этом перечислении один раз. При этом возникает естественная нумерация элементов из Л4, то есть обратимое отображение /, которое каждому натуральному числу г £ {1,2,.,/} ставит в соответствие ¿-й в этом перечислении объект, где I - мощность множества Л4. Например, отображение / множества {1,2,. ,2й} в множество 1п двоичных наборов длины п, задаваемое следующим образом: : % —у (ап, (Тп—11 ■■■, <71), где (сгп, сгп-1, ., а- двоичное представление числа г - 1, определяет нумерацию множества 1п. Она порождает перечисление двоичных наборов в лексикографическом порядке.

Часто требуется, чтобы нумерующая функция / удовлетворяла определенным ограничениям. В этом случае возникает вопрос о существовании и нахождении нужной нумерации. Обычно эти ограничения являются следствием условий, которым должно удовлетворять перечисление, порождаемое функцией /. Например, во многих практических задачах требуется перечислять объекты некоторого множества так, чтобы соседние объекты различались в определенном смысле незначительно или далее "минимально". При этом нумерующая функция / должна удовлетворять условию: /(¿) и /■(«' + 1) "близки" при любом г. Преимуществом такого перечисления является возможность быстрого порождения соседних объектов, а следовательно и всего множества. В настоящее время область комбинаторики, посвященная такого типа перечислениям, бурно развивается. При этом объектами упорядочения являются двоичные наборы [17, 15], перестановки [19], ^-элементные подмножества п-элементного множества [12, 24, 30], представление целого числа га в виде суммы слагаемых [31], двоичные деревья [21] и др. Эти перечисления нашли свое применение в таких различных областях как циклическое тестирование [28], сигнальное кодирование [22], сжатие данных [27], расположение процессоров в вершинах гиперкуба [13], подсчет перманента [24] и др. Обзоры полученных результатов и информацию по их применению можно найти в [29, 16].

Другим примером ограничения на нумерующую функцию является минимизация наибольшего абсолютного значения разности номеров, поставленных в соответствие "близким" объектам. В [18] показано, что для множества 1п такая задача решается с помощью так называемой изопериметрической нумерации.

Задачу нумерации двоичных наборов длины га можно рассматривать как задачу кодирования натуральных чисел {1,2,.,2П} двоичными га-ками, а также, как задачу нумерации подмножеств га-элементного множества, используя естественную биекцию между 1п и множеством всех подмножеств множества {1,2,., 2П}: г>1, г;2,., уп) —»• {г | — 1, 1 < г < га}.

Произвольное перечисление двоичных наборов длины га, при котором соседние наборы различаются в единственной позиции, обычно называют "двоичным кодом Грея" или просто "кодом Грея". Для задач существования и эффективного задания кодов Грея оказался полезным язык символьных последовательностей с ограничениями на подслова [15, 6, 3, 26|. При таком подходе вместо самого кода Грея рассматривается кодирующая его символьная последовательность, а ограничения на упорядоченность двоичных наборов формулируются в виде запретов на подслова. Получающиеся при этом задачи обычно просто формулируются, что позволяет либо решать задачи, либо находить нетривиальные свойства решений. Например, в [7] для известной задачи о существовании гамильтонова цикла в графе двух средних слоев гиперкуба нечетной размерности получены необходимые и достаточные условия на символьную последовательность, кодирующую такой цикл, и показано, что буквы должны удовлетворять определенным требованиям равномерного расположения в этой последовательности.

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

Первая задача формулируется следующим образом: для произвольных п и т, т < п, и некотором I, I < 2п, построить такое инъективное отображение / начального отрезка натурального ряда {1,2,.,/} во множество 1п = {0,1}", что равенство p(№,№) = \i-j I выполняется для всех тех i,j Е {1,2,.,/}, для которых |i — j| < m, где p - метрика Хемминга на In. Такие отображения впервые рассматривались в работе A.A. Евдокимова [3], где были названы {т,п)-нумерациями.

Эта задача входит в большой класс задач построения отображений дискретных метрических пространств, сохраняющих расстояния [1], то есть таких отображений, которые обладают следующими свойствами: а) при отображении сохраняются расстояния, не превышающие некоторого значения, называемого радиусом изометричностщ б) расстояния, превышающие некоторое значение (называемое порогом различимости)} не могут сжиматься отображением ниже этого порога.

Если множеством, в которое осуществляется отображение, является множество двоичных наборов длины п с метрикой Хемминга, то вложение, удовлетворяющее свойствам (а) и (б),можно считать таким кодированием объектов исходного множества, при котором малые изменения в кодируемых объектах приводят к малым же изменениям в их кодах [1]. Так {т, п) -11 у м е pai i и и являются локально изометрическим кодированием начального отрезка натуральных чисел с радиусом изометричности т и порогом различимости 1 [3, 35]. Коды, удовлетворяющие условиям (а) и (б), называются цепными кодами [5, 25]. Такими являются, например, коды "змея в ящике", интенсивно изучаемые в связи с различными приложениями [б]. Свойство локальной изометричности кода является полезным, поскольку о метрической близости кодируемых объектов удается узнать по коду. Это свойство оказывается, например, очень эффективным при распознавании образов [11].

В [16] показано, как перечисление двоичных наборов, задаваемое циклической (т, п)-нумерацией, использовалось для усовершенствования конструкций цифровых и фотоновых детекторов.

В работе A.A. Евдокимова [3] задача построения (ш, п)-нумерации была сведена к задаче отыскания слова Л' длины I в /¿-буквенном алфавите со следующими свойствами:

- в любом подслове слова X существует буква, входящая в это подслово нечетное число раз;

- в любом подслове длины т слова Л" все буквы различны. Ниже такие слова будут называться (т, п)-словами. В [3] были построены циклические (т, п)-слова длины 2" для всех п и т < п/2 + 1 (за исключением случая п = 4 и т = 3) и доказано существование циклических (тг-, ггг-)-слов длины 2Щ для бесконечной последовательности некоторых значений тг- и щ, в частности, для последовательности и для последовательности m-i = 3 - V + 1, щ = 5 • 2г', г > 0.

Следовательно, для этих значений параметров задача была решена.

Позднее конструкции циклических (т, го)-слов рассматривались Goddyn L., Lawrence G.M. и Nemeth Е. в работе [16], в которой были получены результаты, близкие предыдущим. В частности, было доказано существование циклических (тг,щ}-слов длины 2Щ для последовательности значений т{- 2 • 2г", щ = 3 • 2г' - 1, г > 0.

В [33] был приведен другой подход к построению циклических (т, п)-слов, основанный на использовании линейного [го, б?]-кода с равновесным базисом. Позднее в [9] с помощью этого подхода были построены циклические (т,п)-слова длины m2n-|rn/2L Однако ранее в [34, 35] была приведена конструкция циклических {п — 1,п)-слов длины (го — 1)2^'/2!. Используя простейшее утверждение с помощью таких слов можно легко получить циклические (т, го)-слова длины т2п~~^т/'2\ что и было показано в [37].

Естественным обобщением задачи перечисления объектов в порядке минимального изменения является следующая задача: перечислить все элементы некоторого множества так, чтобы соседние различались на заданную величину. Примером такой задачи является задача упорядочения всех перестановок 1. го, при котором соседние перестановки различаются в каждой позиции. Эта задача была решена в [32]. Другим примером такого типа перечислений является задача отыскания гами-льтонового цикла в графе shuffle-exchange network, решенная R.Feldman и P.Mysliwietz [14]. В этом графе два двоичных набора (вершины) смежны тогда и только тогда, когда один набор получается из другого одной из следующих операций: ■- перемещение одной единицы влево или вправо; - отрицание последней позиции. Гамильтонову циклу соответствует такое перечисление двоичных наборов, при котором расстояния между соседними наборами будет равно либо 1, либо 2.

Общей задачей перечисления двоичных наборов длины п в заданном порядке является следующая задача, рассматриваемая в главе 3 диссертации. Пусть задан список расстояний D = (d\1 d-21. ., d^n). Существует ли, а если да, то построить такое перечисление t'o, V\y - • • j V2n — 1 всех двоичных наборов длины п, что при любом г, 1 < г < 2п, справедливо равенство p(Vi,V(i+i} mod 2«) = di+i, где р - расстояние Хемминга. В диссертации эта задача решена в случае, когда список D является периодическим с периодом 4.

Перейдем к более детальному изложению содержания диссертации. Диссертация состоит из данного введения, трех глав и списка литературы.

Первая глава посвящена кодирующим последовательностям перечислений двоичных наборов длины п. Для перечисления в порядке минимального изменения, то есть когда соседние наборы различаются в одной позиции, дано понятие кодирующего слова X — х\ х.ч . х\ в алфавите Ап — {1,2,.,п}, где при любом г, 1 < г < I, есть номер позиции, в которой различаются (г — 1)-й и г-ж наборы в этом перечислении. Приведены четыре известные индуктивные конструкции кодирукщих слов.

Для произвольного перечисления двоичных наборов длины п введено понятие кодирующей последовательности множеств SX = Л'2, ., над алфавитом Ап, где при любом г, 1 < г < I. множество Хг состоит из номеров позиций, в которых различаются (г — 1)-й и г-й наборы в этом перечислении. Приведены пять конструкций кодирующих последовательностей множеств, четыре из которых являются обобщением конструкций кодирующих слов.

Вторая глава диссертации посвящена (ш, п)-нумерациям двоичных наборов.

В разделе 2.1 введены понятия (га, п)-нумерации, (т,п)-слов и циклических (т, п)-слов. Приведены их простейшие свойства.

В разделе 2.2 доказана следующая

ТЕОРЕМА 2.1. Пусть X является циклическим {п— 1, п)-словом и имеет вид где для каждого г Е {1,2,.,/} справедливо равенство |Хг-| = п — 2, а Х{ обозначает ту букву алфавита, Ап~\, которая отсутствует\ в слове Х{ (она определена единственным образом). Тогда слово является циклическим (п + 1, п + 2)-словом.

Эта теорема позволяет по циклическому {п — 1, п)-слову определенного вида находить циклическое (п + 1, п -+- 2)-слово. При этом длина слова увеличивается более чем в два раза. Эта конструкция позволяет получать экспоненциальные нижние оценки для максимальной длины с(т, п) циклического (т, «)-слова.

СЛЕДСТВИЕ 2.1. При любом тс, п > 3, справедливы неравенства

X = Х\ п Л'2 п . X4 тс,

У = у\ (п + 2) У2 (п + 2) . У21 (п + 2), где

У2г1 - тс (тс + 1) Х{, У2{ = х{ (тс + 1) Хг-, г е {1,2,.,1}

ТЕОРЕМА 2.2. При любых пит, 0 < т < п. справедливы неравенства с(т, п) >

3/2т2" (т+1)/2? если т нечетмо и т > 7, ш2п-[т/2] в щхггпивном случае.

В разделе 2.3 приведена следующая конструкция циклического (т, п)-слова. Пусть п > 3, 2 < т < п. Разобьем алфавит Ап на три попарно непересекающихся алфавита: {аьа2, •. ,ат»Ь {ьъ • - •, Ьт'+1} и {сьс2,. ,с„тх}, где т' = [(т-1)/2], т" = |(т + 1)/2]. Для любого г, 0 < г < 2та , рассмотрим слово Х-'г = ж"г(2) . ж-п(т') в алфавите {Ь^ Ь2, • • •, определяемое следующим образом. Пусть (&гт,, с^'-!? <7| ) —двоичное представление номера г и = 1. Полагаем если сг] =0, bp(j) в противном случае, где рЦ) равно такому /, что I > сг]+1 = а}+2 Образуем слово aU = 0, а\ тт = w0w . w™,^ w0m wf wm, ''2m —1' полагая при любом г, 0 < i < 2m\ w: m a\ x™(1) a2 ж™(2). am/ ж™(га'), если число m четно, a\ xf(\) аъ ж"г(2). am> xf{mr) am>+i: в противном случае.

Пусть а - последняя буква слова Гт, а слово Тт таково, что Тш = Тш а. Пусть слово У — у\ У2 • ■ • 2/2»-"1-1 в алфавите {с1, с2,., 1} является циклическим кодирующим словом. Тоща справедлива ТЕОРЕМА 2.3» Слово

Ят,п фт т фт у фт ^^ является циклическим (гп, гг)-словом.

Теорема 2.3 позволяет построить простой алгоритм нахождения г-го двоичного набора в порожденной словом Нт'п циклической (ш, п)-нумерации по номеру г. В разделе 2.4 приведен такой алгоритм.

В разделе 2.5 рассмотрено множество ;рт>" таких циклических (т, п)-слов длины /, в которых каждая из [т/2] фиксированных букв встречается [7/т] раз.

Заметим, что слово Нт'п принадлежит множеству рт'п и имеет длину т2П~'т/2"1

ТЕОРЕМА 2.4. Длина любого слова из множества 'Рт,п не превосходит 77г2п~Гт/21

В разделе 2.6 приведены оценки и точные значения максимальных длин (п — 1, п)-слов и циклических (п — 1,п)-слов, полученные с помощью перебора на ЭВМ.

Третья глава диссертации посвящена рассмотрению задачи перечисления двоичных наборов длины п согласно заданному списку расстояний. При решении этой задачи используются кодирующие последовательности ¿множеств.

В разделе 3.1 вводятся основные определения и приводятся несложные утверждения. Последовательность п-мерных двоичных наборов г>о, Х>1, ., 172»-1 называется (¿1, с^, • •., ^-перечислением, если выполнены следующие условия: г) !1{ ф при любых г ф ]] и) •> ) — <^'+1 при любых i И О < I < 2П~к И

0<j< 2к, где Щп — щ.

Последовательность множеств, кодирующая такое перечисление, называется (<гь ¿2, • • •, '^-последовательностью.

Используя несколько общих лемм, получено решение задачи перечисления при к = 0 и 1.

УТВЕРЖДЕНИЕ 3.1. При любых п и <1 < п, (й-п)-перечисление существует тогда и только тогда, когда й нечетно.

УТВЕРЖДЕНИЕ 3.2. При любых п, д.х и д,2, йх < й2 < п, di,d2',n)- перечисление существует тогда и только тогда, когда хотя бы одно из чисел d\ или d2 является нечетным.

В разделе 3.2 введено понятие уравновешенного двоичного слова и получены необходимые условия для существования перечисления двоичных наборов с данным списком расстояний. Пусть X — х\ х2 . xi является произвольным двоичным словом с г единицами, при любом г, 1 < г < г. Через /г- обозначим число нулей между г-ой и (г + 1)-ой единицами слова X, 1 < г < г, Iq - число нулей в начале, а /Г - в конце слова X. Слово X является уравновешенным, если число г четно и справедливо равенство г/2 г/2 hj-i = hi-j=1 i=0

Для произвольного набора параметров (<ii, d2, • ■ • ? d2k;n) его характеристикой называется такое двоичное слово жт Ж2 . x2k, что ж,- = ^ (mod 2), 1 < i < 2h.

Набор параметров {di,d%,., d2k] п) назовем допустимым, если выполнены условия a) d{ < n при любом г, 1 < г < b) хотя бы одно di нечетно; c) если d{ = п, то d{+1 ф п (полагаем <i2fc+1 =

ТЕОРЕМА 3.1. Пусть существует (di,d2,. ,d2k]n)-перечисление их \ х2 . х2к - характеристика его набора параметров. Пусть г - число единиц в слове х\ х2 . х2к. Тогда набор параметров (<¿1, d2. ,d2k] п) является допустимым и выполнено следующее условие либо к < п и число г нечетно, либо слово Х\ х2 . х2к является, уравновешенным.

ТЕОРЕМА 3.2. Пусть двоичное слово X = Х\ х2 . х2п является уравновешенным. Тогда существует такое (di, d2l., d2n] п)~ перечисление, что X является характеристикой его набора параметров.

В разделе 3.3 доказана лемма, позволяющая сводить задачу отыскания (с!ь ¿2) ■ • • ? <^2*5 ^-перечислений, при к < п — 1 к задаче построения {1\М-> ■ ■ - ^-последовательности для некоторых параметров /1, /о,. •, ¿2*, то есть производить "понижение размерности" задачи. С помощью этой леммы получен основной результат третьей главы диссертации.

ТЕОРЕМА 3,3. При любом п > 3 (йхл^^йз^^п)-перечисление существует тогда и только тогда, когда набор параметров (<}], с/2 - (Ь- ") является допустимым, а его характеристика удовлетворяет свойству (*) теоремы 3.1.

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

Автор выражает искреннюю признательность своему научному руководителю А. А. Евдокимову за постановку задач, постоянное внимание к работе и многочисленные полезные обсуждения.

1. Евдокимов А. А. Метрические свойства вложений и коды, сохраняющие расстояния // Модели и методы оптимизации. Новосибирск: Наука. 1988. С.116-132. (Тр./ АН СССР. Сиб. отделение. Ин-т математики. Т 10).

2. Евдокимов А. А. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. 1994. Т.1, N 1, С.5-12.

3. Евдокимов А. А. О нумерации подмножеств конечного множества // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1980. Вып. 34. С. 8-26.

4. Евдокимов А. А, Вложение цепей и циклов в гиперкуб. I. // Методы дискретного анализа в решении экстремальных задач: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1990. Вып. 50. С. 10-25.

5. Евдокимов A.A. Цепные коды с произвольным расстоянием // Докл. АН СССР. 1976. Т. 228, N 6. С. 1273-1276.

6. Евдокимов A.A. О максимальной длине цепи в единичном п-мерном кубе. // Матем.заметки, 1969. Т. 6, вып. 3. С. 309-319.

7. Евдокимов A.A., Пережогин А.Л. Минимальные нумерации подмножеств конечного множества и проблема гамильтоновости графа средних слоев гиперкуба // Дискретный анализ и исследование операций. 1997. Т. 4, N 4. С. 6-12.

8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

9. Зачтен А. Я., вам. Сохраняющие расстояния циклические коды на линейном базисе // Дискрет, анализ и исслед. операций. 1998. Т. 5, N 4. С. 38-44.

10. Зыков А.А. Основы теории графов. М.: Наука, 1987. 381 с.

11. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

12. Bitner J.R., Ehrlish G., Reingold E.M. Efficient generation of the binary reflected Gray code and its applications // Comm. Assoc. Corn-put. Mach. 1976. V.19. P.517-521.

13. Chen M., Shin K.G. Subcube allocation and task migration in hyper-cube multiprocessors // IEEE Trans. Comput. 1990. V.39. P. 11461155.

14. Feldman R., Mysliwietz P. The shuffle-exchange network has a hamil-tonian path // Tech. Report 116, Fachbereich Mathematik-Informatik, Universitat-GH-Paderborn, 1993.

15. Gilbert E.N. Gray codes and paths on the n-cube // Bell Systems Technical Journal. 1958. V.37. P. 815-824.

16. Goddyn L., Lawrence G.M., Nemeth E. Gray codes with optimized run lengths // Utilitas Math. 1988. V.34. P. 179-192.

17. Gray F. Pulse code communications // U.S. Patent 2632058, March 1953.

18. Harper L.H. Optimal numberings and isoperimetric problems on graphs //J. Combin. Theory. 1966. V. 1. N 3, P. 385-393.

19. Johnson S.M. Generation of permutation by adjacent transpositions // Math. Comp. 1963. V.17. P.282-285.

20. Laborde J.M., Madani R.M. Generalized hypercubes and (0,2)-graphs // Discrete Math. 1997. V.165/166. P. 447-459.

21. Lucas J.M., Baronaigien D.Roelants van, Ruskey F. On rotations and the generation of binary trees //J. Algorithms. 1993. V.15. P. 343366.

22. Ludman J.E. Gray code generation for MPSK signals // IEEE Trans. Comm. 1981. V.29. P. 1519-1522.

23. Madani R.M. Characterization of Laborde-Mulder graphs (extended odd graphs) // Discrete Math. 1996. V.150. P. 293-301.

24. Nijenhuis A., Wilf H.S. Combinatorial algorithms for computers and calculators. New York: Academic Press. 1978.

25. Preparata F.P., Nievergelt J. Difference-preserving codes // IEEE Trans. Inform. Theory. 1974. V. 20. P. 643-649.

26. Ramras M. A new method of generating Hamilton cycles on the n-cube // Discrete Math. 1990. V. 85. P. 329-331.

27. Richards D. Data compression and Gray-code sorting // Inform. Process. Lett. 1986. V.22. P. 210-205.

28. Robinson J., Cohn M. Counting sequences // IEEE Trans. Comput. 1981. V.30. P. 17-23.

29. Savage C. D. A survey of combinatorial Gray codes // SIAM Rev. 1997. Vol. 39, N. 4. P. 605-629.

30. Savage C.D., Winkler P. Monotone Gray codes and the middle levels problem // J. Combin. Theory. Ser. A. 1995. V. 70, N 2. P. 230-248.

31. Savage C.D. Gray code sequences of partitions // J. Algorithms. 1989. ¥.10. P. 577-595.

32. WilfH.S. Combinatorial Algorithms. An Update, SIAM. Philadelphia. 1989.

33. Zanten A. J.van. On the construction of distance-preserving codes// Algebraic and Combinatorial Coding Theory. Proceedings of the Fifth International Workshop of the ACCT, Unicorn, Shumen (Bulg.), 1996, 302-306.

34. Пережогин А.Л. Об изометрическом кодировании натуральных чисел // Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96). Тезисы докладов. Новосибирск. 1996. С. 122-123.

35. Пережогин А.Л. О локально изометрическом кодировании натуральных чисел // Дискрет, анализ и исслед. операций. 1996. Т. 3, N 4. С. 69-76.

36. Пережогин А.Л. О циклических нумерациях двоичных слов // Материалы Международной Сибирской конференции по исследованию операций. Новосибирск. 1998. С. 134.

37. Пережогин А.Л. О циклических < m, п >-нумерациях // Дискрет, анализ и исслед. операций. 1998. Т. 5, 4. С. 61-70.

38. Пережогин А.Л. О циклических перечислениях двоичных наборов через равные расстояния // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16-19 декабря 1998 г.). Москва, 1999. С. 71.

39. Пережогин А.Л. О циклических < ш,гг >~нумерациях // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции (Нижний Новгород, 17-22 мая 1999 г.). Часть И. Москва, 1999. С. 185.