Information Technology Reference
In-Depth Information
3. Loop over
S
. Denote by
k
the
j
th element of
S
.Ifthe
k
th element of
P
2
is 0,
this means we have not yet used
k
in our permutation.
Set
P
2
(
k
) to
j
to mark it as used.
Set
P
1
(
j
) to
k
.
4. Initialize a counter
k
to 1.
5. Loop over
P
1
.Ifthe
j
th element,
P
1
(
j
), is 0 then it needs to be filled in with a
positive integer not yet used.
Find smallest
k
for which
P
2
(
k
) is 0 (telling us that
k
is not used as yet in the
permutation).
For that
k
,set
P
1
(
j
) to be
k
,andmark
P
2
(
k
) nonzero (alternatively, could
simply increment
k
so it will not revisit this value).
6. Return
P
1
.
getPerm2 = Compile[
{{
{{
{{
vec
,
Integer
,
1
vec
,
Integer
,
1
vec
,
Integer
,
1
}}
}}
}}
,
Module[
,
Module[
,
Module[
getPerm2 = Compile[
getPerm2 = Compile[
{
{
{
p1
,
p2
,
len = Length[vec]
,
k
p1
,
p2
,
len = Length[vec]
,
k
p1
,
p2
,
len = Length[vec]
,
k
}
}
}
,
p1 = p2 = Tab le[0
,
,
p1 = p2 = Tab le[0
,
,
p1 = p2 = Tab le[0
,
{
{
{
len
}
}
}
];
len
len
];
];
Do[
k
= vec[[
j
]];
Do[
k
= vec[[
j
]];
If[p2[[
k
]] == 0
,
p2[[
k
]] =
j
;p1[[
j
]] =
k
; ]
,{
If[p2[[
k
]] == 0
,
p2[[
k
]] =
j
;p1[[
j
]] =
k
; ]
,
If[p2[[
k
]] == 0
,
p2[[
k
]] =
j
;p1[[
j
]] =
k
; ]
,{
{
j
,
len
j
,
len
j
,
len
}
}
];
}
];
];
k
= 1;
k
= 1;
Do[If[p1[[
j
]] == 0
,
While[p2[[
k
]]
Do[If[p1[[
j
]] == 0
,
While[p2[[
k
]]
Do[If[p1[[
j
]] == 0
,
While[p2[[
k
]]
= 0
,
k
++];
= 0
,
k
++];
= 0
,
k
++];
p1[[
j
]] =
k
;
p1[[
j
]] =
k
;
p2[[
k
]] =
j
]
,
p2[[
k
]] =
j
]
,
p2[[
k
]] =
j
]
,
{
{
{
j
,
len
j
,
len
j
,
len
}
}
}
];
];
];
p1]];
We illustrate with a small example. Say we have the vector
.Whatpermu-
tation does this represent? Well, we have a 4 in the first slot, so the resulting permutation
vector starts with 4. Then we have a 1, so that's the next element in the permutation.
Next is a 4, which we have already used. We defer on that slot. Next is a 3, so the fourth
slot in our permutation is 3. last is a 1, which we have already encountered, so we defer
on filling in the fifth position of our permutation. We have completed one pass through
the permutation. The entries we were unable to use were in positions 3 and 5. The val-
ues not yet used are 2 and 5 (because we filled in a vector as
{
4
,
1
,
4
,
3
,
1
}
,where
x
and
y
are not yet known). We now simply use these in order, in the empty slots. That is, entry
3 is 2 and entry 5 is 5. We obtain as our permutation
{
4
,
1
,
x
,
3
,
y
}
{
4
,
1
,
2
,
3
,
5
}
.
getPerm2[
getPerm2[
getPerm2[
{
{
{
4
,
1
,
4
,
3
,
1
4
,
1
,
4
,
3
,
1
4
,
1
,
4
,
3
,
1
}
}
}
]
]
]
{
4
,
1
,
2
,
3
,
5
}
This notion of associating a list with repeats to a distinct shuffle has a clear drawback
insofar as earlier elements are more likely than later ones to be assigned to their cor-
responding values in the vector. All the same, this provides a reasonable way to make
a chromosome vector containing repeats correspond to a permutation (and once the
method has started to produce permutations, mating/mutation will not cause too many
repeats provided the crossover probability is either fairly low or fairly high). Moreover,
one can see that any sensible mating process of two chromosomes will less drastically
Search WWH ::
Custom Search