*main::min_chunks = \&Lingua::Anagram::SmallestChange::min_chunks;
min_chunks('aaabbcc', 'ccbbaaa');
package Lingua::Anagram::SmallestChange;

use strict;
use warnings;
use Algorithm::Permute;

require Exporter;
use vars qw(@ISA @EXPORT_OK);
@ISA = qw(Exporter);

@EXPORT_OK = qw(min_chunks split_word);

sub  split_word {
  my ($word) = @_;
  my @letters = split //, $word;
  my %graph;
  for my $index (0 .. $#letters) {
    if (exists $graph{$letters[$index]}) {
      push @{$graph{$letters[$index]}}, $index;
    } else {
      $graph{$letters[$index]} = [$index];
    }
  }
  %graph;
};

sub count_chunks {
  my ($word, $graph) = @_;
  my @gr = map {shift @{$graph->{$_}}} split //, $word;
  my ($chunks, $prev) = (0, -2);
  for my $pos (@gr) {
    $chunks++ if $prev + 1 != $pos;
    $prev = $pos;
  }
  $chunks;
}

sub min_chunks {
  my ($given, $target) = @_;
  my (%permutations, @state);
  my %origin = split_word($given);

  # populate the state array, this is an array of anon arrays each anon array

  # has a letter from the word and an anon array of one combination of the
  # positions of that letter.
  for my $lett (keys %origin) {
    if (@{$origin{$lett}} != 1) {
      $permutations{$lett} = Algorithm::Permute->new($origin{$lett});
      push @state, [$lett, [$permutations{$lett}->next]];
      delete $origin{$lett};
    }
  }

  # call this reset because the first thing the processing loop does is call
  # next and if we don't do this we'd lose the first permutation.
  $permutations{$state[0][0]}->reset if defined $state[0];
  my $chunks = length $target; 

  FIND: while (1) {
    # origin now only contains one element arrays in it's values copy origin
    # into disposable so we can operate destructively on the one element arrays

    my %working;
    for (keys %origin) {
      $working{$_} = [$origin{$_}[0]];
    }

    # generate the next permutation
    my $i = 0;
    {
      next if $i > $#state; # we've iterated through all states of all the objects

      my @new = $permutations{$state[$i][0]}->next;
      if (@new) {
        $state[$i][1] = [@new];
      } else {
        $permutations{$state[$i][0]}->reset;
        $state[$i][1] = [$permutations{$state[$i][0]}->next];
	$i++;
	redo;
      }
    }

    for my $s (@state) {
      $working{$s->[0]} = [@{$s->[1]}];
    }
    my $new_count = count_chunks($target, \%working);
    $chunks = $new_count if $chunks > $new_count;
    last FIND if $i > $#state; # we've iterated through all states of all the objects

  }
  $chunks;
};

1;
