Technicalia
|
It is worth reproducing the algorithm here. The implementation in builtins\permute.e also contains
some additional commented-out variations that may or may not provide slightly more suitable ordering.
global function permute(integer n, sequence set)
--
-- return the nth permute of the given set.
-- n should be an integer in the range 1 to factorial(length(set))
--
sequence res
integer w
n -= 1
res = set -- so permute(n,string/seq) yields string/seq
for i=length(set) to 1 by -1 do
w = remainder(n,i)+1
res[i] = set[w]
set[w] = set[i]
n = floor(n/i)
end for
return res
end function
There is no corresponding library routine for generating combinations. The following template routine shows one way
to generate combinations of a given set. It is anticipated that you would need to modify this for each specific use.
procedure comb(integer pool, needed, done=0, sequence chosen={})
if needed=0 then -- got a full set
?chosen -- or call a routine[id] or whatever
return
end if
if done+needed>pool then return end if -- cannot fulfil
-- get all combinations with and without the next item:
done += 1
comb(pool,needed-1,done,append(chosen,done))
comb(pool,needed,done,chosen)
end procedure
comb(3,2) -- outputs {1,2} {1,3} {2,3}
And here is a version that returns all combinations - many other variations are possible
function comb(sequence res, pool, integer needed, done=0, sequence chosen={})
if needed=0 then -- got a full set
res = append(res,chosen)
elsif done+needed<=length(pool) then
-- get all combinations with and without the next item:
done += 1
res = comb(res,pool,needed-1,done,append(chosen,pool[done]))
res = comb(res,pool,needed,done,chosen)
end if
return res
end function
?comb({},{4,5,6},2) -- {{4,5},{4,6},{5,6}}
A practical application can be seen in demo\rosetta\Sudoku.exw
|