Searching for algorithm to generate combinations ordered by preference

Question

I am trying to find an algorithm to identify ordered combinations of outcomes as follows:

• There are N contests, where each contest has 3 mutually exclusive outcomes (win, loss, or tie) for a total of 3N outcomes and 3^N combinations
• Each of the 3N possible outcomes has been assigned a unique rank, with the most preferable outcome having a rank of 1 and the least preferable outcome having a rank of 3N
• Find the first M combinations of outcomes for each contest, starting with the combinations that include the most preferably ranked outcomes.

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.

Answer 1

This algorithm seems to work. An implementation in Python follows.

Essentially I take the input and then sort it by value of the given result:

Contest 1 Win = 1
Contest 2 Win = 2
Contest 3 Win = 3
Contest 1 Tie = 4
Contest 2 Tie = 5
Contest 3 Tie = 6
Contest 1 Loss = 7
Contest 2 Loss = 8
Contest 3 Loss = 9

I call these orderings. Then I generate an empty result list:

[None, None, None]

The recursive algorithm is very simply and is as follows:

1. If the slots are all full, then print the result and return.
2. Otherwise, iterate through the unused orderings in ascending order. If the ordering is for an unused slot, then fill the slot, mark the ordering as used, and recur. Otherwise, keep iterating.

Here's the code. There's an additional trick to avoid duplicates such that if we just filled say ordering #6, we'll only use orderings #7, 8, and 9.

#rankings as tuple of (winval, tieval, lossval) for each
#contest
rankings = [(1, 4, 7), (2, 5, 8), (3, 6, 9)]

#first sort the rankings by their values into
#list of (contestnum, w/t/l, value)
orderings = []
for i, (w, t, l) in enumerate(rankings):
    orderings.append((i, 'w', w))
    orderings.append((i, 't', t))
    orderings.append((i, 'l', l))
orderings.sort(key=lambda (i,res,val): val)

#now, find solution recursively as follows:
#- if list is full then print result & return
#- else, iterate thru the rankings & recur for each unused slot

def solve(orderings, slots, used_orderings, first_ordering):
    if all(slot is not None for slot in slots):
        yield slots
        return

    i = first_ordering
    while i < len(orderings):
        slot, result, value = orderings[i]

        if used_orderings[i]:
            i += 1
            continue
        if slots[slot] is not None:
            i += 1
            continue

        slots[slot] = (result, value)
        used_orderings[i] = True
        for solution in solve(orderings, slots, used_orderings, i):
            yield solution
        #backtrack
        slots[slot] = None
        used_orderings[i] = False

        i += 1

#print the first 40 solutions
num_solutions = 0
for solution in solve(orderings, [None]*len(rankings), [False]*len(orderings), 0):
    print "Solution #%d: %s" % (num_solutions+1, solution)
    num_solutions += 1
    if num_solutions >= 40:
        break

Here is the results it prints for the given input, which matches the question:

Solution #1: [('w', 1), ('w', 2), ('w', 3)]
Solution #2: [('w', 1), ('w', 2), ('t', 6)]
Solution #3: [('w', 1), ('w', 2), ('l', 9)]
Solution #4: [('w', 1), ('t', 5), ('w', 3)]
Solution #5: [('w', 1), ('l', 8), ('w', 3)]
Solution #6: [('w', 1), ('t', 5), ('t', 6)]
Solution #7: [('w', 1), ('t', 5), ('l', 9)]
Solution #8: [('w', 1), ('l', 8), ('t', 6)]
Solution #9: [('w', 1), ('l', 8), ('l', 9)]
Solution #10: [('t', 4), ('w', 2), ('w', 3)]
Solution #11: [('l', 7), ('w', 2), ('w', 3)]
Solution #12: [('t', 4), ('w', 2), ('t', 6)]
Solution #13: [('t', 4), ('w', 2), ('l', 9)]
Solution #14: [('l', 7), ('w', 2), ('t', 6)]
Solution #15: [('l', 7), ('w', 2), ('l', 9)]
Solution #16: [('t', 4), ('t', 5), ('w', 3)]
Solution #17: [('t', 4), ('l', 8), ('w', 3)]
Solution #18: [('l', 7), ('t', 5), ('w', 3)]
Solution #19: [('l', 7), ('l', 8), ('w', 3)]
Solution #20: [('t', 4), ('t', 5), ('t', 6)]
Solution #21: [('t', 4), ('t', 5), ('l', 9)]
Solution #22: [('t', 4), ('l', 8), ('t', 6)]
Solution #23: [('t', 4), ('l', 8), ('l', 9)]
Solution #24: [('l', 7), ('t', 5), ('t', 6)]
Solution #25: [('l', 7), ('t', 5), ('l', 9)]
Solution #26: [('l', 7), ('l', 8), ('t', 6)]
Solution #27: [('l', 7), ('l', 8), ('l', 9)]

