Биномиальные системы счисления

 

А. Я. Заятея, вая

 

Биномиальные системы счисления

 

 

ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ Январь—март 1999. Серия 1. Том 6, № 1, 12-18

УДК 519.714

БИНОМИАЛЬНЫЕ СИСТЕМЫ СЧИСЛЕНИЯ И НУМЕРАЦИИ КОМБИНАТОРНЫХ ОБЪЕКТОВ1)

А. Я. Зачтен, ван

Изучается роль различных систем счисления в решении задач перечисления комбинаторных объектов в лексикографическом порядке и порядке их минимального изменения, аналогичном известному коду Грея. Изложение иллюстрируется примерами.

Введение

Пусть V — множество некоторых комбинаторных объектов и |У| = N. Далее, пусть объекты V линейно упорядочены согласно некоторому критерию, определяющему относительный порядок объектов. Тогда каждому объекту можно приписать индекс или номер, который обычно изменяется от 1 до N или от 0 до N — 1.

Определение номера объекта обычно называется задачей нумерации. Обратная задача нахождения объекта по данному номеру называется задачей денумерации. Очень часто порядок на множестве V определяется рекурсивно. В таком случае требуется получить нерекурсивное решение задачи (де-)нумерации.

Поскольку многие комбинаторные объекты представляются в виде двоичных наборов или, в более общем случае, в виде слов в алфавите из q букв, q ^ 2, они могут быть упорядочены лексикографически, и тогда можно говорить о лексикографическом коде. Другим порядком является порядок минимального изменения, или код Грея, при котором изменение при переходе к следующему объекту является «минимальным».

Оказывается, что в большинстве случаев существуют некоторые системы счисления, которые очень подходят для решения задач нумерации [4]. Так, обычная двоичная система счисления является подходящей системой для лексикографически упорядоченного кода L(n) двоичных наборов длины п. Это же верно и для кода Грея G{n) тех же объектов.

Менее известными примерами являются нумерации двоичных наборов длины п одинакового веса к. Подходящей системой для лексикографического кода 1/(п, к) является биномиальная система счисления, тогда как в случае кода Грея G(n,k) удобно использовать так называемую чередующуюся биномиальную систему счисления [5]. Еще две биномиальные системы (называемые смешанными биномиальными системами) оказываются удобными для нумерации кода С(п,к) разбиений числа п на к частей. В С(п, к) эти разбиения представляются в виде .. .гь

где Ti + г2 + • • • + гк — п, т{ ^ 0, и упорядочены в некотором порядке минимального изменения [6].

Обобщением обычной биномиальной системы является циклономи- альная система, которая может быть использована для нумерации лексикографического кода Lq(n,k) таких наборов (аь... , ап) в алфавите

n

{0,1,... , q - 1), что Х>г = к (см. [2]).

1. Комбинации

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

Лексикографический код L(n, к) определяется рекурсивно следующим образом:

Цп, 0) = (00 ... 0), Ь(щ п) = (11 ... 1),

 

 

Кодовые слова нумеруются числами от 0 до (£) — 1. Подходящей системой счисления для такой нумерации является хорошо известная биномиальная система счисления (см., например, [1]), основанная на следующем свойстве.

Утверждение 1. Пусть к ^ 1 — произвольное целое. Любое целое число N ^ 0 единственным образом представимо в виде

где ak > afc_i > ак_2 > • • • > a2 ^ 0.

В этом случае используем запись: N — (dk^k-i^k-i • • -a>i)s- Номер г-го кодового слова /г- кода L(n, к) можно представить в виде 
где 62, ... , Ьк — номера позиций единиц в (справа налево), 0 ^ bj ^ тг — 1 для всех j.

G(n,k)

О < к <п.

Эти же слова могут быть упорядочены как код Грея G(n, к) следующим образом:

G(n, 0) = (00 ... 0), G(n, п) — (11... 1),

' 0G{n- 1,&) " lG(n-l,k)R_

Обозначение G(n — — l)R используется для списка G(n — 1,к — 1), заданного в обратном порядке. Соответствующей системой счисления является чередующаяся система счисления, введенная в [5],

