[R] Permutations

Rolf Turner rolf at math.unb.ca
Tue Jul 13 23:58:54 CEST 2004


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




More information about the R-help mailing list