[R] Permutations

[Marc Schwartz]

On Tue, 2004-07-13 at 15:02, Rolf Turner wrote:
> Marc Schwartz wrote (in response to a question from Jordi Altirriba):

snip

> This does not solve the problem that was posed.  It only permutes the
> blocks, and does not allow for swapping between blocks.  For instance
> it does produce the ``acceptable'' permutation
> 
> 	1 2 4 | 3 5 6 | 7 8 9 | 10 11 12   YES-----2nd permutation
> 
> I would guess that a correct solution is likely to be pretty
> difficult.  I mean, one ***could*** just generate all 12!
> permutations of 1 to 12 and filter out the unacceptable ones.  But
> this is getting unwieldy (12! is close to half a billion) and is
> inelegant.  And the method does not ``generalize'' worth a damn.

Rolf,

You are correct. I missed that (not so subtle) change in the line above.
I mis-read the "inter-blocks (no intra-blocks)" requirement as simply
permuting the blocks, rather than allowing for the swapping of values
between blocks. Time for new bi-focals...

As Robert has also pointed out in his reply, this gets quite unwieldy.

One of the follow up questions might be, is it only allowable that one
value at a time can be swapped between blocks or can multiple values be
swapped between blocks simultaneously? 

I am not sure that it makes a substantive impact on the problem or its
solution, however. The question is what is to be done with the resultant
set of permutations?

FWIW, on a 3.2 Ghz P4 with 2Gb of RAM:

> system.time(perms <- permutations(12, 12, 1:12))

Error: cannot allocate vector of size 1403325 Kb
Timing stopped at: 2274.27 54.58 2787.76 0 0


Marc