As has been pointed out by Robert Baskin, your ``restricted''
permutations comprise the bulk of all permutations; i.e. the
restriction isn't as restrictive as one might have expected.
So constructing ***all*** restricted permutations is probably not
very useful.
However if you simply wish to ***generate*** restricted permutations
at random, then your problem is (I think) solvable as follows:
===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===
restr.perm <- function ()
{
S <- 4:12
G <- NULL
A <- list(1:3,4:6,7:9,10:12)
for(k in 1:4) {
for(i in A[[k]]) {
tmp <- union(i,S)
tmp <- setdiff(tmp,G)
x <- if(length(tmp)==1) tmp else sample(tmp,1)
G <- c(G,x)
S <- setdiff(S,G)
}
S <- union(S,A[[k]])
R <- if(k < 4) A[[k+1]] else NULL
R <- union(R,G)
S <- setdiff(S,R)
}
G
}
===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===
Sample output:
> set.seed(42)
> restr.perm()
[1] 12 11 5 2 10 9 4 8 3 7 1 6
> restr.perm()
[1] 10 12 5 9 3 2 7 1 4 8 11 6
which look O.K. according to my understanding of your criterion
for ``acceptable'' permutations.
cheers,
Rolf Turner
[EMAIL PROTECTED]
Jordi Altirriba wrote:
> Dear R users,
> I'm a beginner user of R and I've a problem with permutations that I
> don't know how to solve. I've 12 elements in blocks of 3 elements and
> I want only to make permutations inter-blocks (no intra-blocks)
> (sorry if the terminology is not accurate), something similar to:
>
> 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
>
> 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - -
> 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - - -
> 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
> - -
> 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
> - - - - - -
> 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
> - -
> ....
>
> Thanks for your time,
>
> Jordi Altirriba
> Ph D student
>
> Hospital Clinic – Barcelona - Spain
>
>
> MSN Motor. http://motor.msn.es/researchcentre/
>
> ______________________________________________
> [EMAIL PROTECTED] mailing list
> https://www.stat.math.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>
> From [EMAIL PROTECTED] Tue Jul 13 17:19:55 2004
> From: "Baskin, Robert" <[EMAIL PROTECTED]>
> To: =?iso-8859-1?Q?=27Jordi_Altirriba_Guti=E9rrez=27?= <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED]
> Subject: RE: [R] Permutations
> Date: Tue, 13 Jul 2004 16:12:46 -0400
> MIME-Version: 1.0
> X-OriginalArrivalTime: 13 Jul 2004 20:14:08.0328 (UTC)
> FILETIME=[F4123480:01C46915]
> Received-SPF: none (hypatia: domain of [EMAIL PROTECTED] does not designate
> permitted sender hosts)
> Received-SPF: none (hypatia: domain of [EMAIL PROTECTED] does not designate
> permitted sender hosts)
> X-Virus-Scanned: by amavisd-new at stat.math.ethz.ch
> Content-Transfer-Encoding: 8bit
> X-MIME-Autoconverted: from quoted-printable to 8bit by hypatia.math.ethz.ch id
> i6DKABdp031609
> Cc:
> X-BeenThere: [EMAIL PROTECTED]
> X-Mailman-Version: 2.1.5
> List-Id: "Main R Mailing List: Primary help" <r-help.stat.math.ethz.ch>
> List-Unsubscribe: <https://www.stat.math.ethz.ch/mailman/listinfo/r-help>,
> <mailto:[EMAIL PROTECTED]>
> List-Archive: <https://www.stat.math.ethz.ch/pipermail/r-help>
> List-Post: <mailto:[EMAIL PROTECTED]>
> List-Help: <mailto:[EMAIL PROTECTED]>
> List-Subscribe: <https://www.stat.math.ethz.ch/mailman/listinfo/r-help>,
> <mailto:[EMAIL PROTECTED]>
> X-Spam-Math-Flag: NO
> X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on erdos.math.unb.ca
> X-Spam-Math-Status: No, hits=-4.9 required=5.0 tests=BAYES_00 autolearn=ham
> version=2.63
>
> I may be confused, but I think what you described will produce greater than
> 472 million permutations. I think your second permutation <1 2 4 | 3 5 6 |
> 7 8 9 | 10 11 12 YES-----2nd permutation> shows that you want more than
> just a permutation of entire blocks.
>
> There are a total of 12! (12 factorial) permutations of 1:12 ignoring your
> blocking restriction.
>
> There are 3! * 9! Permutations in which the first block has an intrablock
> permutation and the rest of the 9 symbols can do anything. Since there are
> 4 blocks then there are fewer than 4 * 3! * 9! permutations with intra-block
> transfers (this 4*3!*9! double counts some intrablock permutations - you
> need to take out of the 9! the count of intra-block only permutations among
> the remaining 9 symbols: 3!*3!*3!).
>
> This gives more than
> 12! - 4*3!*9! + 1 = 9!*[12*11*10 - 4*3*2*1] + 1 = 12*9![110 - 2] + 1 ~ 472
> million permutations.
>
> How could you possibly deal with all of these permutations? If you can deal
> with this much junk then maybe you can generate all 12! Permutations and
> take out the ones you don't want.
>
> Sorry if I got it totally wrong
> bob
>
>
>
> -----Original Message-----
> From: Jordi Altirriba Gutiérrez [mailto:[EMAIL PROTECTED]
> Sent: Tuesday, July 13, 2004 3:07 PM
> To: [EMAIL PROTECTED]
> Subject: [R] Permutations
>
>
> Dear R users,
> I'm a beginner user of R and I've a problem with permutations that I don't
> know how to solve. I've 12 elements in blocks of 3 elements and I want only
> to make permutations inter-blocks (no intra-blocks) (sorry if the
> terminology is not accurate), something similar to:
>
> 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
>
> 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - -
> 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - - -
> 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
> - -
> 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
> - - - - - -
> 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
> - -
> ....
>
> Thanks for your time,
>
> Jordi Altirriba
> Ph D student
>
> Hospital Clinic - Barcelona - Spain
>
>
> MSN Motor. http://motor.msn.es/researchcentre/
______________________________________________
[EMAIL PROTECTED] mailing list
https://www.stat.math.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
