我正在尝试寻找一种算法来识别结果的有序组合，如下所示：
例如，假设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个组合。
首先，让我们重新描述问题，以便抽象出细节并确保我们正在谈论同一问题。
存在3 ^ N个长度为N的元组。每个元组的分量a_i（a_1，a_2，...，a_N）是介于1到3N（含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个元组。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句