96 lines
1.5 KiB
AutoHotkey
96 lines
1.5 KiB
AutoHotkey
#NoEnv
|
|
SetBatchLines -1
|
|
Process, Priority,, high
|
|
|
|
output := "Derangements for 1, 2, 3, 4:`n"
|
|
|
|
obj := [1, 2, 3, 4], objS := obj.Clone()
|
|
Loop ; permute 4
|
|
{
|
|
obj := perm_NextObj(Obj)
|
|
If !obj
|
|
break
|
|
For k, v in obj
|
|
if ( objS[k] = v )
|
|
continue 2
|
|
output .= ObjDisp(obj) "`n"
|
|
}
|
|
output .= "`nTable of n, counted, calculated derangements:`n"
|
|
|
|
Loop 10 ; Count !n
|
|
{
|
|
obj := []
|
|
count := 0
|
|
output .= A_Tab . (i := A_Index-1) . A_Tab
|
|
Loop % i
|
|
obj[A_Index] := A_Index
|
|
objS := obj.Clone()
|
|
Loop
|
|
{
|
|
obj := perm_NextObj(Obj)
|
|
If !obj
|
|
break
|
|
For k, v in obj
|
|
if ( objS[k] = v )
|
|
continue 2
|
|
count++
|
|
}
|
|
output .= count . A_Tab . cd(i) . "`n"
|
|
}
|
|
output .= "`nApproximation of !20: " . cd(20)
|
|
MsgBox % Clipboard := output
|
|
|
|
perm_NextObj(obj){ ; next lexicographic permutation
|
|
p := 0, objM := ObjMaxIndex(obj)
|
|
Loop % objM
|
|
{
|
|
If A_Index=1
|
|
continue
|
|
t := obj[objM+1-A_Index]
|
|
n := obj[objM+2-A_Index]
|
|
If ( t < n )
|
|
{
|
|
p := objM+1-A_Index, pC := obj[p]
|
|
break
|
|
}
|
|
}
|
|
If !p
|
|
return false
|
|
Loop
|
|
{
|
|
t := obj[objM+1-A_Index]
|
|
If ( t > pC )
|
|
{
|
|
n := objM+1-A_Index, nC := obj[n]
|
|
break
|
|
}
|
|
}
|
|
|
|
obj[n] := pC, obj[p] := nC
|
|
return ObjReverse(obj, objM-p)
|
|
}
|
|
|
|
ObjReverse(Obj, tail){
|
|
o := ObjClone(Obj), ObjM := ObjMaxIndex(O)
|
|
Loop % tail
|
|
o[ObjM-A_Index+1] := Obj[ObjM+A_Index-tail]
|
|
return o
|
|
}
|
|
|
|
ObjDisp(obj){
|
|
For k, v in obj
|
|
s .= v ", "
|
|
return SubStr(s, 1, strLen(s)-2)
|
|
}
|
|
|
|
|
|
cd(n){ ; Count Derangements
|
|
static e := 2.71828182845904523536028747135
|
|
return n ? floor(ft(n)/e + 1/2) : 1
|
|
}
|
|
ft(n){ ; FacTorial
|
|
a := 1
|
|
Loop % n
|
|
a *= A_Index
|
|
return a
|
|
}
|