[Math] Generate all possible combinations of 3 digits without repetition

combinatorics

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?

Best Answer

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.