Too many permutations?

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

•  Subject
• Author
• Posted on
I have a list with 64 entries and I wanted to run an operation on every
permutation of the list (to see what is the "best" order of the list
elements).  But the number of permutations would be (I think) 64! which
is 1.27 x 10^89.

I can reduce the number of entries to 56 but that doesn't make it doable:
still 7.11 x 10^74 permutatations.  I'm guessing this is hopeless in Perl
or any other language for that matter??

John Black

Re: Too many permutations?

Well, if iterating over each permutation takes only 1 millisecond then
you only have to wait somewhere around 10^80 years :-)

Instead of using brute force you need to find a smarter algorithm, mabye
even an algorithm that may return a sub-optimal but close-enough result.
What that algorithm might be depends very much on the actual problem,
but some keywords you might want to look up: branch-and-bound, dynamic
programming, NP-complete

jue

Re: Too many permutations?

El 14/01/16 a las 18:12, J�rgen Exner escribió:

You could find a satisfactory solution if you could write the fitness
function of what you want. There are a bunch of algorithms that
overcomes the problem of try each combination, as simulated annealing,
genetic algorithms, greedy random adaptative search, etc. These,
combined with the logic you program in the function to improve the
solutions could give you a more than aceptable solution.

--
http://gamo.eu.pn/
The generation of random numbers is too important to be left to chance

Re: Too many permutations?

"Keep trying the random permutations until the time is up. Define the
best which was found as 'satisfactory'." ...

Re: Too many permutations?

True, that's one approach.
Unfortunately I am afraid in his case he will be able to enumerate only
a somewhat small percentage of the whole search space ;-)

jue

Re: Too many permutations?

El 14/01/16 a las 23:16, J�rgen Exner escribió:

So what? Is there anybody telling to try brute force approach?
Actually, a problem solved is of the kind of timetable for a crew.
That's 5 persons x 2^(3 shifts x 365 days) possibilities. Somewhat
the problem is "easy" because there are a lot of solutions families
that satisfies the constraints, and you are not trying to find one.
That's not uncommon, that a NP-hard problem turns out to be "easy" if
you try the heuristic approach.

You have examples in my web. I.e. 6x6 puzzle.

--
http://gamo.eu.pn/
The generation of random numbers is too important to be left to chance

Re: Too many permutations?

jurgenex@hotmail.com says...

Some good news.  Sorry I can't really go into the scenario but I
realized I don't really have a 64 entry list.  I have 8 lists of 8.
I.e. I don't need any of the 8 in a given list to exchange with anything
in one of the other 7 lists.  I just need permutations within the 8
lists.  So my permutation space is really only 8*8! which is no big
deal.

But I still need a method to create the permutations.  I can't get
something from cpan (on a site install) and I didn't want to re-invent
the wheel.  So I copied this sub directly out of the book Higher Order
Perl:

