4
$\begingroup$

It's possible to generate all possible combinations of 3 digits by counting up from 000 to 999, but this produces some combinations of digits that contain duplicates of the same digit (for example, 099). I could obtain all combinations of 3 digits without repetition by counting up from 000 to 999, and then removing all numbers with duplicate digits, but this seems inefficient. Is there a more efficient way to accomplish the same task?

$\endgroup$
  • $\begingroup$ What do you mean by 'generate'? Do you want an algorithm for them? Or are you asking for the number of 3 digits without repetition? $\endgroup$ – Calvin Lin May 22 '13 at 20:09
  • $\begingroup$ @CalvinLin I'm trying to find an efficient algorithm that can generate all of them. $\endgroup$ – Anderson Green May 22 '13 at 20:10
  • $\begingroup$ How about generating the ${10 \choose 3}$ subsets of distinct digits and them permuting the digits? Or do you want them in numerical order? $\endgroup$ – Calvin Lin May 22 '13 at 20:12
  • $\begingroup$ @CalvinLin That approach would probably work, since the combinations of digits don't need to be in numerical order. $\endgroup$ – Anderson Green May 22 '13 at 20:19
  • $\begingroup$ When you talk about inefficiency, for the stated problem you're talking about optimising a program that would run in less than a microsecond (it would take you longer to hit the enter key). Unless you're seeking some unstated scalability, it's generally considered bad practice to optimise unnecessarily like this. If you are seeking some kind of scalability, the best approach will depend on the application you have in mind. $\endgroup$ – Douglas S. Stones May 23 '13 at 1:10
3
$\begingroup$

Yes, there does exist such a way. First you select a digit d from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Then you select a digit e from ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}-d). Then you select a digit f from (({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}-d)-e). You first select 0 for d, then 1, and so on until you get to 7. And, you always select the least digit first for e and f also, with the additional condition that d < e < f. List out the first sequence, 012, 013, 014, 015, 016, 017, 018, 019. Then list all the other numbers beneath them with the condition that for all numbers e and f, and with d held constant, the digits for e and f follow the natural number sequence down the column. Partition each set of sequences by d. The column rule only applies within each partition. (this description might come as incomplete or could use some revision).

The list thus goes:

012, 013, ...,         019
023, 024, ...,     029
034, 035, ..., 039
.
.
.
089

123, 124, ...,      129
134, 135, ..., 139
.
.
.
189

.
.
.

789

I'll clarify the last part here:

567, 568, 569

578, 579

589


678, 679

689


789

Perhaps better, say we try to do the same thing in base 4. The entire sequence goes

012, 013

023


123

In base 5 the process yields:

012, 013, 014

023, 024

034


123, 124

134


234

Thus, in base 10 the sum of the first 8 triangular numbers gives us the number of such combinations: +(1, 3, 6, 10, 15, 21, 28, 36)=120. Similarly, it should logically follow that for x digit numbers in base z, where x < z, or x=z, there exist +[T$_1$, ..., T$_ (z-(x+1))$] such combinations, where T$_n$ indicates the nth triangular number.

I guess the underlying idea I've used here lies in following the natural number sequence across the rows, and down the columns for the digits e and f also.

$\endgroup$
1
$\begingroup$

You have 10 options for the first, then 9 (10 - the first) for the second, and 8 for the third. That makes $10 \cdot 9 \cdot 8$. But they can be shuffled in $3!$ ways, so the result is: $$ \frac{10 \cdot 9 \cdot 8}{3!} = 120 $$

$\endgroup$
  • 1
    $\begingroup$ This provides a way to find the number of possible combinations without repetition, but it doesn't provide a way to actually generate each combination (which is what this question is asking). $\endgroup$ – Anderson Green May 23 '13 at 0:58
0
$\begingroup$

I think one solution to your question is given by Algorithm L in Volume 4 of "The Art of Computer Programming" by Knuth, section 7.2.1.3. Here is a link to a pre-publication fascicle:

http://www.kcats.org/csci/464/doc/knuth/fascicles/fasc3a.pdf

$\endgroup$
0
$\begingroup$

This JavaScript produces all 120 combinations.

out=[];
for (i=0;i<8;i++) for (j=i+1;j<9;j++) for (k=j+1;k<10;k++) out.push(''+i+j+k);
out.join(', ');

Each loop starts from either $0$ or one after the previous loop, and continues as far as it can go allowing for the other loops. ''+i+j+k is a string in JavaScript, so the output is:

$012, 013, 014, 015, 016, 017, 018, 019, 023, 024, 025, 026, 027, 028, 029, 034, 035, 036, 037, 038, 039, 045, 046, 047, 048, 049, 056, 057, 058, 059, 067, 068, 069, 078, 079, 089, 123, 124, 125, 126, 127, 128, 129, 134, 135, 136, 137, 138, 139, 145, 146, 147, 148, 149, 156, 157, 158, 159, 167, 168, 169, 178, 179, 189, 234, 235, 236, 237, 238, 239, 245, 246, 247, 248, 249, 256, 257, 258, 259, 267, 268, 269, 278, 279, 289, 345, 346, 347, 348, 349, 356, 357, 358, 359, 367, 368, 369, 378, 379, 389, 456, 457, 458, 459, 467, 468, 469, 478, 479, 489, 567, 568, 569, 578, 579, 589, 678, 679, 689, 789$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.