Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Re: Big Picture

by duelafn (Parson)
on Oct 01, 2002 at 00:39 UTC ( #201910=note: print w/replies, xml ) Need Help??

in reply to Big Picture
in thread constructing large hashes

Why, I'm classifying codimension two hyperplane arrangements in C2. What else would I be doing?

Basically, I need to create all of the permutations of 1 to n, then for each one, apply a set of three rules which will give me a list of different permutations which shall be deemed "equivalent" to the current one. I give each of these a common tag and then move on.

I do perform quite a few lookups to determine whether I have already applied the set of rules to a particular permutation through one of its equivalent representations. This is important since each of the rules can give me many equivalent permutations.

At the end I perform one final clean up since sets of equivalent permutations may have been labeled with different tags. I make note of these occurrances during the first pass through though, so the final cleanup is trivial.

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

Update: Sorry, we're in C2 not C4

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

Replies are listed 'Best First'.
Re: Re: Big Picture
by PhiRatE (Monk) on Oct 01, 2002 at 23:11 UTC

    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 :)

      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,

      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% --
        I know your arrays aren't growing linearly like this, so the difference wouldn't be so extreme.


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://201910]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2023-09-24 19:43 GMT
Find Nodes?
    Voting Booth?

    No recent polls found