OpenEuphoria

1. Permutations

• Posted by Tor Bernhard Gausen <tor.gausen at C2I.NET> May 01, 1999
• 783 views
• Last edited May 02, 1999

Here's a function that returns the maximum possible
permutations (combinations) of all the top level elements
(which are different from eachother) in a sequence .

-- code starts here (but you knew that, didn't you?).

function faculty (integer i1)
    atom i2
    i2=1
    for n=1 to i1 do
        i2 *= n
    end for
    return i2
end function

function count_elements(sequence s1)
    integer found
    sequence s2, s3
    s2={}
    s3={}
    for n=1 to length(s1) do
        found = 0
        for m=1 to length(s2) do
            if not compare(s1[n],s2[m]) then
                s3[m] += 1
                found=1
            end if
        end for
        if found=0 then
            s2 &= {s1[n]}
            s3 &= 1
        end if
    end for
    s1={}
    for n=1 to length(s3) do
        if s3[n] > 1 then
            s1 &= s3[n]
        end if
    end for
    return s1
end function

global function permutate (sequence s)
    sequence elements
    atom divisor
    divisor = 1
    elements=count_elements(s)
    for n=1 to length(elements) do
        divisor *= faculty (elements[n])
    end for
    return faculty (length(s)) / divisor
end function

--- end

Example:

permutate ("euphoria")

returns 40320 while

permutate("sequence")

(same length) returns only 6720.

Subsequences can of course also be permutated.


Did you know that ... the sentence "how on earth can this function
ever be useful to anyone?" can be recombined in as much as
1.898648171e+55 different ways?


Best Regards,

Tor Gausen

3. Re: Permutations

• Posted by Tor Bernhard Gausen <tor.gausen at C2I.NET> May 02, 1999
• 754 views
• Last edited May 03, 1999

Yep!

First of all: you're right: that should be "factorial"
not faculty (I just took a chance with a direct
Norwegian-English translation. Some day I'll
learn that that's hardly ever a good idea).

> >Did you know that ... the sentence "how on earth can this function
> >ever be useful to anyone?" can be recombined in as much as
> >1.898648171e+55 different ways?

> Hmmmmmm i must be counting it wrong.... i get
> 55 letters(spaces included) and factorial 55 is
> 1.269640335366e+73

Now try dividing that with the product of the factorials of
the numbers of all equal elements. Would you say that
the word LEE is an interesting acronym of the name
LEE, just because the two E's has swapped places? 

> besides... only a few hundred.. meybe a few thousnad..
> will be understandable.

Good point, Grape. One could create a function that found
all the combinations that produced only english words
(using the word list in Junko's spellchecker for instance),
but even with a short sentence, like the one I used with 55
letters, one would have to spell-check an awful amount of
possible sentences, and given the fact that a human STILL
would have to go through all those correctly spelled
sentences to see whether they 1) actually meant something
(if that's a point), most of them would probably prove
surrealistic, 2) that the grammer was correct (not much of
a chance). Finally it would STILL be a completely useless
routine; who would ever want to code it? 


More of those Best Regards,

Tor Gausen

5. Re: Permutations

• Posted by Terry Moriarty <terry at EDERNEY.IDPS.CO.UK> May 25, 1999
• 775 views

On Sat, 1 May 1999 16:16:04 PDT, Grape Vine <chat_town at HOTMAIL.COM> wrote:

><snip>
>
>>Did you know that ... the sentence "how on earth can this function
>>ever be useful to anyone?" can be recombined in as much as
>>1.898648171e+55 different ways?
>>
>>
>>Best Regards,
>>
>>Tor Gausen
>HMmmmmm i must be counting it wrong.... i get 55 letters(spaces included)
>and factorial 55 is 1.269640335366e+73

Can I clarify?

56 letters including 10 spaces and a question mark.

allowing for duplicates (i.e. 3 h's, 6 n's)
and the fact that I can't tell the difference between nnnnnn and nnnnnn
then you have

        = 56! / (10! * 3! * 5! * 6! * 6! * 3! * 2! * 4! * 2! * 2! * 2! * 2!
* 3!)

        = 1.898648171e+55 different ways?



>
>
>besides... only a few hundred.. meybe a few thousnad.. wil lbe
>understandable
>
>Grape
>
>


Jjustt  ryyyin gtohe llllp.

All the best

Terry

7. Re: Permutations

• Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
• 751 views

> That function is a permutation function.
> It will generate any requested permutation based on index and
> permutation set.

Ah, I see. It would take a while to generate if the set was 1 million
objects in length, though. It *would* be more secure than a fixed
offset from the last point to the next.

One thing is, that the function needs to return indexes, not the
values themselves, so that if I had this:

x = perm(original_sequence, number)
new = {}
for a = 1 to length(x) do
    new &= original_sequence[ x[a] ]
end for
--at this point, new contains the permutation

how would I alter the code snippet you gave me?

-- 
MrTrick

9. Re: Permutations

• Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
• 742 views

> > }}}
<eucode>
> > x = perm(original_sequence, number)
> > new = {}
> > for a = 1 to length(x) do
> >     new &= original_sequence[ x[a] ]
> > end for
> > --at this point, new contains the permutation
> > </eucode>
{{{

> > how would I alter the code snippet you gave me?
> >
> > --
> > MrTrick
> 
> There are a couple ways of doing this.
> One method is a wrapper around what I have already
> created.
> Another requires a reworking of my code.
> I'm still not sure what 'number' is suppose to be.
> unless it is an permutation index value.
> A value that states *which* permutation to return
> indexing values for?

Basically, yes. I would like something like that.
The *number* would be something like a symmetric key.
ie, the sequence is scrambled in that way, and sent off.
All others can't decode the sequence unless they know the
value of the number used, or use a brute force method.

The other method works quickly, and on large-sized arrays, but is
limited in key values.
Roughly about length / 5.
-- 
MrTrick