I am trying to find an algorithm to identify ordered combinations of outcomes as follows:
For example, assume that N = 3 and the outcomes are ranked as follows:
Contest 1 Win = 1
Contest 1 Tie = 4
Contest 1 Loss = 7
Contest 2 Win = 2
Contest 2 Tie = 5
Contest 2 Loss = 8
Contest 3 Win = 3
Contest 3 Tie = 6
Contest 3 Loss = 9
Given these rankings, the combinations should be ordered as follows:
Contest 1 Win (1), Contest 2 Win (2), Contest 3 Win (3)
Contest 1 Win (1), Contest 2 Win (2), Contest 3 Tie (6)
Contest 1 Win (1), Contest 2 Win (2), Contest 3 Loss (9)
Contest 1 Win (1), Contest 2 Tie (5), Contest 3 Win (3)
Contest 1 Win (1), Contest 2 Loss (8), Contest 3 Win (3)
Contest 1 Win (1), Contest 2 Tie (5), Contest 3 Tie (6)
Contest 1 Win (1), Contest 2 Tie (5), Contest 3 Loss (9)
Contest 1 Win (1), Contest 2 Loss (8), Contest 3 Win (6)
Contest 1 Win (1), Contest 2 Loss (8), Contest 3 Loss (9)
Contest 1 Tie (4), Contest 2 Win (2), Contest 3 Win (3)
Contest 1 Loss (7), Contest 2 Win (2), Contest 3 Win (3)
Contest 1 Tie (4), Contest 2 Win (2), Contest 3 Tie (6)
Contest 1 Tie (4), Contest 2 Win (2), Contest 3 Loss (9)
Contest 1 Loss (7), Contest 2 Win (2), Contest 3 Tie (6)
Contest 1 Loss (7), Contest 2 Win (2), Contest 3 Loss (9)
Contest 1 Tie (4), Contest 2 Tie (5), Contest 3 Win (3)
Contest 1 Tie (4), Contest 2 Loss (8), Contest 3 Win (3)
Contest 1 Loss (7), Contest 2 Tie (5), Contest 3 Win (3)
Contest 1 Loss (7), Contest 2 Loss (8), Contest 3 Win (3)
Contest 1 Tie (4), Contest 2 Tie (5), Contest 3 Tie (6)
Contest 1 Tie (4), Contest 2 Tie (5), Contest 3 Loss (9)
Contest 1 Tie (4), Contest 2 Loss (8), Contest 3 Tie (6)
Contest 1 Tie (4), Contest 2 Loss (8), Contest 3 Loss (9)
Contest 1 Loss (7), Contest 2 Tie (5), Contest 3 Tie (6)
Contest 1 Loss (7), Contest 2 Tie (5), Contest 3 Loss (9)
Contest 1 Loss (7), Contest 2 Loss (8), Contest 3 Tie (6)
Contest 1 Loss (7), Contest 2 Loss (8), Contest 3 Loss (9)
I am looking for a way to generate these combinations in order for arbitrary large values of N, although I don't expect to ever get all combinations. For example, with N=256 and a total of 3^256 combinations I am looking to find the first 500 combinations.
First, let's rephrase the problem in order to abstract the details and to be sure that we are talking about the same problem.
There are 3^N tuples of length N. The components a_i of each tuple (a_1,a_2,...,a_N) are different integers between 1 and 3N inclusive, and for a fixed i, a_i can only take values in a subset S_i, of cardinality 3. For every value in [1,3N] there is one and only one position in the tuple that can assume that value.
Now, denote by sorted(S) the tuple resulting from sorting the components of tuple S in the natural order of integers. We say that a tuple S is less than a tuple T iff sorted(S) is less than sorted(T) in lexicographic order.
The problem consists in finding the first M tuples in the given order, among the 3^N existing ones, where M << 3^N.
The solution principle that I see is essentially backtracking with pruning.
To prune the search space in a critical manner, compute the highest power of 3 not greater than M. Let's say this power is H. We have 3^(H+1) > M >= 3^H. At that point, you know that your M tuples lie in a set where (N-H-1) tuple components take their smallest-possible value. These components can be found and fixed as follows: first, take the component i that can take value 1, and fix it to 1. Then, among the values of [1,3N] not taken by component i, choose the smallest, and fix the only component j able to take that value, to that same value. Continue in the same way, fixing (N-H-1) components. After that, you have determined a set of at most 3M tuples. You can generate that complete set of tuples (by exhaustive search over the remaining H+1 components) and then sort this set, obtaining the first M tuples.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments