Looking for “Domino combination” algorithm
-
18-09-2019 - |
Question
I'm going to complete my apprenticeship as coder and I got a nice j2me project to work on, but I have to admit that I'm not that good with mathematical algorithms as I'd like to be.
My problem is to create all possible "domino pairs" from a given set of values. For example: The possible values go from 0 to 6. Now imagine some domino tokens with those values. The output should then be something like this:
00
01
02
03
04
05
06
11
12
13
...
Each pair only appears a single time but pairs with two equal values are possible.
I've already searched for this problem, but either I didn't find a solution for this particular problem or I didn't really understand how the algorithms work.
I'd really appreciate any explanations and algorithms. Feel free to post alternative solutions as well. I'd prefer to not just have a solution, but to understand it as well ;)
Solution
Pseudo code:
for i from 0 to n inclusive
for j from i to n inclusive
output i,j
The important point is that the second loop doesn't start from zero. This means we don't have to test if a domino has already been used. We know that all dominos produced using this algorithm are unique because of the way the algorithm is constructed.