Блог

Существует ли разумно вычислимое взаимно однозначное сопоставление/кодирование, которое преобразует:

1. упорядоченные последовательности (c1, c2, ... ) битов, байтов или символов, т. е. строк конечного алфавита, в
2. неупорядоченные наборы байтов, символов или чисел?

Я могу придумать несколько кодировок, но они не очень хороши. Лучшее, что я мог придумать, — это кодирование строки в виде набора пар (расположение символа, сам символ).:

 import random

def set_encode(string):
    return set([str(i)   character for i, character in enumerate(string)])

def recover(set_encoding):
    dictionary = {int(entry[0:-1]) : entry[-1] for entry in set_encoding}
    return ''.join([dictionary[key] for key in sorted(dictionary.keys())])

def validate(set_encode_function):
    for j in range(10):
        random_string = ''.join([chr(random.randint(32, 127)) for i in range(20)])
        result = set_encode_function(random_string)
        if not isinstance(result, set):
            print('Not a set.')
            return False
        if not all([isinstance(element, str) for element in result]):
            print('Not a set of strings.')
            return False
        if not random_string == recover(result):
            print(random_string   ' != '   recover(result))
            return False
        print(' '   random_string   ' => '   str(result)   ' => '   recover(result))
    return True

validate(set_encode)
# True
 

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

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

Я надеюсь на что-то немного более элегантное, чем то, что я написал в приведенном выше фрагменте Python, что-то, что лучше «заполнит» пространство (2) множеств (может быть, что-то с симметричными полиномами?).