It is known that the code consists of 4 digits. It is also known that all the numbers are different.

Tell me, please, the optimal algorithm for enumerating values ​​from 0000 to 9999. I will sincerely be grateful for the pseudo-code.

  • 3
    Ultimately, to guarantee finding the answer, you still need 10,000 iterations. What kind of optimality can we talk about? - D-side
  • 3
    @ D-side I'll be a bore. Not 10,000, but less, because the condition states "all figures are different" - Kromster
  • 2
    @KromStern well laaaaadno, 5040 ( [*0..9].permutation(4).count ). Not even half as much: P - D-side
  • four
    @D-side we can only accept these numbers manually (mechanical lock), then 10*9*8*7 == 5040 noticeably less than 10000 even if the robot enters the code for you. Also (but another question) it is interesting to consider an algorithm that would equally wear the wheels with numbers (if you want to keep the lock intact ) - jfs
  • If you are given an exhaustive answer, mark it as correct (a daw opposite the selected answer). - Nicolas Chabanovsky ♦

2 answers 2

In the forehead - four nested cycles for each of the numbers (as if we were turning the wheels of the lock on the suitcase). For numbers to the right of the first, we check that it does not coincide with the numbers to the left. If it is necessary to pick up the code in the described conditions, there is no point in sweating with optimization.

 var a, b, c, d, result=[]; for( a=0; a<10; a++) { for( b=0; b<10; b++) { if( b === a) continue; for( c=0; c<10; c++) { if( c===a || c===b) continue; for( d=0; d<10; d++) { if( d===a || d===b || d===c) continue; // abcd из разных цифр result.push( ''+a+b+c+d); } } } }

Upd. Probably can be optimized. When scrolling through the numbers from left to right, there are 10 options in the first position, 9 in the second, 8 in the third, and only 7 in the right. Instead of 10,000 iterations, just 5040. But I haven't come up with anything better than an array and sorting. Fig optimization:

 var a,b,c,d,A,B,C,D,U,result=[]; for( a=0; a<10; a++) { for( b=0; b<9; b++) { for( c=0; c<8; c++) { for( d=0; d<7; d++) { A = a; B = b; if( B>=A) B++; U = [A,B].sort(); C = c; if( C>=U[0]) C++; if(C>=U[1]) C++; U = [A,B,C].sort(); D = d; if( D>=U[0]) D++; if(D>=U[1]) D++; if( D>=U[2]) D++; result.push( ''+A+B+C+D); } } } }

    What you need is the generation of all placements without repetitions , or (in the English version) k-permutations .

    Roughly speaking, look for all combinations of 4 digits out of 10, and for each combination go through all permutations. This is if global.

    Pseudocode - here (forgive me, I can't show indexes normally, I had to use pro-TeX ...):

     def a = { 0, 1, 2 … (n - 1) } def edge = k - 1 // find j in (k…n-1) where a_j > a_edge j = k while j < n and a_edge >= a_j, ++j if j < n { swap a_edge, a_j } else { reverse a_k to a_{n-1} // find rightmost ascent to left of edge i = edge - 1 while i >= 0 and a_i >= a_i + 1, --i if i < 0, // no more permutations return 0 // find j in (n-1…i+1) where a_j > a_i j = n - 1 while j > i and a_i >= a_j --j swap a_i, a_j reverse a_{i+1} to a_{n-1} } output a_0, a_1 … a_{k-1}

    Taken from here .