Myoungjin Jeon

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.