## Late Weekly challenge 67 #1 only

I wrote some library to make combination in 2013.
I was overwhelming when I found this challenge but I found that it is buggy !!!

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 Myoungjin

use 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 secs

```

I'm a chef and haven't got enough time to code these days.
but this kind of challenge makes me feel alive.

```