Для массива из 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 возможных перестановок).
(Перестановки == "возможности"; факториал = L! = L * (L-1) * ... * 1 = именно то, как вы рассчитываете возможности)
Этот метод также не намного больше, чем хранение индекса перестановки. Вы можете хранить 128 элементов в случайном порядке в 1024 битах (32 х 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 или любой другой язык.