Определим объекты множества P:

  1. a - объект множества P (далее объект)
  2. b - объект
  3. (xy) - объект, где x ∈ P и y ∈ P

примеры объектов: a, b, (ba), ((ab)b), (b(a(bb)))

назовём a и b элементарыми объектами, все остальные - парами, то есть объекты множества P это элементы, пары элементов, пары пар, пары пар пар и т.д.

Определим a как "первый элемент"; установим отношение между элементарными объектами: b следует за a, или b больше a

Можно ли определить отношение порядка для всех объектов? Если да, как перечислить все элементы P от первого(a) до заданного максимального?

задан 2 Янв 18:53

изменен 2 Янв 19:35

@asianirish: пока не очень ясно, что именно Вы хотите сделать. Здесь первая проблема в том, что если мы зададим конечное множество M -- например, M={1,2,3}, то у нас всего три объекта. Новых объектов (11), (12), ... , (33) можно образовать 9, но они уже не будут принадлежать M. Но в принципе можно это всё сформулировать корректно. Получатся скобочные выражения. Вопрос в том, что мы упорядочиваем (все выражения вместе, или для фиксированного числа пар скобок). Кроме того, надо сказать, какими свойствами это новое упорядочение должно обладать, а то ведь можно упорядочить как попало.

(2 Янв 19:16) falcao

@falcao Нужно упорядочить все (или найти алгоритм перечисления всех) объектов - элементарных {1,2,3}, их пар, пар пар, пар пар пар и т.д., то есть мы задаем последний элемента (максимальный, например до ((33)3) и нужно перечисли все объекты от 1 до этого заданного "максимума"). Упорядочить нужно так, чтобы следуя этому порядку перечислить все объекты и не более одного раза.

(2 Янв 19:22) asianirish

((12)3)≠(1(23)), а то бы это были просто числа и упорядочить легко (интуитивно)

(2 Янв 19:25) asianirish
10|600 символов нужно символов осталось
1

@asianirish: Вы не исправили текст как следует, и не ответили на заданные вопросы. Поэтому придётся сказать нечто по принципу "авось подойдёт" :)

У нас есть элементарные объекты 1,2,...,n. В таком виде их и расположим. Скажем, что их ранг равен нулю. Если есть объекты a,b рангов k,m>=0, то рангом пары (ab) считаем число k+m+1. Все объекты будем упорядочивать сначала по рангам, а при фиксированном значении ранга способ будет уточнён ниже.

За объектами ранга 0 пойдут объекты ранга 1, то есть пары вида (ij), где i,j -- элементарные объекты. Их упорядочиваем сначала по номеру первой координаты, потом по второй. Получатся (11), (12), ... , (1n), (21), (22), ... , (2n), ... , (nn).

Теперь объекты ранга 2: это пары вида (ab), где сумма рангов a и b равна 1. Примеры: (i(jk)) или ((ij)k). Первый элемент пары имеет меньший ранг, и такие объекты мы уже упорядочили. Поэтому далее пойдут объекты вида (1(ab)), потом (2(ab)), и так далее до (n(ab)). В каждом случае (ab) пробегает все пары списка из предыдущего абзаца. Затем наступаем черёд (11) на первом месте, и мы выписываем ((11)1), ... , ((11)n). Далее делаем то же самое поочерёдно с (12) вместо (11), и в конце с (nn). Это даёт упорядочение объектов ранга 3.

По тому же принципу располагаем объекты ранга 4 и так далее.

Общее описание: rk(a,b)=rk(a)+rk(b)+1; для двух различных пар объектов считаем (a,b) < (c,d), если либо rk(a,b) < rk(c,d), либо rk(a,b)=rk(c,d), но a < c (рекурсия!), либо rk(a,b)=rk(c,d), a=c, b < d.

ссылка

отвечен 2 Янв 19:34

Да, я тоже интуитивно нащупывал такие "ранги", но придется все время "помнить" при выполнении перечисления все объекты низших рангов, чтобы комбинируя их получать объекты высшего ранга. Или же каждый раз генерировать их динамически - либо память, либо время

(2 Янв 19:40) asianirish

@falcao (Сорри, что не исправил, просто с точки зрения меня, то есть человека-нематиматика, формулировка вопроса казалась однозначной, даже не знал, что можно исправить или пояснить. В любом случае, спасибо за ответ, Ваш "авось" сработал верно;)

(2 Янв 19:45) asianirish
1

@asianirish: у Вас две вещи были в объяснении, на мой взгляд, несовершенны. Если Вы определяете объекты по рекурсии, то сначала задаёте множество элементарных объектов, а потом по рекурсии определяете понятие объекта (всякий ЭО есть О; если a, b -- объекты, то (ab) -- объект; других объектов нет. А в конце не было сказано про подразумеваемые свойства упорядочения.

С рангами работать как раз очень просто. Вообще, эти объекты -- это корневые двоичные деревья, у которых "листы" имеют метки из исходного множества. В таком виде и хранить данные, и сравнивать очень легко (вершины "помнят" ранг).

(2 Янв 19:55) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×82
×8
×4

задан
2 Янв 18:53

показан
133 раза

обновлен
2 Янв 19:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru