R help - Jan 2010 - Constrained vector permutation

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]]

Andrew Rominger <ajrominger <at> gmail.com> writes:
> I'm trying to permute a vector of positive integers > 0 with the
constraint
Hi Andy

I'm not sure if you are explicitly wanting to use a sampling approach, but
the
gtools library has a permutations function (found by ??permutation then ?
gtools::combinations).

Hope this helps,
Jason Smith

Here is the script I used:


# Constraint
# f(n_i) <= 2 * f(n_(i-1))
#
# Given a start value and the number of elements
# recursively generate a vector representing the 
# maximum values each index is allowed
#
f <- function(value, num_elements) {
	#cat(paste("f(",value,",",num_elements,")\n"))
	if (num_elements < 1) {
		value;
	} else {
		z <- c(value,f(2*value, num_elements-1))
	}
}

# Generate base vector
v <- 2:6

# Calculate constraint vector
v.constraints <- f(v[1],length(v)-1)

# Generate permutations using gtools functions
library(gtools) 
v.permutations <- permutations(length(v), length(v), v)

# Check each permutation
results <- apply(v.permutations,1, function(x) all(x <= v.constraints))

#
# Display Results
#
print("Original Vector")
print(v)
print("Constraint Vector")
print(v.constraints)
print("Does Vector meet Constraints")
print(cbind(v.permutations,results))

I just realized I read through your email too quickly and my script does
not actually address the constraint on each permutation, sorry about that.

You should be able to use the permutations function to generate the vector 
permutations however.

Jason