http://qs1969.pair.com?node_id=202143

in reply to Re: Big Picture

Thanks for asking! (but I bet you're sorry you did)

You're not wrong there :) :)

Its situations like this where MathML or equivalent would be really nice, since you could just give me the forumlae :)

In essence, what I understood was the following:

For every permutation 1->n check every permutation 1->n to see if it is equivalent according to the rules. If it is, mark it as such.

Results: a set of groups of permutations who are deemed equivalent.

Are the rules transitive?

My head generated psuedocode something like this (no efficiency or anything, just a general algorithm):

```foreach \$p_1 (permutation(1..n)) {
if (\$tags{\$p_1}) { next; }
\$tags{\$p_1} = \$p_1;
foreach \$p_2 (permutation(1..n)) {
if (rule1(\$p_1, \$p_2) && rule2(\$p_1,\$p_2) && rule3(\$p_1, \$p_2))
+ {
\$tags{\$p_2} = \$p_1;
}
}
}

But that only works if the rules are both transitive and symmetric (you hint that they are but I may be reading it wrong)

I would be interested in the contents of the rules 1->3 if they're not going to make my head ache :)

Replies are listed 'Best First'.
Re: Re: Re: Big Picture
by duelafn (Parson) on Oct 02, 2002 at 13:18 UTC
Actually, I (fortunately) do not need two for loops. The main loop of my code is this:
```  \$i = 'A'; # the class label
for \$n (@temp) {
next if defined \$arrangements{\$n}; # already classified it.

@n = split /,/, \$n;
@classmates = ( \$n, join(',', reverse @n) ); # n and its mirror
@classmates = (@classmates, &M1(@n)); # Maz 1
@classmates = (@classmates, &M2(@n)); # Maz 2
@classmates = (@classmates, &M3(@n)); # Maz 3

&ClassReunion( \$i, \@classmates );
\$i++;
}

M1, M2, and M3 are the three moves (literally, the permutations represent lines in space) which return a new list of permutations. &ClassReunion just does some magic with the label \$i.

M1 is easy, it is just the cyclic permutations of the list Ex: M1(12345) -> 51234, 45123, 34512, 23451. sub M1 { map join(',', @_[\$_..\$#_], @_[0..\$_-1]), 1..\$#_ }

M2 is the inverse permutation. The permutation 4132 is equivalent to tr/1234/4132/. The inverse would then be tr/4132/1234/.

```sub M2 {
my %temp;
@temp{(1..@_)} = @_;
%temp = reverse %temp;
return join(',', @temp{(1..@_)});
}

M3 is, unfortunately much harder to explain, and has much longer code. I've posted a working version of the code on my sratchpad. If you /msg me I will post a better explanation of M3 there as well.

Good Day,
Dean

If we didn't reinvent the wheel, we wouldn't have rollerblades.

@classmates = (@classmates, &M1(@n));
Just a quick check reveals:
```> perl -lwe'use Benchmark "cmpthese";@a=0..8;cmpthese(-8, {push => sub
+{push@x,@a[0..2]}, comb => sub{@y=(@y,@a[0..2])}})'

Benchmark: running comb, push , each for at least 8 CPU seconds ...
comb: 28 wallclock secs (28.33 usr +  0.00 sys = 28.33 CPU) @ 44.7
+9/s (n=1269)
push:  8 wallclock secs ( 8.13 usr +  0.25 sys =  8.38 CPU) @ 4172
+8.04/s (n=349681)
Rate   comb   push
comb  44.8/s     --  -100%
push 41728/s 93056%     --