Утверждение 2. Пусть к ^ 1 — произвольное натуральное число. Любое N 0 яря четном к и любое N > 0 яря нечетном к однозначно представимо в виде

а>к\ (а*-Л , / , /^tti

где а* > ajfe.i > а*_2 > • • • > ax ^ 0.

В этом случае будем писать N = (akak_1ak„2 • • Номер г-го

кодового слова кода G(n, fe) представим в виде

где Cifc — 0 при четном к и = — 1 при нечетном к.

2* Разбиения

Пусть n ^ 0 и к > 0. Под разбиением числа п на к частей понимается упорядоченное представление

n = г1 + г2-\ + гк,

где гь 7*2? • • • ? гк — целые неотрицательные числа. Это разбиение будем записывать в виде слова

ГкГк-1-.-7V (1)

Разбиение (1) можно интерпретировать в терминах размещения частиц по ячейкам. Пусть имеется к помеченных ячеек и п неразличимых предметов. Тогда каждому разбиению (1) соответствует единственное размещение п частиц по ячейкам. Список, возникающий при упорядочивании слов (1) в лексикографическом порядке, обозначим через D(nyk). Слова из D(n,k) занумерованы числами от 0 до - 1. Если d(

является г-м словом в D(n, то

.(п + к-1\ 
= + 1 ~ !> 1 ^ 1 ^ к ~

Рассмотрим упорядоченность разбиений (1) согласно коду Грея. Под этим мы понимаем, что список всех разбиений упорядочен так, что каждое размещение частиц по ячейкам получается из предшествующего перемещением единственной частицы из какой-либо ячейки в другую. Определим код Грея следующим образом (что является неболь

шой вариацией из [5]):

С(п,1) = (п), 0C(n,ft-l) "

1<7(п- 1)л

С(п, к) ~ 2С(п — 1, fc — 1) ? &>L

Для решения задачи нумерации С(п, к) понадобится следующее

щ

где

Утверждение 3. Пусть к ^ 1 — произвольное натуральное число. Произвольное N ^ О однозначно представимо в виде

ак-1 к- 1

ак-2 к- 2

N = ek

+ С,

+ Ск

+ Ск

+ £о

 

 где > > а*_2 > • • • > ai > а0, ап € {-1,0}, = 1 я 6

{—1,1} при 0 ^ i ^ к — 1. причем — £{+1 тогда и только тогда, когда раг(щ) ф par(ai+1). Число С равно — 1 при par(k) — раг(а&) и равно 0 при par(k) ф par(ak).

Четность любого числа а определяем следующим образом: par (а) = 1, если а четно, и par (а) = — 1, если а нечетно. Кроме того, полагаем, как обычно, (J) = 1 и ("д1) = 0, что необычно.

Для любого k ^ 1 утверждение 3 позволяет представлять единственным образом любое число N ^ 0 при нечетном к и любое число N > 0 при четном к в виде N = (акак__1.. .а0)е, где ак четно, > ак_г > ■ • ■ > а0 и а0 6 {-1,0}.

Аналогичное представление N — (акак_1.. .а0)0 в случае нечетного ак имеем для любого N ^ 0 при четном к и для любого N > 0 при нечетном

В обоих случаях для N имеем

 

 

ajb-i fc - 1

N = ek

+ £к-1

+ • ■ • + £о 

где ек = 1 и £{ = если раг(а,-) ф par(ai+l), и £в- = -£t-+i, если

раг(а£) = par(ai+i). Эти системы счисления называются «четная смешанная биномиальная система счислению» и «нечетная смешанная биномиальная система счисления>>.

г=1

В дальнейшем нам понадобятся частичные суммы

а0 = 0, а3 = ]Pri? 1 ^j^k. Введем обозначения:

Г 1, если г л нечетно, 6j = { l^j^k ^ 0, если Tj четно,

и

bj := aj + j + Q<j<k-l,

Пусть Ci является г-м кодовым словом кода С (п. к). Если п + к четно, то номер г может быть представлен в четной смешанной системе счисления

'п + к- 1\

- I- (Ьк_1Ьк_2...Ь0)е- (,

где С — 0 при четном п и £ = —1 при нечетном п.

Подобное выражение в нечеткой смешанной системе счисления (е вместо о) верно, если п + к нечетно.

3. Примеры

(i) Если слово 110101 рассмотреть как слово из £(6,4), то его номер представляется в виде (5420),, что соответствует величине Q) + +

(2) + (?) = 5 + 4 + 1 + 0 = 10-

Если слово 110101 рассмотреть как слово из G(6,4), то его номером

окажется число (6531 )a = (*) - Q) + Q - (}) = 15 - 10 + 3 - 1 = 7. (И) Обратно, пусть требуется вычислить /6 £ L(6,4). Записывая

получаем /6 = 101011.

Чтобы получить д6 Е G(6,4), вычисляем 6 - (4 = 6 в чередующейся биномиальной системе счисления для к — 4, получая

ЧЭ-М-(?)-<«>■• 
Поэтому кодовый набор имеет единицы в 5, 4, 2 и 1-й позициях. Следовательно, д6 = 110110.

3. Рассмотрим разбиение с,- := 1201 € С(5,4). Последовательно вычисляем

a ~ (а4,аз,а2,а1,ао) = (5,4,2,2,0), £ = (£3i£2,£U£o) = (1,-1,-1,-1), = (1,0,0,0,0).

С помощью этих параметров находим 63 = 4 + 2 + 1 = 7, b2 ~ 2 + 1 + 0 = 3, bi = 2 + 0 + 0 = 2, Ьо = 0 + (-1) + 0 = -1. Так как числа п + к = 9 и гг = 5 нечетны, то номер разбиения 1 2 0 2 равен

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

Пусть г — номер некоторого слова rkrk_i.. £ С(п,к) и пусть (frfc-A-2 • • -bo)p (р = е или р ~ о) является представлением числа (П+п_1) — 1 — С ~~ ^ Тогда при любом г, 1 ^ г < к, имеем га- = bi — Ь{—\ — 6i+i + Si — 1, где Si G {0,1}, причем 6г — 1 при par(b0) = 1 и 6i = 1 при 1 < г < к и par(bi_i) — par(bt-_2)-

Применим это правило для нахождения с16 G С(5,4). Так как числа п + к = 9 и п = 5 нечетны, то представляя число 55 — 16 + 1 = 40 в нечетной биномиальной системе счисления, находим

40 =,(7420)..

Следовательно, Ь = (ЬзЛАА) = (7,4,2,0) и 6 = (£4,£3-А-Л) = (0,1,1,1). Поэтому г3 = 7- 4- 0 + 1 = 3, г2 = 4- 2-1 + 1-1 = 1 и 7*1 = 2 — 0 — 1 + 1 — 1 = 1. Таким образом, искомым кодовым словом является 0311.

ЛИТЕРАТУРА

1. Кнут Д. Искусство программирования для ЭВМ: В 2 т. М.: Мир, 1976. Т. 1: Основные алгоритмы.
2. Roos С., Snijders A., Zanten A. J. van. Суclonomial number systems and the ranking of lexicographycally ordered constant-sum codes // Arc Combina- toria. 1998. V. 48. P. 173-184.
3. Wilf H. S. Combinatorial algorithms: an update. Philadelphia, PA: SIAM, 1989. VI+47 p. (CBMS-NSF Regional Conf. Ser. in Appl. Math.; V. 55). 
   Zanten A. J. van. Minimal-change codes and number systems. Delft: Univ. of Technology, Fac. of Mathematics and Informatics, 1991. Rept. 91-29.
4. Zanten A. J. van. Index system and separability of constant weight Gray codes // IEEE Trans, on Inform. Theory, 1991. V. 37, N 4. P. 1229-1233.
5. Zanten A. J. van. The ranking problem of a Gray code for compositions // Ars Combinatoria. 1995. V. 41. P. 257-268.

Адрес автора:

A. J. van Zanten Delft University of Technology, Department of Mathematics, P. 0. Box 5031, 2600 GA Delft, The Netherlands. E-mail:

Статья поступила 3 сентября 1998 г.

a.j .vanzanten@twi.tudelft.nl

1 Перевод с английского доклада автора, прочитанного на Международной Сибирской конференции по исследованию операций, которая состоялась в Новосибирске с 22 по 27 июня 1998 г.