time python3 Task1.combination.using-lib.py > /dev/null
________________________________________________________
Executed in 213.78 secs fish external
usr time 52.31 secs 0.00 millis 52.31 secs
sys time 20.40 secs 4.54 millis 20.39 secs
It was faster until I tested with (:M(50) :N(5)) when compared to my code
but with higher number, it is getting slowr.
I think that finding combination isn't necessarily written using recursive calling.
so this is my first "working" solution.
it is possible to use some list of words (ex) "a", "b", "c" ) instead of number.
#!/usr/bin/env perl
# -*- Mode: cperl; cperl-indent-level:4; tab-width: 8; indent-tabs-mode: nil -*-
# Copyright (c) 2013,2020 JEON Myoungjin
use strict; use warnings;
package List::Selection::Combination;
#use Carp qw(croak);
#use version 0.77 our $VERSION = version->declare( '0.1.3' );
sub make_combination_no_recursive ( $$ ) {
my $N = $_[0]; # number of selection
my @elements = @{ $_[1] }; # reference !!!
my $M = scalar @elements;
my @result;
# minimum sanity check
if ( $M < $N ) {
warn "unable to choose $N from given selection of $M";
return ();
}
my ( @room, # number of spaces(rooms) each finger can move
@pos, # current position of finger
$next_id # of finger to move
);
# set initial values ...
{
# each finger can move to right number of ( M-N ) space(s).
@room = ( $M-$N ) x $N;
@pos = 0..($N - 1);
$next_id = $N - 1; # id starts from zero
# initial record; note: use not index number but real value
push @result, [ map { $elements[$_] } @pos ];
#print "@pos\n";
}
{
if ( $room[$next_id] > 0 ) {
# can move to right so .. do it.
--$room[$next_id];
++$pos[$next_id];
# and make a record
push @result, [ map { $elements[$_] } @pos ];
#print "@pos\n";
redo;
}
else {
# no more room to move
# so find the next finger to move.
my $found = 0;
for ( my $i = $next_id; $i > 0; --$i ) {
if ( $room[ $i-1 ] > 0 ) {
$next_id = $i-1;
$found = 1;
last;
}
}
if ( $found ) {
#move all the fingers which are starts from $next_id to last one
@pos[ $next_id..($N-1) ]
= ( $pos[$next_id]+1 ) ..( $pos[$next_id] + ($N-$next_id) );
@room[ $next_id..($N-1) ] # note: all finger has same room
= ( $room[ $next_id ] - 1 ) x ( $N - $next_id );
# and make a record
push @result, [ map { $elements[$_] } @pos ];
#print "@pos\n";
# next finger to move will be ($N-1)
# or will find next loop;
$next_id = ($N-1);
redo; # if we can move next finger
}
}
}
return @result;
}
package main;
my $m = shift // 5;
my $n = shift // 2;
my @result = List::Selection::Combination::make_combination_no_recursive
( $n, [ 1..$m ] );
for my $r (@result) {
print "@r\n";
}
below code is almost same as above but assume use only digits.
and in format the challenge wants me to do.
# -*- Mode: cperl; cperl-indent-level:4; tab-width: 8; indent-tabs-mode: nil -*-
# Copyright (c) 2013,2020 JEON Myoungjinuse strict; use warnings;
#use feature qw /say/;package List::Selection::Combination;
#use Carp qw(croak);
#use version 0.77 our $VERSION = version->declare( '0.1.3' );sub print_combination_no_recursive ( $$ ) {
my $N = $_[0]; # number of selection
my @elements = @{ $_[1] }; # reference !!!
my $M = scalar @elements;local $" = ",";
if ( $M < $N ) {
warn "unable to choose $N from given selection of $M";
return ();
}print "[ ";
my ( @room, # number of spaces(rooms) each finger can move
@pos, # current position of finger
$next_id # of finger to move
);{
@room = ( $M-$N ) x $N;
@pos = 1..$N;
$next_id = $N - 1; # id starts from zero
print "[@pos]";
}{
if ( $room[$next_id] > 0 ) {
--$room[$next_id];
++$pos[$next_id];
print ", [@pos]";
redo;
}
else {
my $found = 0;
for ( my $i = $next_id; $i > 0; --$i ) {
if ( $room[ $i-1 ] > 0 ) {
$next_id = $i-1;
$found = 1;
last;
}
}if ( $found ) {
@pos[ $next_id..($N-1) ]
= ( $pos[$next_id]+1 ) ..( $pos[$next_id] + ($N-$next_id) );
@room[ $next_id..($N-1) ]
= ( $room[ $next_id ] - 1 ) x ( $N - $next_id );
print ", [@pos]";$next_id = ($N-1);
redo;
}
}
}
print " ]";
}package main;
my $m = shift // 5;
my $n = shift // 2;List::Selection::Combination::print_combination_no_recursive
( $n, [ 1..$m ] );
and performance is quite excellent.time perl Task1.combination.pl 100 5 | wc -l 75287520
________________________________________________________
Executed in 34.37 secs fish external
usr time 34.98 secs 906.00 micros 34.98 secs
sys time 2.19 secs 105.00 micros 2.19 secsI'm a chef and haven't got enough time to code these days.
]]>
but this kind of challenge makes me feel alive.
sub readOnly ( $; ) { shift->read_write }
or
sub validate ( $;$ ) {
my $error;
...
$error; # but which semicolon appended
}
but I couldn't recommend it for any other uses otherwise many people who is not accustomed to perl will be confused. (-:
]]>It's an method to avoid loading too much,
and I'm looking for other methods as well, in the other cases, such as loading just necessary plugins by check and then load actually into the current process.
It's not a best way though. because it has overhead to fork another process and read hard disk more often. It's totally an option.
thank you for reply. (-:
]]>package MyApp;
# I just want to know WNOHANG from sys_wait_h ... [-;
our $WNOHANG_VALUE ||= `$^X -MPOSIX=:sys_wait_h -e "print WNOHANG;"`;
sub WNOHANG () { $WNOHANG_VALUE }
!!'^^';
sigh maybe useful for a long-time running program if you are sensitive to memory usage..
]]>