Hello,

I'm trying to permute a vector of positive integers > 0 with the constraint
that each element must be <= twice the element before it (i.e. for some
vector x, x[i] <= 2*x[i-1]), assuming the "0th" element is 1.  Hence the
first element of the vector must always be 1 or 2 (by assuming the "0th"
element is 1).  Similarly, the 2nd must always be below/= 4, the 3rd always
below/= 6, etc.

Here's an example, suppose I have the vector x
x <- 2:6

This vector already fits the constraint, and a permutation such as

x.good <- c(2,4,6,5,3)

would also fit the constraint, but the vector

x.bad1 <- c(4,6,5,3,2)

does not work because of the 4 in the first position.  The vector

x.bad2 <- c(2,6,5,3,4)

does not work because of the 6 in the second position.

Does anyone know of a pre-made function to permute a vector under such a
constrain?  Or perhaps a clever way to somehow use a function (e.g. ---)
that permutes a contingency table constrained by the marginals?

If such possibilities are not out there, what about this idea:

Assume the given vector already complies with the constraint (e.g. x <-
2:6).

First "cut" the vector (like cutting a deck of cards) at some random (given
condition*) position p:

x1 <- x[1:(p-1)]
x2 <- x[p:length(x)]
x <- c(x2,x1)

* the condition is that p must be chosen such that x2[1] <= 2.

Then "shuffle" the updated vector x by swapping two of its elements, e.g.

temp.x <- x[i]
x[i] <- x[j]
x[j] <- temp.x

Here i and j must be chosen such that the resulting swap does not violate
the condition x[i] <= 2*x[i-1].  Ideally, all the possible swaps could be
represented in a matrix of 0/1 or FALSE/TRUE, such as
z <- c(2,4,6,5,3)

Z <- matrix(c(    1,0,0,0,0,
        0,1,0,0,1,
        0,0,1,1,1,
        0,0,1,1,1,
        0,1,1,1,1),5,5)

Then one would repeat these two processes many times, each time randomly
choosing to either cut or shuffle.

My issue is I don't really know how to get the matrix of allowable swaps--I
don't know how to automate distinguishing which swaps are allowable and
which aren't.

So my questions here are: most importantly does this method even seem sound
(i.e. are all possible solutions likely to have equal probability)? and
secondly, how would I find all possible swaps?

Thanks in advance for any insight.

-Andy

	[[alternative HTML version deleted]]

