I'm not sure I fully understood your suggestions here, perhaps again because of my own difficulties explaining the problem in the first place.

First, I would assign each element a number corresponding to its row: 0,.., $dim-1. Then I would add $dim to each element if it was equal to 'x' and 2*$dim if it was equal to '*'.

Hmm, so something like:

  my @bits = (0 .. $dim - 1);
  for (0 .. $dim - 1) {
    $bits[$_] += 2 * $dim if $v & (1 << $_);
  }
  $bits[$height] += $dim;
  my @bitmap = map $_ % $dim, sort { $b <=> $a } @bits;
[download]

If I understand this correctly, this should produce the same @bitmap that my current code calculates. I'm not sure about the efficiency: the dominant order of my current code for that calculation is O($dim), but I suspect replacing many O($dim) perl opcodes with an O($dim log $dim) C-coded sort will probably win on the constants. And the resulting code is certainly a lot clearer than I had.

Now that you have the permutation, simply map all the other columns using the permutation. If you have many columns, I'd suggest creating a lookup table for the mapping. You are done.

This bit I don't understand. Having built the mapping of bits (rows), I then applied it with this code:

  # we now know what row should go where, so build and return the mapp
+ed result
  my @invmap = sort { $bitmap[$a] <=> $bitmap[$b] } 0 .. $dim - 1;
  my @vmap = (0);
  for (0 .. $dim - 1) { 
    my $mapped = 1 << $invmap[$_];
    push @vmap, map $_ + $mapped, @vmap;
  } 
  return ($bitmap[$height], [ @$args[ @vmap ] ]);
[download]

This first inverts the mapping with a sort, then uses the inverse mapping of bits to construct a mapping for each of the 2 ^ $dim bit patterns, then applies that map to the current $args arrayref. Is that significantly different from what you're suggesting here?

In the broader picture, your transformations induce an automorphism (permutation) on the array of bits, which by projection down to your $args array, induce an automorphism of the $args array itself. An interesting exercise would be to act directly on the $args array itself, skipping the bitwise sorting entirely.

I'm not sure I understand this either: are you suggesting removing the need for the rearrangement by recoding the rest of the program to work on the array in place, eg using an auxiliary array to describe the bit-order? That might be interesting, but the primary benefit of the rearrangement is to make logically equivalent arglists identical so that memoization can short-circuit the calculations. If I don't do the actual rearrangement, I still need to identify a signature for the arglist that encapsulates the same rearrangement for the memoization to work, and I suspect that means doing the work of the actual rearrangement in all but name.

Apologies if I've wildly misunderstood any of the things you were trying to say.

Hugo

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.