OpenEuphoria

Permutations

• Posted by "Unkmar" <L3Euphoria at bellsouth.net> Jun 30, 2004
• 726 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