Suppose you are given a list of possible Bitcoin that you control (inputs). You need to pay someone exactly 0.71 BTC. How would you select exactly 2 inputs in such a way as to minimize the change output if you could ignore fees? Write a python function that selects the two inputs.

min_change_input_pair.py

# simple class to contain the id and value of a transaction
class Transaction:
  def __init__(self, id, value):
    self.id = id
    self.value = value

  def __add__(self, other):
    return self.value + other.value

  # readable output
  def __str__(self):
    return "{%s: %f}" % (self.id, self.value)

  # readable output
  __repr__ = __str__

inputs = [
  Transaction('abc', 0.01),
  Transaction('def', 5.0),
  Transaction('ghi', 1.00023),
  Transaction('jkl', 0.798),
  Transaction('mno', 6.19203),
  Transaction('pqr', 0.0004)
]

print '--- min change for transaction pairs ---'

# given a set of inputs and an amount, find the pair of transactions which
# yield the least amount of change, or find the pair of transactions with
# the mimumum sum greater than the amount provided
# inputs: [Transaction] a list of transactions
# amt: (float) the value we are trying to send
# returns (2): the transactions and the change (delta)
def two_transactions_min_change(inputs, amt):
  # requires two inputs
  if len(inputs) < 2:
    return

  change = None
  tx1 = None
  tx2 = None

  ilen = len(inputs)

  # double loop to create all combinations of two transactions
  for i in range(0, ilen - 2):
    # loop range starting at 1+1 to avoid combinations of the same transaction
    # as well as combinations in reverse order of those we've already seen
    for j in range(i + 1, ilen - 1):
      chg = inputs[i] + inputs[j] - amt
      # discard pairs whose sum is less than `amt`
      if chg < 0:
        continue

      # if new delta is less than previous (or previously unset),
      # save the inputs
      if change is None or change > chg:
        tx1 = inputs[i]
        tx2 = inputs[j]
        change = chg

  return [tx1, tx2], change

# test cases
import numpy
for a in numpy.arange(0.5, 13.0, 0.5):
  transactions, change = two_transactions_min_change(inputs, a)
  print a, change, transactions

min_change_set.py

# Original Problem:
# Suppose you are given a list of possible Bitcoin that you control (inputs).
# You need to pay someone exactly 0.71 BTC. How would you select exactly 2
# inputs** in such a way as to minimize the change output if you could ignore
# fees? Write a python function that selects the two inputs.

# ** - I couldn't resist the temptation to remove the "exactly 2 inputs"
# restriction

# simple class to contain the id and value of a transaction
class Transaction:
  def __init__(self, id, value):
    self.id = id
    self.value = value

  def __add__(self, other):
    return self.value + other.value

  # readable output
  def __str__(self):
    return "{%s: %f}" % (self.id, self.value)

  # readable output
  __repr__ = __str__

inputs = [
  Transaction('abc', 0.01),
  Transaction('def', 5.0),
  Transaction('ghi', 1.00023),
  Transaction('jkl', 0.798),
  Transaction('mno', 6.19203),
  Transaction('pqr', 0.0004)
]

print '--- min change sans transaction count ---'

# create all combinations of inputs whose sum is greater than the provided
# amount
# results is "passed by reference" and will contain a dictionary whose keys
# are the change and whose values are a set of transactions
def greater_combinations(inputs, amt, transactions, results):
  # iterate over each item in inputs
  for i in range(0, len(inputs) - 1):
    txs = transactions + [inputs[i]]
    total = sum(map(lambda t: t.value, txs))

    if total > amt:
      results[total - amt] = txs
      # no need to recurse further, it will only yield a set with more change
      continue

    # recurse with the "rest" of the array (to avoid duplicates)
    greater_combinations(inputs[i+1:], amt, txs, results)

# given a set of inputs, find the set which results in the least amount of
# "change", or, find the set of inputs with the mimimum sum greater than the
# amount
def min_change(inputs, amt):
  combinations = {}

  greater_combinations(inputs, amt, [], combinations)

  if not len(combinations):
    return [[], None]

  min_diff = min(combinations.keys())

  return combinations[min_diff], min_diff

# test cases
import numpy
for a in numpy.arange(0.5, 14.0, 0.5):
  transactions, change = min_change(inputs, a)
  print a, change, transactions