How to get the translation seed?

by emilbarton (Scribe)
 on Aug 31, 2011 at 11:15 UTC Need Help??
emilbarton has asked for the wisdom of the Perl Monks concerning the following question:

I asked indirectly a question in Re: Length obfuscation that I'd like to extend here to a wider audience:

Is there a means to obtain the translation seed "n0123.." permutationally?

The translation seed allows to shift any permutational string to the right by one sign. What I mean by permutationally is that you can obtain your result with the help of the function perm() primarily. For example the natural suite "0123..n" can be obtained permutationally by repeating y = perm(x,x) and then y1 = perm(y,x) enough times with y1,y2,etc. for any permutation x. In Re: Length obfuscation I think that with some more efforts, the function comp() could be reduced to a particular composition of calls to perm().

I know it's more a math question than a Perl one but I found that it was not a bad idea to ask for the wisdom of Perl monks - who are used to deal with generic problems of this kind after all. Getting the translation seed permutationally should make a system of permutational functions more efficient.

```sub perm {
my (\$target,\$agent) = @_;
my @targ = split //,\$target;
my @perm = split //,\$agent;
my \$res;
for (my \$i = 0; \$i < (@perm); \$i++){ \$res .= \$perm[\$targ[\$i]] }
return \$res;
}

Comment:

By "permutation" we understand any permutation of the distinct elements pertaining to the natural - or well ordered - suite "01..n". The function perm() above accepts two permutations in the same base n+1 < 11. For this function, "012", "3102", "7465023198", are valid permutations when "013", "3112" or "7465023198A" are not.

Replies are listed 'Best First'.
Re: How to get the translation seed?
by jethro (Monsignor) on Aug 31, 2011 at 14:53 UTC

Lets talk some more basics: perm(x,y) simply permutes y with the permutation x, right? And the regex in the first post of the original thread (lets call it origperm()) does a few different(!) but fixed (if I didn't read the code wrong) permutations.

Now you could just find out the permutation that is the sum of all permutations done on the string. That would be quite fast but not very exiting. Instead you want to calculate each single permutation done by each single invocation of the origperm regex, so that y=perm(yourcalculatedperm_n,y) is equivalent to the n-th invocation of y=origperm_n(y) ?

If Ithis is not the case (and I suspect I'm wrong somewhere), please enlighten me/us.

PS: I have not tried to decipher comp(). I assume that it would be a lot faster if you just tell us what it does in mathematical terms. This might be true for your whole question. A math question is best asked in math language

This question has not much to see with what you call origperm(), nor with comp(). Besides I don't know much about maths and I don't know how to say what I've said in a better way, sorry. I hope this will not impede you and others to think about the meaning of what I've asked.

If you want a clue about what I expect, consider this. We have seen that the well ordered suite can be obtained by means of perm() after a certain amount of iterations. This is because permutations are cyclic. Now each permutation then has a certain cyclic value. I can imagine that a particular means of obtaining "n012.." could make use of this cyclic value and thus the rule might look like:

For any permutations x and y, if x has a cyclic value of (max cyclic value for the base) and y (medium cyclic value for the base) then "n012.." can be obtained by the following composition of perm()...

But this is just imagination about what I would like to know.

Re: How to get the translation seed?
by emilbarton (Scribe) on Sep 13, 2011 at 18:58 UTC

And now ladies and gentlemen, for all those of you who were secretely anxious to get an answer to my question, I propose the following one.

The natural suite (== "01..n") being the first of a well ordered set @S of \$b! members in base \$b, one can get the translation seed (== "n012..") permutationally by permuting element number (\$b-1)! (== "0n..21") with element number \$b! (== "n..210") in the same set:

\$tran = perm(\$S[(\$b-1)!],\$S[\$b!])

I keep waiting for your insights on this subject, and for other answers to the same question.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://923401]
Approved by planetscape
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2017-08-20 02:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (313 votes). Check out past polls.

Notices?