Masalah ini cukup mudah dilakukan dengan brute force. Bahkan, itu akan cukup cepat untuk memaksa juga. Tapi di mana kesenangannya?

Masalah

Menghasilkan daftar semua pasangan nomor 5 digit unik yang dijumlahkan 121212. Namun, setiap angka desimal harus muncul tepat satu kali dalam salah satu angka. Jadi pasangan yang valid adalah (98167, 23045). Tetapi pasangan yang tidak valid akan (23456, 97756)karena 7, 5, 6diulang lebih dari satu kali, dan 1, 8, 0tidak digunakan sama sekali. Tepatnya ada 192 pasangan unik.

Aturan

1. Efisiensi: Anda dapat dengan paksa memaksakan ini. Tapi itu sepele untuk dilakukan. Jadi alih-alih, tantangan sebenarnya di sini adalah menemukan cara untuk secara efisien menghasilkan daftar angka.

2. Persyaratan Kode Sumber: Tidak dapat menyimpan daftar nomor (atau bagian mana pun dari itu). Urutan nomor harus dibuat dengan cepat.

Selamat bersenang-senang!

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")

Diinangi di: http://ebusiness.hopto.org/findpairs.htm

Realisasi matematis: Jika Anda memiliki satu pasangan, 15 pasangan lainnya dapat dengan sepele dihasilkan dengan menukar angka di antara kedua angka tersebut, oleh karena itu saya hanya mencari angka-angka di mana angka yang pertama lebih besar dari angka yang kedua, dan kemudian cukup mengeluarkan semua permutasi.

Saya mulai dari angka paling tidak signifikan dan menghasilkan urutan sebagai traversal pohon, untuk setiap langkah menyatakan bahwa hasil antara benar dan tidak ada digit yang dihabiskan dua kali. Dengan metode ini fungsi hanya perlu dipanggil 50 kali secara total. Di mesin saya, Chrome menghasilkan hasil runtime yang biasanya 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.

Ini cukup efisien karena ia membangun angka-angka (loop paling dalam dieksekusi total 4570 kali) dan cukup pendek karena saya bermain golf sedikit (201 karakter), tapi saya tidak begitu yakin saya ingin menjelaskan ini :)

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))

Nilai yang dikembalikan cukup aneh, meskipun: panggilan wdengan tuple kosong, dan Anda mendapatkan iterator 10-tupel. 10 tupel ini adalah digit dari dua angka, sayangnya mundur dan bergantian , yaitu tupel

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

mewakili angka 51430 dan 69782.

Uji:

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

Ini adalah versi yang tidak dikoleksi:

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;
}

Ini melintasi semua pasangan nomor 5-digit yang berjumlah 121212 (artinya 39393 iterasi, atau ~ 1/46 dari iterasi yang digunakan oleh jawaban fR0DDY ). Untuk setiap pasangan, ini membentuk topeng bit dari angka di setiap angka, kemudian melihat apakah mereka ATAU hingga 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/

Ide dasar: menghasilkan kombinasi angka yang valid yang dapat digunakan di kolom paling kanan. Misalnya, (0,2), (3,9), (4,8), (5,7). Untuk setiap kombinasi, temukan pasangan yang bekerja untuk digit berikutnya-dari-kanan, secara berulang, tanpa menggandakan digit pada pasangan pertama. Perulangan hingga sepasang angka 5-digit telah dihasilkan. Gabungkan semua hasil itu menjadi satu larik, dan daftarnya adalah 192 elemen. Ini saya percaya harus memerlukan tentang iterasi paling sedikit, tetapi semua alokasi / deallokasi array membuatnya secara keseluruhan agak tidak efisien secara praktis.

Tes penghitungan saya menunjukkan bahwa fungsi fdisebut 310 kali, loop dalam idieksekusi total 501 kali (di semua panggilan ke f), dan loop dalam-dalam jdieksekusi total 768 kali (di semua segalanya).

Python, 171 karakter

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)

Kode mempertahankan invarian yang x, ymemiliki cangka dan bahwa semua yang tidak terpakai angka yang di set d.

Rutin Rdisebut total 841 kali, yang cukup efisien.

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