Re: [R] Permutations

From: Rolf Turner <rolf_at_math.unb.ca>
Date: Wed 14 Jul 2004 - 07:58:54 EST


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
					rolf@math.unb.ca

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/
>
> ______________________________________________
> R-help@stat.math.ethz.ch 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 r-help-bounces@stat.math.ethz.ch Tue Jul 13 17:19:55 2004
> From: "Baskin, Robert" <RBaskin@ahrq.gov>
> To: =?iso-8859-1?Q?=27Jordi_Altirriba_Guti=E9rrez=27?= <altirriba@hotmail.com>,
> r-help@stat.math.ethz.ch
> 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 r-help-bounces@stat.math.ethz.ch does not designate permitted sender hosts)
> Received-SPF: none (hypatia: domain of rbaskin@ahrq.gov 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: r-help@stat.math.ethz.ch
> 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:r-help-request@stat.math.ethz.ch?subject=unsubscribe>
> List-Archive: <https://www.stat.math.ethz.ch/pipermail/r-help>
> List-Post: <mailto:r-help@stat.math.ethz.ch>
> List-Help: <mailto:r-help-request@stat.math.ethz.ch?subject=help>
> List-Subscribe: <https://www.stat.math.ethz.ch/mailman/listinfo/r-help>,
> <mailto:r-help-request@stat.math.ethz.ch?subject=subscribe>
> 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:altirriba@hotmail.com]
> Sent: Tuesday, July 13, 2004 3:07 PM
> To: r-help@stat.math.ethz.ch
> 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/



R-help@stat.math.ethz.ch 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 Received on Wed Jul 14 08:19:19 2004

This archive was generated by hypermail 2.1.8 : Wed 03 Nov 2004 - 22:54:56 EST