Esse problema é bastante fácil de fazer com força bruta. De fato, será razoavelmente rápido também a força bruta. Mas onde está a graça nisso?

O problema

Produza uma lista de todos os pares de números exclusivos de 5 dígitos que somam 121212. No entanto, cada dígito decimal deve aparecer exatamente uma vez em qualquer número. Então, um par válido seria (98167, 23045). Mas um par inválido seria (23456, 97756)porque 7, 5, 6é repetido mais de uma vez e 1, 8, 0não é usado. Existem exatamente 192 pares únicos.

Regras

1. Eficiência: Você pode fazer isso com força bruta. Mas isso é trivial de se fazer. Portanto, o verdadeiro desafio aqui é encontrar uma maneira de produzir com eficiência a lista de números.

2. Requisitos do código-fonte: Ele não pode armazenar a lista de números (ou qualquer parte dela). A sequência numérica deve ser gerada em tempo real.

Diverta-se!

Javascript

function findpairs(arrin1,arrin2){
    functioncount++
    var arr1=[]
    var arr2=[]
    var strike=[]
    var overflow=0
    var b
    var len=arrin1.length
    for(var a=0;a<len;a++){
        arr1[a]=arrin1[a]
        arr2[a]=arrin2[a]
        strike[arr1[a]]=true
        strike[arr2[a]]=true
        overflow=+((arr1[a]+arr2[a])>9)
    }
    var desired=12-(len%2)-overflow
    for(a=9;a>0;a--){
        b=(desired-a)%10
        if(a>b && !strike[a] && !strike[b]){
            if(len==4){
                if((a+b)>9){
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    resultcount+=16
                }
            }
            else{
                arr1[len]=a
                arr2[len]=b
                findpairs(arr1,arr2)
            }
        }
    }
}
resultcount=0
functioncount=0
start=+new Date()
findpairs([],[])
end=+new Date()
document.write("<br>"+resultcount+" results<br>"+(end-start)+" ms<br>"+functioncount+" function calls")

Hospedado em: http://ebusiness.hopto.org/findpairs.htm

Realização matemática: se você tem um par, outros 15 podem ser gerados trivialmente trocando dígitos entre os dois números, portanto, só procuro números em que os dígitos do primeiro são todos maiores que os dígitos do segundo e, em seguida, simplesmente produzo todas as permutações.

Começo com os dígitos menos significativos e gero a sequência como uma travessia em árvore, para cada etapa que afirma que o resultado intermediário está correto e que nenhum dígito é gasto duas vezes. Com esses métodos, a função precisa ser chamada apenas 50 vezes no total. Na minha máquina, o Chrome gera resultados de tempo de execução de tipicamente 2 ms.

C ++

#include<iostream>
using namespace std;
#include<algorithm>

int main()
{
    long long N,F,S;
    char str[11]="1023456789";
    while (1) {
        sscanf(str,"%lld",&N);
        F=N/100000;S=N%100000;
        if (F>60000)
           break;
        if (F+S==121212)
           printf("%lld %lld\n",F,S);
        next_permutation(str,str+10);
    }
}

http://www.ideone.com/Lr84g

Python 2.

É bastante eficiente porque constrói os números (o loop mais interno é executado 4570 vezes no total) e muito curto porque joguei um pouco (201 caracteres), mas não tenho muita certeza se quero explicar isso :)

p=lambda t,a,d:((x,y)for x in range(10)for y in[(t-x-a)%10]if(x not in d)&(y not in d)and x-y)
w=lambda s:[s]if len(s)==10and s[:5]<s[5:]else(m for n in p(2-len(s)/2%2,sum(s[-2:])/10,s)for m in w(s+n))

Os valores retornados são bastante peculiares: ligue wcom uma tupla vazia e você obterá um iterador de 10 tuplas. Estas 10 tuplas são os dígitos dos dois números, infelizmente para trás e alternando , ou seja, a tupla

(2, 0, 8, 3, 7, 4, 9, 1, 6, 5)

representa os números 51430 e 69782.

Teste:

result = list(w(()))

assert len(set(result)) == 192               # found all values
assert len(result) == 192                    # and no dupes 

for digits in result:
    assert all(0 <= d <= 9 for d in digits)  # real digits -- zero through nine
    assert len(set(digits)) == 10            # all digits distinct

    n1 = int("".join(map(str, digits[9::-2])))
    n2 = int("".join(map(str, digits[8::-2])))

    assert n1 + n2 == 121212                 # sum is correct

