Алгоритм получения комбинации по проценту (неограниченной длины)

Question

Например есть следующая комбинация (все возможные комбинации из цифр от 1 до 2 длиной 3).

111 - 0%
112 - 14%
121 - 28%
122 - 42%
211 - 57%
212 - 71%
221 - 85%
222 - 100%

Комбинации цифр где каждая цифра может иметь диапазон в данном случае например от 1 до 2 включительно. Мне надо получить именно комбинацию 71% (например 71% эта комбинация 212 если кому не понятно).

Я в результате 1-го года размышлений как это можно сделать естественно не генерируя заранее готовые комбинации и выбирая из них уже по % я придумал алгоритм основанный на процентах от процентах но он не подходит для работы с большими по длине комбинациями (например 10000000 длина где цифры от 0 до 9 включительно), максимум комфортно это 300-1000 знаков, как бы он подходит, но для этого мне надо брать число процента с 0-ми равное по длине больше чем текста на этой странице и при нормализации по следующему % у меня уйдет n-е количество минут а то и часов.

Как получить по проценту любую комбинацию по ограничениям?

Answer 1

Попробую накидать схему на Вашем примере. Трехсимвольные комбинации из цифр 1 и 2. Таких комбинаций всего 8.

Считаем, сколько процентов составляет одна комбинация. c=100/7
Имея проценты, например, 71%,находим номер этой комбинации n = 71/c, номера начинаются с нуля.
Так как используются только две цифры, переводим полученный номер в двоичную запись и представляем строкой.
каждую цифру в строке увеличиваем на значение младшей используемой цифры - в вашем случае на 1. А если бы использовались, например, цифры 6 и 7, то увеличивали бы на 6.
Результат получен.

Кажется, должно работать...

Answer 2

На степень b умножаем, округляем, b-ичную запись получаем.

Функция to_digits переводит число в цифры по заданной базе. Питон не поддерживает эту функциональность из коробки. Для скорости пришлось сделать "разделяй и властвуй":

def to_digits(k, n, b):

    def digits(k, n):
        if n <= 256:
            for _ in range(n):
                yield 1 + k % b
                k //= b
        else:
            n1 = n // 2
            n2 = n - n1
            k2, k1 = divmod(k, b ** n1)
            yield from digits(k1, n1)
            yield from digits(k2, n2)

    return reversed(tuple(digits(k, n)))


t1, t2, t3 = input().split()
n = int(t1)
b = int(t2)
p = float(t3)
pn, pd = p.as_integer_ratio()

m = b ** n - 1
k = (m * pn + (100 * pd) // 2) // (100 * pd)

sep = '' if b < 10 else '_'
print(sep.join(str(d) for d in to_digits(k, n, b)))

$ echo 3 2 71 | python strange-percents.py
212

$ echo 3 3 71 | python strange-percents.py
311

$ echo 3 9 71 | python strange-percents.py
745

$ echo 3 10 71 | python strange-percents.py
8_1_10

$ time echo 1166400 2 71 | python strange-percents.py
2122121222...1111212111

real  0m2.152s
user  0m2.076s
sys   0m0.020s

$ time echo 1166400 2 86 | python strange-percents.py
2212221111...2121112222

real  0m2.166s
user  0m2.076s
sys   0m0.032s

Answer 3

А что тут год думать? заменяем цифры в порялке возрастания на 01...n, получаем все числа в n-1-чной системе счисления, и все.

71%? Без вопросов. Для вашего случая всего 8 значений, значит, так как 0 соотетствует 0%, диапазон равен 7 значений.

0.71*7 ~5? значит, 5 == 101, или, по-вашему, 212. На что вы потратили год?

Для 123 - тут может быть всего 3^3=27 значений, значит, 0.71*(27-1) = 18.46. Округляем до 18, в троичной системе счисления это 200, значит, переводя в ваши цифры, 311.

БЛОГ НА HUSL

Алгоритм получения комбинации по проценту (неограниченной длины)

Ответы (3 шт):