Комбинаторный подход к перечислению и нумерации двоичных наборов

В дискретной математике нередко возникает задача такого перечисления всех объектов некоторого множества Л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 = (d1 d-21. ., d^n). Существует ли, а если да, то построить такое перечисление t’o, Vy — • • 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 ж&trade-(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П~к И.

Последовательность множеств, кодирующая такое перечисление, называется (<гь ?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.

Для произвольного набора параметров (< i < 2h.

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

ТЕОРЕМА 3.1. Пусть существует (di, d2,., d2k]n)-перечисление их х2. х2к — характеристика его набора параметров. Пусть г — число единиц в слове х х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. 11 461 155.

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 2 632 058, 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. 343 366.

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.