Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View

I have a puzzle to solve, for pleasure rather than gain, and I'd like to
find a perl solution to it because I'm not a mathematician, and
therefore will crack the answer with brute force rather than brains.

I need to calculate all permutations of a list. For the purpose of the
puzzle the mirror images are equivalent ((1234 == 4321) either can be in
my results, but not both.

I'm looking at the documentation for Algorithm::Permute, and I've looked
at List::Permutor. I'm happy to let either one run and generate my
permutations, but I could do with an effective way of weeding out
mirrors of permutations I've already got. I could put each one into a
hash, the key being the permutation, and then:

  my $reversed = scalar reverse $permutation;
  next if ($results);

I just wondered if there's a better way, so that I don't have to
calculate all of the permutations when I'll only need 50% of them.

Thank you for any suggestions.


Justin C, by the sea.

Re: Permutations

Quoted text here. Click to load it

See "perldoc -q permute"

Quoted text here. Click to load it

Maybe: for each generated number compute the matching mirrored number
and keep the generated number only if it is the smaller (or larger) of
the two numbers or if the two numbers are identical. This way you don't
need to repeatedly scan through the already computed numbers.


Re: Permutations

Quoted text here. Click to load it

Note that if the elements are distinct, the reverse will never equal
the generated permutation. In addition, you only need compare the first
element of the permutation with the last element and keep only those
where the first is less than the last: e.g. compare the '1' and the '4'
in the example 1234 == 4321.

Jim Gibson

Re: Permutations

Justin C wrote:
Quoted text here. Click to load it

Just as long as rotational permutations are not also considered
equivalent, per that very long thread a few months ago :)

Quoted text here. Click to load it

Absolutely, as long as you are only counting rather than enumerating, as
as long as and each symbol appears only once:

my $reversed = scalar reverse $permutation;
if ($reversed lt $permutation) { $count++};

You don't need to store all or half of the permutations this way.

If symbols can appear more than once, then you would need to generate
only distinct permutations (I've previously posted code to do that) and
you would have to address palindromes, for example by counting each one
as only 1/2 of a count.

Quoted text here. Click to load it

You could do that too, but much less easily.  The standard permutation
algorithms have no way to prune entire branches of the permutation
chains, so you would have to implement your own.  Whether doing that is
more amusing than solving the math problem is left as an exercise for
the reader :)

In the case of 1234, if you decide to count only the lesser member of
each mirror pair, then you would anchor the first and last symbol to be
from the list:

And then would have to permute only the remaining two symbols
(represented by the periods).  The six other "bookmark" pairs would not
be needed to be generated, as they clearly fail the lesser member criterion.


Site Timeline