Skip to content

Constrained vector permutation

8 messages · Andrew Rominger, Jason, Thomas Lumley +1 more

Jason
# 
Andrew Rominger <ajrominger <at> gmail.com> writes:
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))
Jason
# 
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
Jason
# 
I think I am not understanding what your ultimate goal is so I'm not
sure I can give you appropriate advice.  Are you looking for a single
valid permutation or all of them?

Since that constraint sets a ceiling on each subsequent value, it
seems like you could solve this problem more easily and quickly by
using a search strategy instead of random sampling or generating all
permutations then testing.  The constraint will help prune the search
space so you only generate valid permutations.  Once you are examining
a particular element you can determine which of the additional
elements would be valid, so only consider those.

--jason
Thomas Lumley
#
On Thu, 28 Jan 2010, Jason Smith wrote:

            

      
      
      
    

        
It's easy to generate valid permutations this way.  It does not appear straightforward to ensure that all valid permutations are sampled with equal probability, which I thought was part of the specification of the problem.

       -thomas


Thomas Lumley			Assoc. Professor, Biostatistics
tlumley at u.washington.edu	University of Washington, Seattle

  
  


  


      

    

    
1 day later

    

      
      

        
      

    

    

      
      

        


  

        

      Charles C. Berry
    

    

      
      #
    

  


  

      
On Fri, 29 Jan 2010, Andrew Rominger wrote:

        

            

      
      
      
    

        
Andy,

If you have some sense of importance sampling and/or MCMC you might look 
at

Zaman and Simberloff (2002, Environmental and Ecological Statistics 9,
405--421).

which concerns sampling a binary matrix with fixed margins - not quite 
your problem, but akin to it in being a combinatorial nightmare without 
an obvious direct solution of workable size for real problems.

They define a neighborhood for each allowable matrix s.t. swapping a pair 
of 1's at ij and kl with a pair of 0's at il and kj  (which doesn't 
violate the margin constraints) leads to a member of the neighborhood. 
IIRC, the size of the neighborhood and the sizes of the neighborhoods of 
the members of its neighborhood determine the probabilities of staying put 
or moving to get the next element of the MCMC chain and which member of 
the neighborhood to choose.

I suppose something like that (i.e. defining neighborhoods of allowable 
permutations, measuring their size, and using this to guide sampling or 
develop importance weights) might apply in your case. Maybe something like 
this: start with an ordering of your n-vector that conforms to the 
constraints, look at all the choose(n,2) pairs of elements and check which 
of them could be exchanged to yield another conforming ordering; the 
allowable swaps define the neighborhood, and their number is its size.

So, the idea is to develop an MCMC sampler. Run it for each ordered vector 
to get past the burn in, then take one value from it.

HTH,

Chuck

            

      
      
      
    

        

      
      
    

        
Charles C. Berry                            (858) 534-2098
                                             Dept of Family/Preventive Medicine
E mailto:cberry at tajo.ucsd.edu	            UC San Diego
http://famprevmed.ucsd.edu/faculty/cberry/  La Jolla, San Diego 92093-0901