Being reasonably sure that all valid permutations are equally probable is
important to me.  I've played around with search algorithms in permuting
contingency tables and find that possible solutions decrease rapidly once
one starts assigning values, particularly if small values are assigned
first, so it would seem all solutions are not equally probable (not only
that but one frequently encounters "dead ends" where there are values left
to assign and no allowable place to put them).  As such I think I'd opt to
use sample()... several times if needed.

To clarify, yes, I only need one valid permutation, the idea is I'll
generate 1000s of ordered vectors, and then for each one generate one valid
permutation.

Thanks very much for the help and insights--
Andy


On Thu, Jan 28, 2010 at 3:04 PM, Thomas Lumley <tlumley@u.washington.edu>wrote:

> On Thu, 28 Jan 2010, Jason Smith wrote:
>
>  It wouldn't be guaranteed to produce any usable permutation, but it seems
>>> like it would be much faster and so could be repeated until an acceptable
>>> vector is found.  What do you think?
>>>
>>> Thanks--
>>> Andy
>>>
>>>
>> 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.
>>
>
> 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@u.washington.edu        University of Washington, Seattle
>

	[[alternative HTML version deleted]]

