46 lines
1014 B
Plaintext
46 lines
1014 B
Plaintext
local fmt = require "fmt"
|
|
require "table2"
|
|
|
|
local function are_same(a, b)
|
|
for i = 1, #a do
|
|
if a[i] != b[i] then return false end
|
|
end
|
|
return true
|
|
end
|
|
|
|
local function perfect_shuffle(a)
|
|
local n = #a
|
|
local b = table.rep(n, 0)
|
|
local hsize = n // 2
|
|
for i = 1, hsize do b[i * 2 - 1] = a[i] end
|
|
local j = 2
|
|
for i = hsize + 1, n do
|
|
b[j] = a[i]
|
|
j += 2
|
|
end
|
|
return b
|
|
end
|
|
|
|
local function count_shuffles(a)
|
|
local n = #a
|
|
assert(n % 2 == 0 and n > 1, "Array must be even-sized and non-empty.")
|
|
local b = a
|
|
local count = 0
|
|
while true do
|
|
local c = perfect_shuffle(b)
|
|
++count
|
|
if are_same(a, c) then return count end
|
|
b = c
|
|
end
|
|
end
|
|
|
|
print("Deck size Num shuffles")
|
|
print("--------- ------------")
|
|
local sizes = {8, 24, 52, 100, 1020, 1024, 10000}
|
|
for sizes as size do
|
|
local a = {0}
|
|
for i = 2, size do a[i] = i - 1 end
|
|
local count = count_shuffles(a)
|
|
fmt.print("%-9d %d", size, count)
|
|
end
|