Алгоритм создания уникальной случайной конкатенации предметов

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 

Следующим простым ХОРОШИМ следующим результатом будет:

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

Теперь напишите предложения так, как мы видим, и поверните первый шаг вверх на один раз, второй дважды, третий три и так далее.Мы получаем предложения (обратите внимание, что третий 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 

Проблема в том, что первый ствол будет связан с последним, потому что вращается параллельно.Мне интересно, будет ли это более уникальным, если я поверну последний ствол еще раз в последнем решении (но я предоставляю другие соединения, такие как an-water - но это будет повторяться только 2 раза, а не 3 раза, как сейчас).Не знаю, что «бочки» - хороший способ мыслить здесь.

Я думаю, что мы должны сначала найти определение уникальности

Например, что меняет уникальностьбросить?Если мы используем слово, которое уже использовалось?Разве повторение двух слов близко друг к другу менее уникально, чем повторение слова в некотором промежутке других слов?Таким образом, эта проблема может быть субъективной.

Но я думаю, что во многих последовательностях каждое слово должно использоваться одинаковое время (например, выбор слова случайным образом и удаление из набора, а после получения всех слов обновите все параметры, которыеони могут быть получены в следующий раз) - это легко сделать.

Но, даже если мы получим каждое слово одинаковое число раз, мы должны сделать что-то, чтобы не повторять связи между словами.Я думаю, что более уникальным является повторение слов далеко друг от друга, а не рядом друг с другом.

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 (плюс меньшая энтропия в результате)