And it seems to run instantly if I randomly generate a set of rankings for 256 contests.

Answer 2

GCC 4.7.3: g++ -Wall -Wextra -std=c++0x perm.cpp

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>

using ints = std::vector<int>;

template <typename T>
bool equal(const std::vector<T>& a, const std::vector<T>& b) {
  return std::equal(std::begin(a), std::end(a), std::begin(b)); }

bool is_strictly_monotonic(const ints& p) {
  return std::is_sorted(std::begin(p), std::end(p), std::less_equal<int>()); }

ints gen_seq(int size, int init) {
  ints v(size);
  for (auto& e : v) { e = ++init; }
  return v; }

ints begin_combination(const ints& p, int mod) {
  return gen_seq(p.size(), -1); }

// Not the same as a normal STL end. This is actually the last combination.
ints end_combination(const ints& p, int mod) {
  return gen_seq(p.size(), mod - p.size()); }

// This is the most complicated bit of code, but what it does is
// straightforward. This function treats the input sequence as the
// (radix m+1) digits in a counter. It increments the counter by one, while
// maintaining the constraint that the digits in the sequence be strictly
// monotonic. This means that some numbers in the regular counter sequence
// will be skipped, for example the sequence after {1, 2, 9} (radix 10)
// is {1, 3, 4}. Like all digital counters it wraps on overflow.
void inc_monotonic_seq(ints& p, const int m) {
  assert(is_strictly_monotonic(p));

  int i = p.size() - 1;
  // scan right to left for number to increment
  while (i != -1) {
    if (p[i] < m) {
      ++p[i];
      ints::size_type j = i + 1;
      // propogate carry left to right
      while (j != p.size()) {
        p[j] = p[j - 1] + 1;
        if (m < p[j]) { break; }
        ++j; }
      if (j == p.size()) { break; } }
    --i; }

  // wrap around
  if (i == -1) { p = begin_combination(p, m); }

  assert(is_strictly_monotonic(p));
}

// A combination is valid if each contest is represented once.
bool is_valid_combination(const ints& p, const ints& contests) {
  auto t(p);
  for (auto& e : t) { e = contests[e]; }
  std::sort(std::begin(t), std::end(t));
  return is_strictly_monotonic(t); }

// This is the second most complicated bit of code. It calculates the
// combination following p in the ordered combination sequence. Combinations
// are ordered lexically by the sort of their elements, for example:
// {6, 1, 2} < {3, 1, 5} because {1, 2, 6} < {1, 3, 5}. Further, it enforces
// the constraint that each digit in the combination must be drawn from the
// contest in that position.
bool next_combination(ints& p, const ints& contests) {
  std::sort(std::begin(p), std::end(p));
  const auto mx = end_combination(p, contests.size() - 1);

  do {
    if (equal(p, mx)) { return false; }
    inc_monotonic_seq(p, contests.size() - 1);
  } while (!is_valid_combination(p, contests));

  // Sort in contest order: contest0, contest1, ...
  for (int i = 0; i < p.size(); ++i) {
    while (i != contests[p[i]]) {
      std::swap(p[i], p[contests[p[i]]]); } }

  return true;
}