Aqui está a versão não destruída:

ppcalls = 0       # number of calls to possiblePairs
ppyields = 0      # number of pairs yielded by possiblePairs
ppconstructed = 0 # number of construced pairs; this is the number
                  #     of times we enter the innermost loop

def possiblePairs(theirSumMod10, addition, disallowed):
    global ppcalls, ppyields, ppconstructed
    ppcalls += 1
    for a in range(10):
        b = (theirSumMod10 - a - addition) % 10
        ppconstructed += 1
        if a not in disallowed and b not in disallowed and a != b:
            ppyields += 1
            yield (a, b)

def go(sofar):
    if len(sofar) == 10:
        if sofar[:5] < sofar[5:]: # dedupe
            yield sofar

    digitsum = 2 - (len(sofar) / 2) % 2 # 1 or 2, alternating

    for newpair in possiblePairs(digitsum, sum(sofar[-2:]) / 10, sofar):
        for more in go(sofar + newpair):
            yield more


list(go(()))        # iterate

print ppcalls       # 457
print ppyields      # 840
print ppconstructed # 4570

C

#include <stdio.h>

int mask(int n)
{
    int ret = 0;

    for (; n > 0; n /= 10)
        ret |= 1 << n % 10;

    return ret;
}

int main(void)
{
    int a, b;

    for (a = 21213, b = 99999; a < b; a++, b--)
        if ((mask(a) | mask(b)) == 0x3FF)
            printf("%d %d\n", a, b);

    return 0;
}

Isso percorre todos os pares de números de 5 dígitos que somam 121212 (significando 39393 iterações, ou ~ 1/46 das iterações usadas pela resposta de fR0DDY ). Para cada par, ele forma uma máscara de bits dos dígitos em cada número e depois vê se OR para 0b1111111111.

Javascript (481)

function m(d,i){o=d-i;if(0<=o&&o<=9&&o!=i)return o;o+=10;if(0<=o&&o<=9&&o!=i)return o;return}function p(n,a){x=0;r=[];d=n%10;for(i=0;i<10;i++){if((!a||!a.contains(i))&&(o=m(d,i))&&(!a||!a.contains(o))&&i+o<=n)r[x++]=[i,o]}return r}function f(n,a){var x=0;var r=[];var d=p(n,a);for(var i=0;i<d.length;i++){var s=Math.floor((n-d[i][0]-d[i][1])/10);if(s>0){var t=f(s,d[i].concat(a));for(var j=0;j<t.length;j++)r[x++]=[t[j][0]*10+d[i][0],t[j][1]*10+d[i][1]]}else{r[x++]=d[i]}}return r}

http://jsfiddle.net/XAYr3/4/

Ideia básica: gere combinações de dígitos válidos que possam ser usados ​​na coluna mais à direita. Por exemplo, (0,2), (3,9), (4,8), (5,7). Para cada combinação, encontre recursivamente pares que funcionam para o dígito da direita, sem duplicar os dígitos no primeiro par. Faça o recursão até que um par de números de 5 dígitos tenha sido gerado. Combine todos esses resultados em uma única matriz, e a lista é de 192 elementos. Acredito que isso deva exigir o menor número possível de iterações, mas toda a alocação / desalocação de array o torna praticamente ineficiente.

Meus testes de contagem mostram que a função fé chamada 310 vezes, o loop interno ié executado 501 vezes no total (em todas as chamadas para f) e o loop interno e interno jé executado 768 vezes no total (em tudo).

Python, 171 caracteres

def R(x,y,d,c):
 if not d and x<y:print x,y
 for p in d:
  q=(12-c%2-p-(x+y)/10**c)%10
  if p-q and q in d:R(x+p*10**c,y+q*10**c,d-set([p,q]),c+1)
R(0,0,set(range(10)),0)

O código mantém a invariante que x , ytem cdígitos e que todos os dígitos não utilizados estão no conjunto d.

A rotina R é chamada um total de 841 vezes, o que é bastante eficiente.

C ++

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>

int main()
{
        int i;
        char str1[11]="0123456789",str2[11];
        for (i=99999;i>60000;i--)
        {
                sprintf(str2,"%d%d",i,121212-i);
                sort(str2,str2+10);
                if(!strcmp(str1,str2))
                        printf("%d %d\n",i,121212-i);
        }
}

http://www.ideone.com/Lr84g