Биты и байты: храните инструкции по перемешиванию

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

Пример: Перетасовка 1 4 5: возможные варианты:

1 4 5   [0]
1 5 4   [1]
4 1 5   [2]
4 5 1   [3]
5 1 4   [4]
5 4 1   [5]

Чтобы сохранить перестановку 415, вы просто сохраните 2 (нулевой индекс).

Если у вас есть правильный порядок для исходного набора элементов, вы можете сделать правильный порядок для набора перестановок, перебирая элементы от наименьшего порядка к наибольшему для самого левого элемента, одновременно перебирая оставшиеся элементы для следующего. поместите вправо и так далее, пока не дойдете до самого правого элемента. Вам не нужно будет хранить этот массив, вам просто нужно будет снова сгенерировать перестановки в том же порядке, чтобы «распаковать» сохраненное целое число.

Однако попытка сгенерировать все перестановки одну за другой займет значительное время, если не считать самого маленького из наборов. Вы можете использовать наблюдение, что первые (N-1)! перестановки начинаются с 1-го элемента, вторые (N-1)! перестановок начинаются со второго элемента, затем для каждой перестановки, которая начинается с определенного элемента, 1-е (N-2)! перестановок начинаются с первого из оставшихся элементов и так далее и так далее. Это позволит вам «упаковать» или «распаковать» элементы в O(n), за исключением сложности фактического создания факториалов, а также деления и модуля целых чисел произвольной длины, которые будут несколько существенными.

Вы правы в том, что для хранения только перестановки данных, а не самих данных, вам потребуется столько бит, сколько ceil(log2(permutations)). Для N элементов количество перестановок равно factorial(N) или N!, поэтому вам понадобятся биты ceil(log2(factorial(N))) для хранения только перестановки N элементов без сохранения самих элементов.

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

Обычный алгоритм перетасовки и один из немногих беспристрастных — это перетасовка Фишера-Йейтса. . Каждая итерация алгоритма принимает случайное число и меняет местами два места в зависимости от этого числа. Сохранив список этих случайных чисел, вы сможете позже воспроизвести точно такую ​​же перестановку.

Для массива из L элементов, почему бы не упаковать порядок в биты L*ceil(log2(L))? (ceil(log2(L)) — количество битов, необходимых для хранения L уникальных значений). Например, вот представление "неперетасованного" перемешивания элементов по порядку:

L=2:  0 1       (2 bits)
L=3:  00 01 10     (6 bits)
L=4:  00 01 10 11   (8 bits)
L=5:  000 001 010 011 100 (15 bits)
...
L=8:  000 001 010 011 100 101 110 111 (24 bits)
L=9:  0000 0001 0010 0011 0100 0101 0110 0111 1000 (36 bits)
...
L=16: 0000 0001 ... 1111  (64 bits)
L=128: 00000000 000000001 ... 11111111 (1024 bits)

Основное преимущество этой схемы по сравнению с ответом @ user470379 заключается в том, что извлечь индексы действительно легко, просто сдвиньте и замаскируйте. Нет необходимости регенерировать таблицу перестановок. Это должно быть большой победой для большого L: (Для 128 элементов есть 128! = 3,8562e+215 возможных перестановок).

(Permutations == "возможности"; factorial = L! = L * (L-1) * ... * 1 = точно так же, как вы вычисляете возможности)

Этот метод также не намного больше, чем сохранение индекса перестановки. Вы можете хранить перетасовку из 128 элементов в 1024 битах (32 x 32-битных целых числах). Для хранения 128! требуется 717 бит (23 целых числа).

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

Вот реализация на Ruby, которая должна работать для произвольных размеров. «Инструкция по перемешиванию» содержится в массиве instruction. Первая часть вычисляет перетасовку, используя версию алгоритма Фишера-Йейтса, упомянутую @Theran.

# Some Setup and utilities
sizeofInt = 32  # fix for your language/platform
N = 16
BitsPerIndex = Math.log2(N).ceil
IdsPerWord = sizeofInt/BitsPerIndex

