Учитывая лексикографическое число перестановок, можно ли получить в нем любой элемент в O (1)

Ответ 1

Секрет для этого заключается в "подсчете в базовом факториале".

Таким же образом, что 134 = 1 * 10 ^ 2 + 3 * 10 + 4, 134 = 5! + 2 * 3! + 2! = > 10210 в факториале (включая 1!, исключить 0!). Если вы хотите представить N!, вам понадобится N ^ 2 базовых десяти цифры. (Для каждой факториальной цифры N максимальное число, которое оно может удерживать, равно N). До некоторой степени путаницы в том, что вы называете 0, это факториальное представление является именно лексикографическим числом перестановки.

Вы можете использовать это понимание для решения проблемы Эйлера 24 вручную. Поэтому я сделаю это здесь, и вы увидите, как решить вашу проблему. Мы хотим миллионную перестановку 0-9. В факториальном представлении мы берем 1000000 = > 26625122. Теперь, чтобы преобразовать это в перестановку, я беру свои цифры 0,1,2,3,4,5,6,7,8,9, а первое число равно 2, что является третьим (это может быть 0), поэтому я выбираю 2 в качестве первой цифры, тогда у меня есть новый список 0,1,3,4,5,6,7,8,9, и я беру седьмое число, которое 8 и т.д., И я получаю 2783915604.

Однако это предполагает, что вы начинаете свой лексикографический порядок в 0, если вы действительно начинаете его с одного, вы должны вычесть 1 из него, что дает 2783915460. Это действительно миллионная перестановка чисел 0-9.

Вы можете, очевидно, отменить эту процедуру и, следовательно, легко конвертировать назад и вперед между лексиографическим номером и перестановкой, которую он представляет.

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

Ответ 2

Ваш вопрос немного спорный, потому что ваш размер ввода для произвольного индекса перестановки имеет размер журнала (N!) (при условии, что вы хотите представить все возможные перестановки), который является Theta (N log N), поэтому, если N действительно большой, то просто чтение ввода индекса перестановки займет слишком много времени, конечно, намного дольше, чем O (1). Возможно, можно сохранить индекс перестановки таким образом, чтобы, если вы уже сохранили его, вы можете получить доступ к элементам в O (1) раз. Но, вероятно, любой такой метод будет эквивалентен простому сохранению перестановки в непрерывной памяти (которая также имеет размер Theta (N log N)), и если вы сохраняете перестановку непосредственно в памяти, тогда вопрос становится тривиальным, если вы можете сделать O (1 ) доступ к памяти. (Однако вам все равно нужно учитывать размер битовой кодировки элемента, который является O (log N)).

В духе вашей аналогий шифрования, возможно, вы должны указать небольшой SUBSET перестановок в соответствии с некоторым свойством и спросить, возможен ли доступ к элементу O (1) или O (log N) для этого небольшого подмножества.

Ответ 3

Edit:

Я неправильно понял вопрос, но он не был в отходах. Мои алгоритмы позволяют мне понять: факторическое представление лексикографического числа перестановки почти такое же, как сама перестановка. На самом деле первая цифра факторического представления такая же, как и первый элемент соответствующей перестановки (предполагая, что ваше пространство состоит из чисел от 0 до N-1). Зная это, на самом деле нет смысла хранить индекс, а не сама перестановка. Чтобы узнать, как преобразовать лексикографическое число в перестановку, читайте ниже. См. Также эту ссылку в Википедии о коде Lehmer.

Оригинальное сообщение:

В пространстве S есть N элементов, которые могут заполнить первый слот, что означает, что есть (N-1)! элементы, начинающиеся с 0. Итак, i/(N-1)! это первый элемент (назовем его "а" ). Подмножество S, начинающееся с 0, состоит из (N-1)! элементы. Это возможные перестановки множества N {a}. Теперь вы можете получить второй элемент: его я (% ((N-1)!)/(N-2)!). Повторите процесс, и вы получили перестановку.

Обратное так же просто. Начните с я = 0. Получите второй последний элемент перестановки. Создайте набор из двух последних элементов и найдите в нем позицию элемента (его либо 0-й элемент, либо 1-й), позвоните в эту позицию j. Тогда я + = j * 2!. Повторите этот процесс (вы также можете начать с последнего элемента, но он всегда будет 0-м элементом возможностей).

Java-ish pesudo code:

find_by_index(List N, int i){
    String str = "";
    for(int l = N.length-1; i >= 0; i--){
        int pos = i/fact(l);
        str += N.get(pos);
        N.remove(pos);
        i %= fact(l);
    }
    return str;
}

find_index(String str){
    OrderedList N;
    int i = 0;
    for(int l = str.length-1; l >= 0; l--){
        String item = str.charAt(l);
        int pos = N.add(item);
        i += pos*fact(str.length-l)
    }
    return i;
}

find_by_index должен выполняться в O (n), предполагая, что N предварительно упорядочено, а find_index - O (n * log (n)) (где n - размер пространства N)

Ответ 4

После некоторых исследований в Wikipedia я отбросил этот алгоритм:

def getPick(fact_num_list):
    """fact_num_list should be a list with the factorial number representation, 
    getPick will return a tuple"""
    result = [] #Desired pick
    #This will hold all the numbers pickable; not actually a set, but a list
    #instead
    inputset = range(len(fact_num_list)) 
    for fnl in fact_num_list:
        result.append(inputset[fnl])
        del inputset[fnl] #Make sure we can't pick the number again
    return tuple(result)

Очевидно, что это не достигнет O (1) из-за того, что нам нужно "выбрать" каждое число. Поскольку мы выполняем цикл for и, таким образом, предполагая, что все операции O (1), getPick будет работать в O (n).

Если нам нужно преобразовать из базы 10 в факториальную базу, это вспомогательная функция:

import math

def base10_baseFactorial(number):
    """Converts a base10 number into a factorial base number. Output is a list
    for better handle of units over 36! (after using all 0-9 and A-Z)"""
    loop = 1
    #Make sure n! <= number
    while math.factorial(loop) <= number:
        loop += 1
    result = []
    if not math.factorial(loop) == number:
        loop -= 1 #Prevent dividing over a smaller number than denominator
    while loop > 0:
        denominator = math.factorial(loop)
        number, rem = divmod(number, denominator)
        result.append(rem)
        loop -= 1
    result.append(0) #Don't forget to divide to 0! as well!
    return result

Опять же, это будет работать в O (n) из-за while s.

Суммируя все, лучшее время, которое мы можем найти, O (n).

PS: Я не являюсь носителем английского языка, поэтому могут возникнуть ошибки правописания и фразировки. Извиняйтесь заранее, и дайте мне знать, если вы не можете обойти что-то.

Ответ 5

Все правильные алгоритмы доступа к k-му элементу перестановки, хранящиеся в фактографической форме, должны считывать первые k цифр. Это связано с тем, что независимо от значений других цифр среди первого k, имеет значение, является ли непрочитанная цифра 0 или принимает максимальное значение. Это можно увидеть, проследив каноническую правильную программу декодирования в двух параллельных исполнениях.

Например, если мы хотим декодировать третью цифру перестановки 1? 0, то для 100 эта цифра равна 0, а для 110 эта цифра равна 2.