int main() {
  const int N = 256; // number of contests
  const int M = 500; // number of most preferably ranked outcomes to display

  // This is the third most complicated bit of code. The following vector is
  // a map from priorities to contests. For example, the following 3 contest
  // win-tie-loss priorities {{0, 3, 6}, {1, 4, 7}, {2, 4, 8}} are stored as
  // {0, 1, 2, 0, 1, 2, 0, 1, 2}. This inversion is possible because the
  // contest outcome priorities are required to be disjoint since there is
  // a total ordering over the outcomes. Note, the highest priority is 0
  // (not 1 as in the specification).
  ints contests(3 * N); // map priorities to contests
  int c  = 0;
  for (auto& e : contests) { e = c % N; ++c; }

  // Highest priority combination.
  ints p(N);
  p = begin_combination(p, contests.size() - 1);

  int total = 1;
  do {
    // Finally, doing some sort of mapping here from priorities to strings,
    // as in the problem specification, is trivially done.
    std::copy(std::begin(p), std::end(p), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    if (M < ++total) { break; }
  } while(next_combination(p, contests));

  return 0;
}

A couple of notes:

1. If you run this with N=256 and M=500 (as it is written) you will find it to be too slow. I am sure there is a smart way to avoid all the sorting that I do.
2. If you want M=500 it is not necessary for N to be very large, N=6 will suffice (3^6=729). If N is large what you see is a long constant prefix/head followed by a short changing tail. It is not hard to see why that is if you reflect for a moment.

Answer 3

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.

Answer 4

You can build up the solution in O(N.M) time. A solution here will be a list of M permutations, each with their associated score, in descending order of score.

If N is 1, then the solution is easy: you just order the 3 results you've got, according to their scores (reducing the solution if M < 3). That is, if the outcome scores are win, lose, and draw, then the solution is:

• sorted([('W', win), ('L', lose), ('D', draw)])

(Sorting is done by score, descending of course).

Now for the iterative step. Given a solution (of size M) for a problem of size N - 1, then consider a new contest with outcome scores (win, lose, draw).

Simply add the win, lose, draw scores to each of the M solutions, and resort. That is, suppose that the solution is [(res_1, score_1), (res_2, score_2), ... (res_M, score_M)], then:

• wins = [(res_1 + 'W', score_1+win), (res_2 + 'W', score_2+win), ... (res_M + 'W', score_M+win)]
• loses = [(res_1 + 'L', score_1+lose), (res_2 + 'L', score_2+lose), ... (res_M + 'L', score_M+lose)]
• draws = [(res_1 + 'D', score_1+draw), (res_2 + 'D', score_2+draw), ... (res_M + 'D', score_M+draw)]

The new solution will be sorted(wins + loses + draws)[:M], which is the first M largest solutions from the combined solution. Note, you can do this sorting step in O(M) time using the merge step from mergesort.

Here's some sloppy code that demonstrates the algorithm. For a tight solution, the list slicing and string appends would need to be replaces by something O(1), and a merge step used instead of a general sort.

def results(outcomes, M):
    if len(outcomes) == 1:
        return sorted(zip(outcomes[0], 'WLD'), reverse=True)[:M]
    tr = results(outcomes[1:], M)
    result = []
    for outscore, outcome in zip(outcomes[0], 'WLD'):
        result.extend((sc + outscore, pr + outcome) for sc, pr in tr)
    return sorted(result, reverse=True)[:M]

# Outcome scores for each contest, in order (win, lose, draw).
testcase = [(1, 7, 4), (2, 8, 5), (3, 9, 6)]
print results(testcase, 5)

The output is:

[(24, 'LLL'), (21, 'LLD'), (21, 'LDL'), (21, 'DLL'), (18, 'WLL')]