# sets the n'th bitfield in array a to v
def setBitfield a,n,v
  mask = (2**BitsPerIndex)-1
  idx = n/IdsPerWord
  shift = (n-idx*IdsPerWord)*BitsPerIndex
  a[idx]&=~(mask<<shift)
  a[idx]|=(v&mask)<<shift
end

# returns the n'th bitfield in array a
def getBitfield a,n
  mask = (2**BitsPerIndex)-1
  idx = n/IdsPerWord
  shift = (n-idx*IdsPerWord)*BitsPerIndex
  return (a[idx]>>shift)&mask
end  

#create the shuffle instruction in linear time 
nwords = (N.to_f/IdsPerWord).ceil  # num words required to hold instruction
instruction = Array.new(nwords){0} # array initialized to 0

#the "inside-out" Fisher–Yates shuffle
for i in (1..N-1)
  j = rand(i+1)
  setBitfield(instruction,i,getBitfield(instruction,j))
  setBitfield(instruction,j,i)
end

#Here is a way to visualize the shuffle order
#delete ".reverse.map{|s|s.to_i(2)}" to visualize the way it's really stored
p instruction.map{|v|v.to_s(2).rjust(BitsPerIndex*IdsPerWord,'0').scan(
    Regexp.new('.'*BitsPerIndex)).reverse.map{|s|s.to_i(2)}}

Вот пример применения перемешивания к массиву символов:

A=(0...N).map{|v|('A'.ord+v).chr}
puts A*''

#Apply the shuffle to A in linear time
for i in (0...N)
 print A[getBitfield(instruction,i)]
end
print "\n"

#example: for N=20, produces
> ABCDEFGHIJKLMNOPQRST
> MSNOLGRQCTHDEPIAJFKB

Надеюсь, это не будет слишком сложно преобразовать в javascript или любой другой язык.

Извините, если это уже было рассмотрено в предыдущем ответе, но впервые эти ответы совершенно чужды мне. Я мог бы упомянуть, что знаю Java и JavaScript и ничего не смыслю в математике... Так что log2, permutations, factorial, well-ordering мне неизвестны.

И вдобавок ко всему, я закончил (снова) использовать StackOverflow в качестве белой доски, чтобы написать свой вопрос и ответить на вопрос в моей голове 20 минут спустя. Я был занят некомпьютерной жизнью и, зная StackOverflow, решил, что уже слишком поздно экономить более 20% легко теряемого времени.

В любом случае, заблудившись во всех трех существующих ответах. Вот ответ, который я знаю

(написано на Javascript, но должно быть легко перевести 20 строк иностранного кода на выбранный вами язык)

(увидеть это в действии можно здесь: http://jsfiddle.net/M3vHC)

Редактировать: спасибо AShelly за эту уловку: это не сработает (станет сильно предвзятым), если длина ключа больше 12, при условии, что ваши целые числа 32-битные (более 19 если ваши целые 64-битные)

var keyLength = 5
var possibilities = 1
for(var i = 0; i < keyLength ; i++)
    possibilities *= i+1 // Calculate the number of possibilities to create an unbiased key
var randomKey = parseInt(Math.random()*possibilities) // Your shuffle instruction. Random number with correct number of possibilities starting with zero as the first possibility
var keyArray = new Array(keyLength) // This will contain the new locations of existing indexes. [0,1,2,3,4] means no shuffle [4,3,2,1,0] means reverse order. etcetera
var remainsOfKey = randomKey // Our "working" key. This is disposible / single use.
var taken = new Array(keyLength) // Tells if an index has already been accounted for in the keyArray
for(var i = keyArray.length;i > 0;i--) { // The number of possibilities for the first item in the key array is the number of blanks in key array.
    var add = remainsOfKey % i + 1, remainsOfKey = parseInt(randomKey / i) // Grab a number at least zero and less then the number of blanks in the keyArray
    for(var j = 0; add; j++) // If we got x from the above line, make sure x is not already taken
        if(!taken[j])
            add--
    taken[keyArray[i-1] = --j] = true // Take what we have because it is right
}
alert('Based on a key length of ' + keyLength + ' and a random key of ' + randomKey + ' the new indexes are ... ' + keyArray.join(',') + ' !')