Unsorted Two Sum

Imperative Solution in Python

“Veni, vidi, vici”—Julius Caesar, Imperator of Rome, 44 B.C.

Imperative Python function below accumulates a set of numbers; a result pair exists if a new number’s difference from the total matches any previously accumulated number. This technique improves performance over a naive iteration as the number of numbers increases.

def unsorted_two_sum_to(numbers, total):
  results = []
  acc = set()
  for number in numbers:
    difference = total - number
    if difference in acc:
      results.append((number, difference))
    acc.add(number)
  return(results)

Test with 1, 2, 3 as follows. The answer should match the pair \((1, 2)\) since these two numbers match the only two-tuple (pair) of integers that sum to \(3\), the required sum.

unsorted_two_sum_to([1, 2, 3], 3)

The answer is a list with one pair \((2, 1)\) as follows. Python evaluates to a list of tuples:

[(2, 1)]

Another test confirms it; all combinations sum to \(16\).

unsorted_two_sum_to([6, 7, 8, 9, 1, 16, 2, 3, 14, 13, 4, 5, 12, 32, 44], 16)

This time a number of alternative solutions result; list below.

[(9, 7), (14, 2), (13, 3), (12, 4)]

Functional Solution in Prolog

This is a functional approach where the mind looks for relationships between elements of the problem.

unsorted_two_sum_to(Numbers, Total, Terms) :-
    unsorted_two_sum_to(Numbers, Total, [], [], Terms).

unsorted_two_sum_to([], _Total, _Acc, Terms, Terms) :- !.
unsorted_two_sum_to([Number|Numbers], Total, Acc,
                    Terms0, [Number+Difference|Terms]) :-
    Difference is Total - Number,
    ord_memberchk(Difference, Acc),
    !,
    unsorted_two_sum_to_([Number|Numbers], Total, Acc, Terms0, Terms).
unsorted_two_sum_to(Numbers, Total, Acc, Terms0, Terms) :-
    unsorted_two_sum_to_(Numbers, Total, Acc, Terms0, Terms).

unsorted_two_sum_to_([Number|Numbers], Total, Acc0, Terms0, Terms) :-
    list_to_ord_set([Number|Acc0], Acc),
    unsorted_two_sum_to(Numbers, Total, Acc, Terms0, Terms).

Considerably more code required, as measured by lines. You can easily argue that this approach adds an order of magnitude to the overall complexity. Nevertheless, results amount to the same albeit in Prolog pairwise terms A+B rather than Python tuples.

?- unsorted_two_sum_to([6, 7, 8, 9, 1, 16, 2, 3, 14, 13, 4, 5, 12, 32, 44], 16, A).
A = [9+7, 14+2, 13+3, 12+4].

The functional Prolog solution requires three distinct predicates.

1. Arity-3 unsorted_two_sum_to/3 predicate acts as the public interface and supplies the initial accumulator set and starting empty-term results list.
2. Arity-5 unsorted_two_sum_to/5 predicate performs the list recursive behaviour for Number head terms. This defines the relationship between the incoming numbers and the outgoing terms when a number difference successfully hits the accumulator set.
3. Arity-5 unsorted_two_sum_to_/5 predicate merges the head Number with the accumulator set at each step along the way.

Conclusions

Note that a difference between functional and imperative mindset pervades the solution and the phrasing of the problem as well. Problems phrased as “for each” something imply a loop yet looping does not exist per se in a functional paradigm. The programmer cannot do “for” anything. Posed with a problem in those terms, a translation becomes necessary.

Logic theory offers a mind bridge. Operators every \(\forall\) and exists \(\exists\) express the existential imperatives that for loops attempt to represent in their clumsy von Neumann way: fetch-execute-store cycles running over bits and bytes in RAM. The mind sees relationships between logical entities rather than artificial machine states that reify those relationships within a CPU.

Your personal mileage may vary (YMMV).