1. Permutations
- Posted by Tor Bernhard Gausen <tor.gausen at C2I.NET> May 01, 1999
- 644 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
2. Re: Permutations
- Posted by Grape Vine <chat_town at HOTMAIL.COM> May 01, 1999
- 639 views
<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 besides... only a few hundred.. meybe a few thousnad.. wil lbe understandable Grape _______________________________________________________________ Get Free Email and Do More On The Web. Visit http://www.msn.com
3. Re: Permutations
- Posted by Tor Bernhard Gausen <tor.gausen at C2I.NET> May 02, 1999
- 612 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
4. Re: Permutations
- Posted by Roderick Jackson <rjackson at CSIWEB.COM> May 03, 1999
- 625 views
Well, even if we don't use it for words or sentences, I think I may find = a use for your permutation code. You might be surprised at how often I = find myself trying to manually compute permutations when coding--I've = forgotten the related formulas, and would rather have the computer do = the calculations anyway. Thanks, Rod Jackson ---------- From: Tor Bernhard Gausen[SMTP:tor.gausen at C2I.NET] Sent: Sunday, May 02, 1999 3:26 PM To: EUPHORIA at LISTSERV.MUOHIO.EDU Subject: Re: Permutations 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
- 620 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
6. Permutations
- Posted by "Unkmar" <L3Euphoria at bellsouth.net> Jun 30, 2004
- 613 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
7. Re: Permutations
- Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
- 613 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
8. Re: Permutations
- Posted by "Unkmar" <L3Euphoria at bellsouth.net> Jun 30, 2004
- 641 views
----- Original Message ----- From: "Patrick Barnes" Sent: Wednesday, June 30, 2004 1:48 AM Subject: Re: Permutations > > > 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. It doesn't support more than 17 in length atom size limitation. > One thing is, that the function needs to return indexes, not the > values themselves, so that if I had this: > }}} <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? unkmar
9. Re: Permutations
- Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
- 602 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