创建唯一的随机项目串联的算法

Question

我正在考虑一种算法，该算法将创建 Y 部分的 X 个最独特的串联，其中每个部分可以是多个项目之一。例如 3 个部分:

part #1: 0,1,2
part #2: a,b,c
part #3: x,y,z

And the (random, one case of some possibilities) result of 5 concatenations:

0ax
1by
2cz
0bz (note that '0by' would be "less unique " than '0bz' because 'by' already was)
2ay (note that 'a' didn't after '2' jet, and 'y' didn't after 'a' jet)

Simple BAD results for next concatenation:

1cy ('c' wasn't after 1, 'y' wasn't after 'c', BUT '1'-'y' already was as first-last 

下一个简单的好结果是:

0cy ('c' wasn't after '0', 'y' wasn't after 'c', and '0'-'y' wasn't as first-last part)
1az
1cx

我知道这个解决方案限制了可能的结果，但是当所有完整的唯一可能性都消失时，算法应该继续并尝试保持最可用的唯一性(尽可能少地重复)。

考虑真实的例子:

Boy/Girl/Martin
bought/stole/get
bottle/milk/water

我想要这样的结果:

Boy get milk
Martin stole bottle
Girl bought water
Boy bought bottle (not water, because of 'bought+water' and not milk, because of 'Boy+milk')

也许从所有组合的树开始，但如何首先选择最独特的树？

编辑根据this sample data ，我们可以看到，为 4 个单词 * 3 种可能性创建完全独特的结果，只为我们提供了 3 个结果:

Martin stole a bootle
Boy bought an milk
He get hard water

但是，可以请求更多结果。因此，4. 结果应该是最可用的唯一性，例如 Martin bought hard milk，而不是 Martin stole a water

编辑:有些人开始寻求解决方案？ 将每个部分想象成一个可以旋转的桶，向下旋转时最后一个项目在第一个，向上旋转时第一个项目在最后一个。现在，像这样设置 barells:

Martin|stole |a   |bootle
Boy   |bought|an  |milk
He    |get   |hard|water

现在，按照 We see 写句子，第一个 barell 向上旋转一次，第二个旋转两次，第三个旋转三个，依此类推。我们得到句子(注意第三个 barell 做了一个完整的旋转):

Boy   |get   |a   |milk
He    |stole |an  |water
Martin|bought|hard|bootle 

然后我们得到下一个解决方案。我们可以再处理一次以获得更多的解决方案:

He    |bought|a   |water
Martin|get   |an  |bootle
Boy   |stole |hard|milk 

问题是第一个桶将与最后一个桶连接，因为旋转平行。 我想知道如果我在最后一个解决方案中将最后一个桶再旋转一次是否会更独特(但我提供其他连接，如水 - 但这只会重复 2 次，而不是像现在这样重复 3 次)。不知道这里“桶”是一种很好的思维方式。

我认为我们应该首先找到唯一性的定义

例如，什么改变了唯一性以下降？如果我们使用已经使用过的词？重复彼此靠近的 2 个词是否比在其他词的某些间隙中重复一个词更不独特？所以，这个问题可能是主观的。

但我认为在很多序列中，每个单词应该被使用相似的次数(比如随机选择单词并从集合中移除，并且在获得所有单词后刷新所有选项，以便下次可以获得它们) - 这很容易做。

但是，即使我们得到每个单词相似次数 od 次，我们也应该做一些事情来避免单词之间的重复连接。我认为，更独特的是重复的单词彼此远离，而不是彼此相邻。

Answer 1

任何时候您需要一个新的串联，只需生成一个完全随机的串联，计算它的适应度，然后接受该串联或拒绝它(即概率)。

const C = 1.0

function CreateGoodConcatenation()
{
  for (rejectionCount = 0; ; rejectionCount++)
  {
    candidate = CreateRandomConcatination()
    fitness = CalculateFitness(candidate) // returns 0 < fitness <= 1
    r = GetRand(zero to one)
    adjusted_r = Math.pow(r, C * rejectionCount + 1)  // bias toward acceptability as rejectionCount increases
    if (adjusted_r < fitness)
    {
      return candidate
    }
  }
}

CalculateFitness 永远不应返回零。如果是这样，您可能会发现自己陷入无限循环。

随着 C 的增加，不太理想的连接更容易被接受。 随着 C 的减小，每次调用 CreateGoodConcatenation 的迭代次数都会增加(加上结果中的熵会减少)