Mostra as possibilidades de saque em caixa eletrônico dado as notas disponíveis e perguntado um valor.

caixa_eletronico.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

class SemCaixa(Exception):
    pass

# Lista com valor da nota e quantidade disponível no caixa
caixa = {50: 10, 20: 10, 10: 10, 5: 10}

# Perguntar o valor, saindo se não digitar nada
while True:
    valor = raw_input("Valor: ")
    if not valor:
        sys.exit(0)
    try:
        valor = int(valor)
    except ValueError:
        print "Inválido! Tente novamente ou pressione [Enter] para sair"
        continue
    break

# Analisar recursivamente as notas na lista que chegam no valor
def quais_notas(caixa, valor):
    if not valor:
        return []
    if not caixa:
        raise SemCaixa
    notas_restantes = caixa[:]
    nota, qtd = notas_restantes.pop(0)
    utilizadas = min(int(valor / nota), qtd)
    if not utilizadas:
        return quais_notas(notas_restantes, valor)
    resto = valor - nota * utilizadas
    return [(nota, utilizadas)] + quais_notas(notas_restantes, resto)

# Retorna lista de possíveis arranjos
def arranjos(sequencia):
    if len(sequencia) < 2:
        return sequencia
    if len(sequencia) == 2:
        return [sequencia, sequencia[::-1]]
    resultado = []
    for i in range(len(sequencia)):
        temp = list(sequencia[:])
        x = temp.pop(i)
        for a in arranjos(temp):
            resultado.append([x] + a)
    return resultado

possibilidades = set() # set para evitar duplicidade
caixas = arranjos(sorted([x for x in caixa.items() if x[0] <= valor],
                                                        reverse = True))
for caixa in caixas:
    # duplica o caixa de tuplas para listas para permitir alterações
    caixa = [list(x) for x in caixa]
    while True:
        try:
            possibilidade = quais_notas(caixa, valor)
        except SemCaixa:
            break
        # adiciona a possibilidade ordenada e como tupla para o set
        possibilidades.add(tuple(sorted(possibilidade, reverse = True)))
        nota1, qtd1 = possibilidade[0]
        for n, (nota, qtd) in enumerate(caixa):
            if nota == nota1:
                break
        if qtd1 == 1:
            del caixa[n]
        else:
            caixa[n][1] = qtd1 - 1

# Exibir possibilidades
if not possibilidades:
    print "Não há caixa para este valor!"
else:
    for p, notas in enumerate(sorted(possibilidades, reverse = True)):
        notas = ["%2i x %3i" % n[::-1] for n in notas]
        print 'Possibilidade %4i: %s' % (p + 1, ' + '.join(notas))