Hi there,
it's me again. With another small library. Again.
So anyway - this time it's about permutations. Not sure if there's anything available to handle permutations, so I wrote some functions to do the job.
What do you need permutations for in the first place? I'm glad that you ask! And to be honest, I'm not sure. I need them extremely rarely, but it seemed that they solve a quite specific problem every now and then, which is as follows:
Consider the case that you've got a list of something, e.g. AI units in a game. At some point you want an AI unit to pick a new target to attack. This target should be a random one, but it has to satisfy certain constraints (e.g. the target unit has to be an enemy).
There are many ways to get the job done:
1. Cycle through all units (for i=1 to UnitCount ...) and pick the first one that satisfies the constraints -> problem: units with low IDs will always be chosen first, which is not fair
2. Cycle through all units but starting at a random index (offset = rnd(UnitCount-1) : for i=1 to UnitCount : currentUnit = 1 + ((i+offset) mod UnitCount) ...) and pick the first one that satisfies the constraints -> problem: if there's a block of allied units followed by a block of enemy units, the first one of those enemy units will be attacked more often, which is still not fair
3. Cycle through all units, then make a list of all units who satisfy the given constraints, and pick a random unit out of this list -> fair, but difficult to code and potentially bad performance since this approach calculcates much more than necessary
4. Cycle through all units in completely random order and pick the first one to satisfy the constraints -> problem solved.
Method 4 can be done using permutations. For those of you who haven't heared of them, a permutation is basically a certain order of numbers. For example, (1 2 3 4 5) is a permutation of size 5 with all elements in correct oder. (1 2 3 5 4) is a permutation where 4 and 5 are swapped (so unit with index 5 would be checked before unit 4). (1 2 3 4 4) is not a valid permutation because every element has to be contained in the permutation exactly once.
Now about the library, it provides the following commands:
perm_init() - has to be called once after starting your program
perm_SetAsFirstMemblock(memID) - makes sure the library uses only memblocks with ID >= memID
permID = perm_Make(size) - creates an identity-permutation of given size
perm_Delete(permID) - deletes an existing permutation
index = perm_Get(permID, index) - returns the permutation value of a given index (with 1 <= index <= size)
perm_identity(permID) - sets a permutation to be the identity
perm_Shuffle(permID) - shuffles the permutation
perm_Flip(permID) - flips the values, so that (1 2 3) becomes (3 2 1), i.e. the reverse order
perm_Invert(targetPermID, sourcePermID) - inverts the source permutation, so that a chain of both permutations becomes the identity; all permutations need to have the same size
perm_Chain(targetPermID, sourcePermID1, sourcePermID2) - target permutation becomes the result of chaining both source permutations; all permutations need to have the same size
perm_toString(permID) - converts a permutation into a string, mainly used for debugging purposes
Code:
rem **USAGE SHOWCASE**
rem Initialize permutation-Functions
perm_init()
rem Allow program to use any memblock (starting from ID 1)
perm_SetAsFirstMemblock(1)
rem Create permutations of different size
myPerm1 = perm_Make(5)
myPerm2 = perm_Make(9)
myPerm3 = perm_Make(6)
myPerm4 = perm_Make(6)
myPerm5 = perm_Make(6)
rem Manipulate them
perm_Flip(myPerm2)
perm_Shuffle(myPerm3)
perm_Invert(myPerm4, myPerm3)
perm_Chain(myPerm5, myPerm3, myPerm4)
rem Output
print "In Order: ", perm_toString(myPerm1)
print "Reverse: ", perm_toString(myPerm2)
print "Shuffled: ", perm_toString(myPerm3)
print "Inverted: ", perm_toString(myPerm4)
print "Chained: ", perm_toString(myPerm5)
rem Error-Return
error = perm_Invert(myPerm2, myPerm3)
ink 0x60FFFFFF,0
print
if error < 0 then print "Perm2 and Perm3 cannot be combined due to different sizes!"
wait key
end
rem **END OF SHOWCASE**
#constant perm_FREESTEP = 32
function perm_init()
global perm_firstMemblock as integer = 20
global perm_Count as integer = 0
dim perm_List(0) as perm_ListType
global perm_FreeCapacity as integer = perm_FREESTEP
global perm_FreeCount as integer = 0
dim perm_Free(perm_FreeCapacity)
endfunction
type perm_ListType
exist as boolean
mem as integer
size as integer
endtype
function perm_SetAsFirstMemblock(mem)
perm_firstMemblock = mem
endfunction
function perm_Make(size)
mem = perm__FreeMem()
ID = perm__new()
perm_List(ID).mem = mem
perm_List(ID).size = size
make memblock mem, 2*size
perm_Identity(ID)
endfunction ID
function perm_Delete(list)
perm_List(list).exist = 0
perm__del(list)
endfunction
function perm_Get(list,ID)
r = memblock word( perm_List(list).mem, 2*(ID-1) )
endfunction
function perm_Identity(list)
mem = perm_List(list).mem
for i = perm_List(list).size to 1 step -1
write memblock word mem, 2*(i-1), i
next i
endfunction
function perm_Shuffle(list)
mem = perm_List(list).mem
for i = perm_List(list).size to 1 step -1
src = rnd(i-2)
tmp = memblock word(mem, 2*src)
write memblock word mem, 2*src, memblock word(mem, 2*(i-1))
write memblock word mem, 2*(i-1), tmp
next i
endfunction
function perm_Flip(list)
mem = perm_List(list).mem
size = perm_List(list).size
for i = (size/2) to 1 step -1
src = size - i
tmp = memblock word(mem, 2*src)
write memblock word mem, 2*src, memblock word(mem, 2*(i-1))
write memblock word mem, 2*(i-1), tmp
next i
endfunction
function perm_Invert(list, source)
mem = perm_List(list).mem
memsource = perm_List(source).mem
size = perm_List(list).size
if size = perm_List(source).size
for i = 1 to size
write memblock word mem, 2*(memblock word(memsource, 2*(i-1))-1), i
next i
else
exitfunction -1
endif
endfunction 0
function perm_Chain(list, source1, source2)
mem = perm_List(list).mem
mem1 = perm_List(source1).mem
mem2 = perm_List(source2).mem
size = perm_List(list).size
if size = perm_List(source1).size and size = perm_List(source2).size
for i = 1 to size
write memblock word mem, 2*(i-1), memblock word(mem2, 2*(memblock word(mem1, 2*(i-1))-1))
next i
else
exitfunction -1
endif
endfunction 0
function perm_toString(list)
s$ = ""
mem = perm_List(list).mem
for i = perm_List(list).size to 1 step -1
s$ = str$(memblock word(mem, 2*(i-1))) + " " + s$
next i
endfunction s$
function perm__FreeMem()
m = perm_firstMemblock + perm_Count
while memblock exist(m) : inc m : endwhile
endfunction m
function perm__new()
if perm_FreeCount > 0
ID = perm_Free(perm_FreeCount)
dec perm_FreeCount
else
inc perm_Count
array insert at bottom perm_List()
ID = perm_Count
endif
perm_List(ID).exist = 1
endfunction ID
function perm__del(ID)
perm_List(ID).exist = 0
inc perm_FreeCount
if perm_FreeCount > perm_FreeCapacity
inc perm_FreeCapacity, perm_FREESTEP
array insert at bottom perm_Free(), perm_FREESTEP
endif
perm_Free(perm_FreeCount) = ID
endfunction
