Permutations
- Posted by "Unkmar" <L3Euphoria at bellsouth.net> Jun 30, 2004
- 614 views
----- Original Message ----- From: "Patrick Barnes" Sent: Tuesday, June 29, 2004 8:31 PM Subject: Re: Derangements > > > Something like this? > > > > sequence perm_set > > perm_set = "ABCDEFGHIJKLMNOPQR" > > > > function perm(atom n) > > sequence result > > atom pstep > > integer level, i2 > > sequence remains > > > > result = perm_set > > remains = perm_set > > pstep = factorial(length(perm_set)) > > if (n >= pstep) then > > return -1 > > elsif (n = floor(n)) then > > return -1 > > elsif (0 > n) then > > return -1 > > else > > i2 = length(perm_set) > > for i = 1 to length(perm_set)-1 do > > pstep /= i2 > > i2 -= 1 > > level = floor(n/pstep) + 1 > > n = remainder(n, pstep) > > result[i] = remains[level] > > remains = remains[1..level-1] & remains[level+1..length(remains)] > > end for > > result[length(perm_set)] = remains[1] > > return result > > end if > > end function > > So, what does it do?? > or how does it work?? > > The application I want to use this for involves positions in a large > 2D array, and a reproducible way to step through those positions. 100 > percent coverage is not required, but no position should be visited > twice, as that would overwrite existing data. > > Speed of access is not that important, as most of the time it will be > accessed sequentially. > That function is a permutation function. It will generate any requested permutation based on index and permutation set. Example: perm_set = "ABCD" "ABCD" = perm(0) "ABDC" = perm(1) "DCBA" = perm(23) Nothing between 0 to 23 will be repeated. If you use a larger set such as perm_set ="0123456789" "0123456789" = perm(0) "0123456798" = perm(1) "0123456879" = perm(2) "9876543210" = perm(10*9*8*7*6*5*4*3*2) 10*9*8*7*6*5*4*3*2 = 3,628,800 PS: This does not handle derangements. unkmar