In need of a sequence iterator.

[BrowserUk]

I want to create an iterator that, given parameters of

my $iter = genIterator( 4, 3 );

print while $_ = $iter->();

will produce the following sequence (scrunched and formatted to show the sequence) in that order.

0 00 000 0000 0001 0002
     001 0010 0011 0012
     002 0020 0021 0022
  01 010 0100 0101 0102
     011 0110 0111 0112
     012 0120 0121 0122
  02 020 0200 0201 0202
     021 0210 0211 0212
     022 0220 0221 0222
1 10 100 1000 1001 1002
     101 1010 1011 1012
     102 1020 1021 1022
  11 110 1100 1101 1102
     111 1110 1111 1112
     112 1120 1121 1122
  12 120 1200 1201 1202
     121 1210 1211 1212
     122 1220 1221 1222
2 20 200 2000 2001 2002
     201 2010 2011 2012
     202 2020 2021 2022
  21 210 2100 2101 2102
     211 2110 2111 2112
     212 2120 2121 2122
  22 220 2200 2201 2202
     221 2210 2211 2212
     222 2220 2221 2222

I can do it with a (non-tail) recursive generator, but the lists get very large very quickly and most of the time I only need the next one or two at any given time.

I can 'convert' that generator into an iterator using a thread as a coroutine, but I don't want that dependancy.

Ideally, this would work the same way as tye''s NextPermute(), in that it would take a ref to an array (or possibly a string) and modify it to produce the in the sequence.

After 3 days of trying wrap my brain around this, a reference to some C code, or even what this sequence is called (lexical something?), would help.

[!1]

How about:

sub genIterator {
    my ($len,$count) = @_;
    my @list = ();
    return sub {
        if (@list == 0 || @list < $len) {
            push @list, 0;
        } else {
            $list[-1]++;
            while (@list && $list[-1] >= $count) {
                pop @list;
                $list[-1]++ if @list;
            }
        } 
        return @list ? join("", @list) : undef;
    }

}

Note that the code to iterate should be:

my $iter = genIterator(4,3);
print while defined($_ = $iter->());

since 0 evaluates as false.

[BrowserUk]

That works perfectly. Thankyou.

Looks so easy ... when someone else does it:)

[!1]

Now that I've had a chance to sleep, here's a solution that accepts either a count or an arrayref.

sub genIterator {
    my ($len,$array) = @_;
    $array = [0..$array-1] if $array =~ /^\d+$/;
    die "Don't know what to do with $array" unless ref $array eq "ARRA
+Y";
    my @list = ();
    return sub {
        return undef unless @$array;
        if (@list < $len) {
            push @list, 0;
        } else {
            $list[-1]++;
            while (@list && $list[-1] >= @$array) {
                pop @list;
                $list[-1]++ if @list;
            }
        } 
        return @list ? join("", @$array[@list]) : undef;
    }
}

[hv]

As far as I can see this is just counting in base $count, in which case I'd probably use a string instead:

  sub genIterator {
    my($len, $count) = @_;
    my $cur = '';
    my $lastdig = $count - 1;
    return sub {
      if (length($cur) < $len) {
        $cur .= '0';
      } else {
        $cur =~ s/([^$lastdig])$lastdig*\z/$1 + 1/e
             or $cur = undef;
      }
      $cur;
    }
  }

Of course this assumes $count doesn't exceed 10; this approach gets a bit more complex if you need to deal with larger bases.

Hugo

[BrowserUk]

The $count can get upto 255 (and theoretically beyond with unicode). The numbers are eventually packed to form a binary string of codepoints that increment, magic string auto-increment style, but starting at chr(0) and modulo alphabet size.

I'm currently limiting my thinking to 8-bit ascii bytes, but notionally the alphabet could be larger with unicode.

The actual keys involved (made up from an arbitrary alphabet) are translated to chr(0) ... chr(alphabet max).

[ikegami]

There's gotta be a better way than this:

use strict;
use warnings;

sub genIterator_helper($\@) {
   my ($base, $list) = @_;
   my $i = $#$list;
   for (;;) {
      last if (++$$list[$i] < $base);
      $$list[$i] = 0;
      return undef unless $i;
      $i--;
   }
   return 1;
}

sub genIterator {
   my ($max_digits, $base) = @_;
   my @list;
   foreach my $num_digits (1..4) {
      my @digits = (0) x $num_digits;
      do {
         push(@list, join('', @digits));
      } while (genIterator_helper($base, @digits));
   }
   @list = sort { $a cmp $b } @list;
   return sub { shift(@list) };
}

my $iter = genIterator(4, 3);
print "$_$/" while defined ($_ = $iter->());

[tye]

This is a pretty straight-forward use of Algorithm::Loops's NestedLoops():

#!/usr/bin/perl -w
use strict;

use Algorithm::Loops qw( NestedLoops );

sub genIter
{
    my( $len, $base )= @_;
    return scalar NestedLoops(
        [ ( [ 0 .. ($base-1) ] ) x $len ],
        { OnlyWhen => 1 },
    );
}

my( $len, $base )= ( @ARGV, 4, 3 );
my $iter= genIter( $len, $base );
my @list;
while( @list= $iter->() ) {
    print @list, $/;
}

[Zed_Lopez]

Could you show us your recursive code? It'd make me surer I understand the sequence.

[BrowserUk]

I had to untangle it from it's dependancies with the object it is a method of, but this produces the sequence as show (prior to scrunching and formatting):

#! perl -slw
use strict;

sub gen {
    my( $len, $depth ) = @_;
    return () unless $len;
    return map {
        my $pre = $_;
        ( $pre, map{ $pre . $_ } gen( $len -1, $depth )  );    
    } 0 .. $depth - 1;
}

print for gen( 4, 3 );

[kelan]

I solved this question on my own in Haskell at the time it was posted. It involved using a couple nested maps and some other things that were quite complicated to get my head around (as I remember). However, recently I've been experimenting with using lists as monads, and found my solution to this puzzle. Reworking it from that point of view, it becomes nice and clear. I know you're dabbling with Haskell, so I thought you might be interested.

import Char  -- for intToDigit

gen :: Int -> Int -> [String]
gen 0 _ = []
gen len max = do
  d  <- map intToDigit [0 .. max-1]
  ds <- [] : gen (len-1) max
  return (d:ds)

Below is the first version I came up with. You might not want to read it. It's rather ungainly.

gen :: Int -> Int -> [String]
gen 0 _ = []
gen len max =
  concat (
    map (
          \digit -> [digit] : (
                                map ( digit : )
                                    ( gen (len - 1) max )
                              )
        )
        ( map intToDigit [0 .. max-1] )
  )

[BrowserUk]

I've pretty much given up on Haskell. It's fine if all you want to do is prove that your new variation of Fibonacci compiles okay, but if you want to actually see the output, forget it. Much less if you want to read your data from an external source.