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

# get the next seed (represented as an array of chars)
sub nextseed($) {
  my $array_ref = shift;
  my $i = (@$array_ref) - 1;
  #print join("", @$array_ref); print "\n";
  while ( ($i > 0) && !(@$array_ref[$i-1] eq '#' && (@$array_ref[$i] eq '-'))) {$i--;}
  if ($i == 0) {
    return 0;
  }
  @$array_ref[$i-1,$i] = @$array_ref[$i,$i-1];
  my $u = $i+1;
  my $v = (@$array_ref)-1;
  while ($u<$v) {
    if (@$array_ref[$v] eq '-') {
      $v--;
    } elsif (@$array_ref[$u] eq '#') {
      $u++;
    } else {
      @$array_ref[$v,$u] = @$array_ref[$u,$v];
    }
  }
  return 1;
}

# check if the seed (represented as an array of chars) has an initial and final '#' 
sub acceptedseed($) {
  my $array_ref = shift;
  my $i = (@$array_ref) - 1;
  if (@$array_ref[0] eq '#' && @$array_ref[$i] eq '#') {
    return 1;
  } else {
    return 0;
  }
}


# main parameters : w is the weight, s is the maximal span
for (my $w = 3; $w <= 7 ; $w++) {
    my $s = $w + 4;

  # single seed enumeration (symetric pattern of previous seeds are discarded)
  for (my $j1 = 0 ; $j1 <= $s-$w; $j1++) {
      my $seed1 = ('#' x ($w)) . ('-' x ($j1));
      my @seed1_table = split(//, $seed1);
      do {
          if (acceptedseed(\@seed1_table) && (join('', @seed1_table) le join('', reverse(@seed1_table)))) {
              print "".join('', @seed1_table)."\n";
          }
      } while (nextseed(\@seed1_table));
  }
  # double seed enumeration  (symetric pattern of previous set of seeds are discarded)
  for (my $j1 = 0 ; $j1 <= $s-$w; $j1++) {
      my $seed1 = ('#' x ($w)) . ('-' x ($j1));
      my @seed1_table = split(//, $seed1);
      do {
          if (acceptedseed(\@seed1_table) && (join('', @seed1_table) le join('', reverse(@seed1_table)))) {
              for (my $j2 = 0 ; $j2 <= $s-$w; $j2++) {
                  my $seed2 = ('#' x ($w)) . ('-' x ($j2));
                  my @seed2_table = split(//, $seed2);
                  do {
                      if (acceptedseed(\@seed2_table) && 
                          (
                           # first is not symetric : second must be strictly greater
                           (join('', @seed1_table) lt join('', reverse(@seed1_table))) && (join('', @seed1_table) lt join('', @seed2_table)) 
                           ||
                           # first is symetric : second must be strictly greater and cannot be strictly greater than its reverse
                           (join('', @seed1_table) eq join('', reverse(@seed1_table))) && (join('', @seed1_table) lt join('', @seed2_table)) && (join('', @seed2_table) le join('', reverse(@seed2_table)))
                          ) &&
                          (join('', @seed1_table).",".join('', @seed2_table) lt reverse(join('', @seed1_table).",".join('', @seed2_table)))
                          )
                      {
                          print "".join('', @seed1_table).",".join('', @seed2_table)."\n";
                      }
                  }
                  while (nextseed(\@seed2_table));
              }
          }
      }
      while (nextseed(\@seed1_table));
  }
}
