algorithm - 搜索算法以生成按偏好排序的组合

Question

我正在尝试找到一种算法来识别结果的有序组合，如下所示：

• 有 N 场比赛，每场比赛有 3 个相互排斥的结果（赢、输或平），总共有 3N 个结果和 3^N 种组合
• 3N 个可能的结果中的每一个都被分配了一个唯一的等级，最优选的结果的等级为 1，最不优选的结果的等级为 3N
• 找出每场比赛的前 M 个结果组合，从包含排名最高的结果的组合开始。

例如，假设 N = 3 并且结果排名如下：

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

鉴于这些排名，组合应按以下顺序排列：

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)

我正在寻找一种生成这些组合的方法，以便获得任意大的 N 值，尽管我不希望得到所有组合。例如，在 N=256 和总共 3^256 个组合的情况下，我希望找到前 500 个组合。

Answer 1

这个算法似乎有效。下面是 Python 中的实现。

本质上，我接受输入，然后按给定结果的值对其进行排序：

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

我称这些命令。然后我生成一个空的结果列表：

[None, None, None]

递归算法非常简单，如下：

1. 如果插槽已满，则打印结果并返回。
2. 否则，以升序遍历未使用的排序。如果排序是针对未使用的插槽，则填充插槽，将排序标记为已使用，然后重复。否则，继续迭代。

这是代码。还有一个额外的技巧可以避免重复，例如，如果我们只填写 ordering #6，我们将只使用 orderings #7、8 和 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

这是它为给定输入打印的结果，与问题匹配：

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)]

如果我随机生成一组 256 场比赛的排名，它似乎会立即运行。

Answer 2

首先，让我们重新表述这个问题，以便抽象出细节并确保我们讨论的是同一个问题。

有 3^N 个长度为 N 的元组。每个元组的分量 a_i (a_1,a_2,...,a_N) 是 1 到 3N （含）之间的不同整数，对于固定的 i，a_i 只能取子集中的值S_i，基数为 3。对于 [1,3N] 中的每个值，元组中只有一个位置可以假设该值。

现在，用 sorted(S) 表示以整数的自然顺序对元组 S 的组件进行排序所产生的元组。我们说一个元组 S 小于一个元组 T 如果 sorted(S) 按字典顺序小于 sorted(T)。

问题在于在现有的 3^N 个元组中以给定的顺序找到前 M 个元组，其中 M << 3^N。

我看到的解决方案原则本质上是通过修剪回溯。

为了以严格的方式修剪搜索空间，计算不大于 M 的 3 的最大幂。假设这个幂是 H。我们有 3^(H+1) > M >= 3^H。此时，您知道您的 M 个元组位于一个集合中，其中 (NH-1) 个元组组件取其最小可能值。这些分量可以找到并固定如下：首先，取可以取值为1的分量i，并将其固定为1。然后，在分量i没有取的[1,3N]的值中，选择最小的，并且将唯一能够获取该值的组件 j 修复为相同的值。以同样的方式继续，固定 (NH-1) 组件。之后，您已经确定了一组最多 3M 个元组。您可以生成完整的元组集（通过对剩余的 H+1 个组件进行详尽搜索），然后对该集合进行排序，获得前 M 个元组。

Answer 3

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;
}

几点注意事项：

1. 如果你用 N=256 和 M=500 运行它（正如它所写的那样），你会发现它太慢了。我确信有一种聪明的方法可以避免我所做的所有排序。
2. 如果您希望 M=500，则 N 不必很大，N=6 就足够了（3^6=729）。如果 N 很大，您会看到一个长的常量前缀/头部，然后是一个短的变化的尾部。如果你稍微思考一下，就不难看出为什么会这样。

Answer 4

您可以在 O(NM) 时间内构建解决方案。这里的解决方案将是 M 个排列的列表，每个排列都有其相关的分数，按分数的降序排列。

如果 N 为 1，则解决方案很简单：您只需根据分数对获得的 3 个结果进行排序（如果 M < 3，则减少解决方案）。也就是说，如果结果分数是赢、输和平，那么解决方案是：

• 排序（[（'W'，赢），（'L'，输），（'D'，平局）]）

（排序是按分数完成的，当然是降序）。

现在进行迭代步骤。给定一个规模为 N - 1 的问题的解决方案（规模为 M），然后考虑一场新的比赛，其结果得分（赢、输、平）。

只需将获胜、失败、平局分数添加到 M 种解决方案中的每一个，然后采取措施。即假设解为[(res_1, score_1), (res_2, score_2), ... (res_M, score_M)]，则：

• 获胜 = [(res_1 + 'W', score_1+win), (res_2 + 'W', score_2+win), ... (res_M + 'W', score_M+win)]
• 失去 = [(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)]

新解将是sorted(wins + loses + draws)[:M]，这是组合解中的前 M 个最大解。请注意，您可以使用 mergesort 中的合并步骤在 O(M) 时间内完成此排序步骤。

这是一些演示该算法的草率代码。对于一个紧凑的解决方案，列表切片和字符串追加需要用 O(1) 替换，并且使用合并步骤而不是一般排序。

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)

输出是：

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