Information Technology Reference
In-Depth Information
Outline of getPerm
getPerm
1. Input: a shuffle
S
encoded as
n
−
1 integers in the range
{
1
,...,
n
}
, with the
j
th
.
2. Initialize a vector
P
of length
n
to be the identity permutation (that is, the
ordered list
actually restricted to lie in the subrange
{
j
,...,
n
}
{
1
,...,
n
}
).
3. Iterate over
S
.
4. Swap the
j
th element of
P
with the element whose index is the (current)
j
th
element of
S
.
5. Return
P
.
getPerm = Compile[
{{
{{
{{
shuffle
,
Integer
,
1
shuffle
,
Integer
,
1
shuffle
,
Integer
,
1
}}
}}
}}
,
Module[
,
Module[
,
Module[
getPerm = Compile[
getPerm = Compile[
{
{
{
perm
,
len = Length[shuffle]+1
perm
,
len = Length[shuffle]+1
perm
,
len = Length[shuffle]+1
}
}
}
,
,
,
perm = Range[len];
perm = Range[len];
Do[perm[[
Do[perm[[
Do[perm[[
{
{
{
j
,
shuffle[[
j
]]
j
,
shuffle[[
j
]]
j
,
shuffle[[
j
]]
}
}
}
]] = perm[[
]] = perm[[
]] = perm[[
{
{
{
shuffle[[
j
]]
,
j
shuffle[[
j
]]
,
j
shuffle[[
j
]]
,
j
}
}
}
]]
,
]]
,
]]
,
{
{
{
j
,
len
j
,
len
j
,
len
−
−
−
1
1
1
}
}
}
];
];
];
perm]];
Okay, maybe that was a bit cryptic. Here is a brief example that will shed light on
this process. Say our shuffle encoding for a set of five elements is
{
2
,
4
,
5
,
4
}
.What
would this do to permute the set
{
1
,
2
,
3
,
4
,
5
}
? First we swap elements 1 and 2, so we
have
{
2
,
1
,
3
,
4
,
5
}
. We next swap elements 2 and 4, giving
{
2
,
4
,
3
,
1
,
5
}
.Thenweswap
elements 3 and 5 to obtain
. Finally, as the fourth element in our shuffle is
a 4, we do no swap. Let us check that we did indeed get the permutation we claim.
{
2
,
4
,
5
,
1
,
3
}
getPerm[
getPerm[
getPerm[
{
{
{
2
,
4
,
5
,
4
2
,
4
,
5
,
4
2
,
4
,
5
,
4
}
}
}
]
]
]
{
2
,
4
,
5
,
1
,
3
}
The constraints we would like to enforce are that all chromosome elements be integers,
and that the
j
th such element be between
j
and the total length inclusive. The bit of
code below will show how we might set up such constraints.
len = 5;
len = 5;
vars = Array[
x
,
len
1];
constraints = Prepend[Map[(#[[1]]
vars = Array[
x
,
len
vars = Array[
x
,
len
−
−
−
1];
1];
constraints = Prepend[Map[(#[[1]]
constraints = Prepend[Map[(#[[1]]
≤
≤
≤
#
#
#
≤
≤
≤
len)&
,
vars]
,
Element[vars
,
Integers]]
len)&
,
vars]
,
Element[vars
,
Integers]]
len)&
,
vars]
,
Element[vars
,
Integers]]
{
(
x
[1]
|
x
[2]
|
x
[3]
|
x
[4])
∈
Integers
,
1
≤
x
[1]
≤
5
,
2
≤
x
[2]
≤
5
,
3
≤
x
[3]
≤
5
,
4
≤
x
[4]
≤
5
}
There is a small wrinkle. It is often faster not to insist on integrality, but rather to use
real numbers and simply round off (or truncate). To get uniform probabilities initially,
using rounding, we constrain so that a given variable is at least its minimal allowed
integer value minus 1/2, and at most its maximal integer value plus 1/2.
Without further fuss, we give an outline and code for this optimization approach.
Search WWH ::
Custom Search