Re: Inefficient algorithms

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> Niklas Holsti wrote:
>> Rick wrote:
>>> I am working on a class in algorithmic efficiency and, to make a
>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>> please help with an Ada example.
>>
>> Perhaps the canonical example is this: you are given a Boolean
>> formula containing n Boolean variables. Find a valuation (a value,
>> True or False, for each variable) that makes the formula True.
>
> Replying to myself, since I realize that I probably misunderstood your
> need: what you want is an inefficient O(2^n) solution to an easy
> (non-exponential) problem. The problem I suggested is not, of course,
> an easy one. But it has easy variants. For example, require that the
> Boolean formula uses at most 10 of the n variables, where this limit
> (10) is considered a fixed number independent of the total number (n)
> of variables.

Actually I do think that the problem is trivial and that you can solve
it without recursion.  If you see your array of Booleans as a number in
binary representation:

procedure Inefficient (N : in Natural) is

   subtype Valuation is Natural range 1 .. 2**N;

   -- We assume the solution is Valuation'Last but it could be any value.
   Solution : constant Valuation := Valuation'Last;
begin
   for K in Valuation'Range loop
      exit when K = Solution;
   end loop;
end Inefficient;

-- 
Ludovic Brenta.