Как создать длинный вложенный список, который можно сортировать?

Question

Описание:

Я хочу создать список, в идеале неограниченный, но я могу жить как минимум с 1000 исходных элементов или около того, который имеет неограниченное количество списков, которые могут быть созданы между каждым изначальные элементы списка и то же самое между каждым впоследствии созданным элементом, до бесконечности.

Идея 1:

Список начинается с 1 элемента, назовем его x.Затем я могу добавить 1 элемент слева или справа от x, если слева он должен быть меньше, то справа он должен быть больше.Одна из попыток - использовать целые числа, поэтому, если x равно 500, у нас теперь есть [499, 500, 501], и мы продолжаем идти [498, 499, 500, 501, 502].Теперь мне нужно добавить элемент между элементами, например между 500 и 501, поэтому давайте используем десятичные дроби и добавляем 500.5, затем элемент между 500.5 и 501, так что это будет500.75 и т. Д. *

Проблема:

Этот метод будет запускаться только 38 раз, пока мы не достигнем 500.999999999999, после чего любая программа, которую я запустил, либо язык программирования(JavaScript) или Excel прекратит добавлять десятичные позиции.

Кроме того, я смогу перейти между 500.5 и 500.75 и снова создать список между ними, который остановится на 500.749999999999 после37 итераций и т. Д.

Идея 2:

Использование букв.Результат может быть отсортирован в алфавитном порядке.Начнем с L, слева добавим K, справа добавим M: [K, L, M].Между L и M мы можем создать LM, затем между LM и M мы можем добавить LMM и т. Д.

Проблема:

Ограничениес этим, это то, что слева мы можем перейти только к A, а справа мы можем достичь только Z, намного меньше, чем желаемая 1000 предметов.

У кого-нибудь есть какие-либо предложения?Возможно сочетание букв и цифр?(Но как это отсортировать?) Или, может быть, какая-то формула, о которой я не знаю?Спасибо.

Answer 1

Я могу придумать несколько решений.Что будет работать лучше всего, зависит от вашего языка программирования.

Во-первых, вы могли бы продолжить свое представление о числах с плавающей запятой, но использовать пакет с расширенной точностью или числа с плавающей запятой с повышенной точностью.В Python вы можете использовать стандартный модуль decimal.Прежде чем начать, вы можете установить точность своих номеров достаточно высоко, чтобы покрыть возможное количество добавленных номеров.Для 1000 дополнений будет достаточно 302 десятичных знака.Некоторые языки или пакеты имеют неограниченную точность, поэтому вам не нужно заранее устанавливать точность.

Во-вторых, вы можете использовать рациональные числа.В Python есть модуль fractions, а поскольку целые числа Python имеют произвольную точность, то же самое можно сказать и о дробях.

В-третьих, вы можете реализовать свои собственные дроби, используя два набора натуральных чисел.Кортеж (a, b) 'представляет собой положительное рациональное число a/b, но вы реализуете эти «рациональные числа» самостоятельно.Вы начинаете с (1, 1).Тогда (a, b) меньше (c, d) тогда и только тогда, когда a*d < b*c.Вы делаете кортеж (a, b) меньшим с (a, b+1) и увеличиваете его с (a+1, b).Вы получаете кортеж между (a, b) и (c, d) с (a+c, b+d).Это работает лучше всего, если целые числа имеют произвольную точность.

В-четвертых, вы могли бы использовать 2-кортежа с первым элементом - целым числом, а вторым - строкой.Кортеж до (0, 'A') равен (-1, 'A'), а кортеж после (0, 'Z') равен (0, 'ZA'), или вы можете использовать (1, 'Z').Как вы уже знаете, кортеж между (0, 'A') и (0, 'B') равен (0, 'AB').

В-пятых, вы можете смоделировать дерево двоичного поиска (BST).Поскольку вам нужен список, а не фактический BST, вы имитируете его, делая каждый элемент в своем списке представляющим узел в BST, где 'L' представляет левого сына, а 'R' представляет правого сына.Вы начинаете список с одного элемента '', пустой строки, которая представляет корень BST.Чтобы получить элемент слева от самого левого элемента, объедините 'L' до конца строки, чтобы получить нужный элемент.Чтобы получить элемент справа от самого правого элемента, объедините 'R' до конца строки.Чтобы получить предмет между двумя смежными предметами, мы понимаем, что один должен быть начальной частью другого.Если левый элемент длиннее правого, объедините 'R' с левым элементом.Если левый элемент короче правого, соедините 'L' с правым элементом.Обратите внимание, что этот метод изоморфен использованию дробей, начинающихся с 1, а добавление 'L' изоморфно вычитанию степени 1/2, а добавление 'R изоморфно добавлению степени 1/2.Но строки избегают проблемы конечной точности.

Я могу подумать и о других возможностях.Если бы я реализовал вашу идею, я бы использовал fractions в Python, так как они хорошо интегрированы в язык.Тогда заказ, печать и т. Д. Уже обрабатываются на языке.