Geek Answers Handbook

Algorithm for creating a unique random concatenation of elements

I am thinking of an algorithm that will create the X most unique concatenations of Y-parts, where each part can be one of several elements. For example, 3 parts:

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

And (random, one case of some possibilities) the 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 the following concatenation:

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

Simple GOOD following result:

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

, , . , uniqe, ( , , 2 , 3 , ). , "" - .

,

, ? , ? , , , - ? , .

, (, , , , ) - .

, od , -, , - . , uniqe , .

+5
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 ( )

+1

More articles:


All Articles