sub permute {

my @items = @_;
my \$n = 0;

return Iterator {
\$n++, return @items if \$n==0;
my \$i;
my \$p = \$n;

for (\$i=1; \$i<=@items && \$p%\$i==0; \$i++) {
\$p /= \$i;
}

my \$d = \$p % \$i;
my \$j = @items - \$i;
return if \$j < 0;

@items[\$j+1..\$#items] = reverse @items[\$j+1..\$#items];
@items[\$j,\$j+\$d] = @items[\$j+\$d,\$j];

\$n++;
return @items;
};
}

I do not yet really understand this sub.  I don't know what is going on
with the "return Iterator {" thing.  What the heck is that?  How do you
return something like that?  It looks like some kind of a sub within a
sub?  I've never seen anything like that and I'm not too sure what it is
doing.

But right now I am just trying to figure out how to use it; not so much
how it works.  I was hoping it would just work but its not doing
anything so I'm not sure I'm using it correcly.  My understanding is I
supply an array representing a permutation and the sub returns the next
permutation?

But if I run this code:

my @initial = (0, 1, 2, 3, 4, 5, 6, 7);
my @next = permute(@initial);
print "@initial\n";
print "@next\n";

I just get the same array back out of permute():

\$ perl permute.pl
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

Am I even calling permute() correctly?

John Black

Re: Too many permutations?

El 22/01/16 a las 06:17, John Black escribió:

No. use Algorithm::Combinatorics qw(permute);
There are two ways of use:
- Slurping all the permutations into an array
- Via a iterator called 'next'
HTH

--
http://gamo.eu.pn/
The generation of random numbers is too important to be left to chance

Re: Too many permutations?

Thanks, I know there are cpan solutions available but I am using a site
install where I can't add modules.

John Black

Re: Too many permutations?

On Thursday, January 21, 2016 at 9:17:18 PM UTC-8, John Black wrote:

I think "return Iterator " was intended as an anonymous subroutine...
So, if you replace that with:  return sub { ... };

then, eg, invoke as:

my @permuted;
my \$iterator = permute(@initial);
print "permute: @permuted " while @permuted = \$iterator->();

Re: Too many permutations?

derykus@gmail.com says...

Wow, this worked!  Thanks.  The book is missing the keyword 'sub'.  I
would have thought they would have tested code going into a book?

I still cannot make heads or tails out of what is going on here.  This
whole thing is blowing my mind because I thought I "knew" Perl to a good
working degree.  So there is a sub within a sub such then when you run:

my \$iterator = permute(@initial);

\$iterator becomes some kind of code reference?  To what?  To the inner
sub?  And then if you run:

@permuted = \$iterator->();

You get an array because this calls the inner sub of the permute sub??

Very confused.  Why do this sub within a sub thing?  Couldn't this have
been done far more straightforwardly with two separate subs, or one sub?

John Black

Re: Too many permutations?

On Friday, January 22, 2016 at 9:25:38 AM UTC-8, John Black wrote:

Yes, you're on the right track.  A really good intro to the subject of
anonymous subroutines which act as "closures" is found here:

perldoc -q closure

The explanation there has links to perlref and perlsub for more details.

Re: Too many permutations?

my \$it = permute(0..7);

while ( my @P = \$it->() ) {
print "@P\n";
}

sub permute
{
my (@items,\$n) = (0,@_);

sub
{
\$n++, return @items if \$n==0;
my \$i;
my \$p = \$n;
for (\$i=1; \$i<=@items && \$p%\$i==0; \$i++) { \$p /= \$i }
my \$d = \$p % \$i;
my \$j = @items - \$i;
return undef if \$j < 0;
@items[\$j+1..\$#items] = reverse @items[\$j+1..\$#items];
@items[\$j,\$j+\$d] = @items[\$j+\$d,\$j];
\$n++;
@items
}
}

Re: Too many permutations?

This doesn't work but thanks anyway.

John Black

Re: Too many permutations?

maybe the source is strong at my pc because it works fine here.
it is actually the code you post before

Re: Too many permutations?

I don't know - I'm sure its close - I didn't spend a lot of time to
debug.  I got tons of warnings but even if I comment out #use warnings, I
get two 0s in the list for some reason.

Using "my \$it = permute(0..3);" to keep the output manageable, here are
the first and last few that come out:

0 0 1 2 3
0 0 1 3 2
0 0 2 1 3
0 0 2 3 1
0 0 3 1 2
0 0 3 2 1
0 1 0 2 3
0 1 0 3 2
0 1 2 0 3
0 1 2 3 0
0 1 3 0 2
...
3 2 0 1 0
3 2 1 0 0
3 2 1 0 0

The original code (plus the modifications from C.DeRykus) works.

John Black

Re: Too many permutations?

as fast as possible (for perl)

my  @items = ('a', 'b', 'c');
sub CallBack { print "@_\n" }

my @I = 0 x scalar @items;
my \$code;
for (0..\$#items) {
\$code .= "for (\$I[\$_]=\$I[\$_-1]; \$I[\$_]<\@items;\$I[\$_]++){\n" }
\$code .= 'CallBack(@items[@I])'. '}' x scalar @items;
#print \$code;

eval \$code;

Re: Too many permutations?

This doesn't work but thanks anyway.

John Black

Re: Too many permutations?

as the other people said you should describe the problem