view release on metacpan or  search on metacpan

lib/Algorithm/QuineMcCluskey.pm  view on Meta::CPAN

	#
	##### recurse_solve() level: $level
	##### recurse_solve() called with
	##### primes: "\n" . chart(\%primes, $self->width)
	#
	my @essentials_next = find_essentials(\%primes);

	#
	##### Begin prefix/essentials loop.
	#
	do
	{
		#
		##### recurse_solve() do loop, essentials: @essentials
		#
		# Remove the essential prime implicants from
		# the prime implicants table.
		#
		@essentials = @essentials_next;

		#
		##### Purging prime hash of: "[" . join(", ", sort @essentials) . "]"
		#
		purge_elements(\%primes, @essentials);
		push @prefix, @essentials;

		##### recurse_solve() @prefix now: "[" . join(", ", sort @prefix) . "]"

		#
		# Now eliminate dominated rows and columns.
		#
		# Rule 1: A row dominated by another row can be eliminated.
		# Rule 2: A column that dominated another column can be eliminated.
		#
		#### Looking for rows dominated by other rows
		####    primes table: "\n" . chart(\%primes, $self->width)
		my @rows = row_dominance(\%primes, 1);
		delete $primes{$_} for (@rows);
		#### row_dominance returns rows for removal: "[" . join(", ", @rows) . "]"
		####      primes now: "\n" . chart(\%primes, $self->width)

		my %cols = transpose(\%primes);
		my @cols = row_dominance(\%cols, 0);
		remels(\%primes, @cols);
		#### row_dominance returns cols for removal: "[" . join(", ", @cols) . "]"
		####      primes now: "\n" . chart(\%primes, $self->width)

		@essentials_next = find_essentials(\%primes);

		##### recurse_solve() essentials after purge/dom: @essentials

	} until (is_LequivalentR([
			[ @essentials] => [ @essentials_next ]
			]));

	return [ reverse sort @prefix ] unless (keys %primes);

	#
	# Find a term (there may be more than one) that has the least
	# number of prime implicants covering it, and a list of those
	# prime implicants. Use that list to figure out the best set
	# to cover the rest of the terms.
	#
	##### recurse_solve() Primes after loop
	##### primes: "\n" . chart(\%primes, $self->width)
	#
	my($term, @ta) = covered_least(\%primes);

	#
	##### Least Covered term: $term
	##### Covered by: @ta
	#
	# Make a copy of the section of the prime implicants
	# table that don't cover that term.
	#
	my %r = map {
		$_ => [ grep { $_ ne $term } @{ $primes{$_} } ]
	} keys %primes;

	#
	# For each such cover, recursively solve the table with that column
	# removed and add the result(s) to the covers table after adding
	# back the removed term.
	#
	for my $ta (@ta)
	{
		my (@c, @results);
		my %reduced = %r;

		#
		# Use this prime implicant -- delete its row and columns
		#
		##### Purging reduced hash of: $ta
		#
		purge_elements(\%reduced, $ta);

		if (keys %reduced and scalar(@c = $self->recurse_solve(\%reduced, $level + 1)))
		{
			#
			##### recurse_solve() at level: $level
			##### returned (in loop): arrayarray(\@c)
			#
			@results = map { [ reverse sort (@prefix, $ta, @$_) ] } @c;
		}
		else
		{
			@results = [ reverse sort (@prefix, $ta) ]
		}

		push @covers, @results;

		#
		##### Covers now at: arrayarray(\@covers)
		#
	}

	#
	##### Weed out the duplicated and expensive solutions.
	#
	@covers = uniqels @covers;