Permutations by swapping: Difference between revisions
m
no edit summary
mNo edit summary |
|||
Line 1,588:
"There are 32 permutations of 5 items."</lang>
=={{header|Julia}}==
Nonrecursive (interative):
<lang julia>
function johnsontrottermove!(ints, isleft)
len = length(ints)
function ismobile(pos)
if isleft[pos] && (pos > 1) && (ints[pos-1] < ints[pos])
return true
elseif !isleft[pos] && (pos < len) && (ints[pos+1] < ints[pos])
return true
end
false
end
function maxmobile()
arr = [ints[pos] for pos in 1:len if ismobile(pos)]
if isempty(arr)
0, 0
else
maxmob = maximum(arr)
maxmob, findfirst(x -> x == maxmob, ints)
end
end
function directedswap(pos)
tmp = ints[pos]
tmpisleft = isleft[pos]
if isleft[pos]
ints[pos] = ints[pos-1]; ints[pos-1] = tmp
isleft[pos] = isleft[pos-1]; isleft[pos-1] = tmpisleft
else
ints[pos] = ints[pos+1]; ints[pos+1] = tmp
isleft[pos] = isleft[pos+1]; isleft[pos+1] = tmpisleft
end
end
(moveint, movepos) = maxmobile()
if movepos > 0
directedswap(movepos)
for (i, val) in enumerate(ints)
if val > moveint
isleft[i] = !isleft[i]
end
end
ints, isleft, true
else
ints, isleft, false
end
end
function johnsontrotter(low, high)
ints = collect(low:high)
isleft = [true for i in ints]
firstconfig = copy(ints)
iters = 0
while true
iters += 1
println("$ints $(iters & 1 == 1 ? "+1" : "-1")")
if johnsontrottermove!(ints, isleft)[3] == false
break
end
end
println("There were $iters iterations, and this is the same as $(high-low+1) factorial, or $(factorial(high-low+1)).")
end
johnsontrotter(1,4)
</lang>
Recursive:
<lang julia>
function johnsontrotter(low, high)
function permutelevel(vec)
if length(vec) < 2
return [vec]
end
sequences = []
endint = vec[end]
smallersequences = permutelevel(vec[1:end-1])
leftward = true
for seq in smallersequences
for pos in (leftward ? (length(seq)+1:-1:1): (1:length(seq)+1))
push!(sequences, insert!(copy(seq), pos, endint))
end
leftward = !leftward
end
sequences
end
permutelevel(collect(low:high))
end
for (i, sequence) in enumerate(johnsontrotter(1,4))
println("""$sequence, $(i & 1 == 1 ? "+1" : "-1")""")
end
</lang>
=={{header|Kotlin}}==
| |||