# -*- mode: cperl6; -*-

# 2011 Perl 6 Coding Contest
# Edgar Gonzàlez i Pellicer

# Integer partitions
module Partition;

use LinkedLists;


# Stored partitions
my @partitions;
@partitions[0] = [ LinkedList ];
@partitions[1] = [ LinkedList.new(head => 1, tail => LinkedList) ];
@partitions[2] = [ LinkedList.new(head => 2, tail => LinkedList),
		   LinkedList.new(head => 1, tail => @partitions[1][0]) ];


# Find the start of the partitions whose largest value is below
# or equal to the given value
# Partitions are sorted by decreasing lexicographical order
# It is a lower bound
sub partitions-below-or-eq(Array $partitions, Int $largest) is export {
  # Binary search
  my $l = 0;
  my $r = $partitions.elems;

  # Loop
  while $l < $r {
    # Middle
    my $m = ($l + $r) div 2;
    if $partitions[$m].head > $largest {
      $l = $m + 1;
    }
    else {
      $r = $m;
    }
  }

  # Return the point
  return $l;
}


# Integer partitions
sub int-partitions(Int $n) is export {
  # Generate them
  for @partitions.elems .. $n -> $i {
    # Partitions i
    my $partitions-i = [ LinkedList.new(head => $i, tail => LinkedList) ];

    # Choose the largest element
    for $i - 1, $i - 2 ... 1 -> $largest {
      # Tails
      my $tails = @partitions[$i - $largest];
      my $start = partitions-below-or-eq($tails, $largest);

      # For each one
      for $tails[$start ..^ $tails.elems] -> $tail {
	$partitions-i.push(LinkedList.new(head => $largest, tail => $tail));
      }
    }

    # Set it
    @partitions[$i] = $partitions-i;
  }

  # Return them
  return @partitions[$n].list;
}