用于创建项的唯一随机连接的算法

Question

我正在考虑一种算法,它将创建X个最独特的Y部分连接,其中每个部分可以是几个项目之一.例如3部分:

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

并且(随机的,一种可能性的一种情况)结果是5个连接:

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)

下一次连接的简单BAD结果:

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

简单GOOD下一个结果将是:

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

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

编辑:根据这个样本数据,我们可以看到,创建4个单词*3种可能性的完全独特的结果,只为我们提供了3个结果:

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

但是,可以要求更多结果.所以,4.结果应该是最可用的唯一性,比如Martin bought hard milk,不是Martin stole a water

编辑:有些人开始寻求解决方案吗？ 想象一下每个部件都是一个桶,可以旋转,最后一个项目在旋转时向前移动,在旋转时首先是最后一个.现在,设置这样的裸露:

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

现在,按照我们的看法编写句子,然后先旋转UP一次,第二次旋转两次,然后旋转三次,依此类推.我们得到句子(请注意,第三个完全轮换):

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次).不知道"桶"是思考这里的好方法.

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

例如,什么是改变唯一性下降？如果我们使用已经使用的单词？重复彼此接近的两个单词是不是特别重复,在其他单词的某些空白中重复一个单词？所以,这个问题可能是主观的.

但是我认为在很多序列中,每个单词应该使用相似的时间(比如随机选择单词并从集合中删除,并且在让所有单词刷新所有可以在下次获得的选项之后) - 这很容易做到.

但是,即使我们得到每个单词相似的数字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 时您都会面临增加的迭代（加上结果中的熵减少）