[R] create matrices with constraint

[David L Carlson]

Actually there are not so many matrices as you suggest.

> comb <- combn(28, 4)
> dim(comb)
[1]     4 20475
> sum(comb[1,]==1)
[1] 2925
> comb[, 1]
[1] 1 2 3 4

There are 20,475 combinations, but you cannot choose any four to make a 4x7 matrix since each value can be used only once. The combn() function returns the combinations sorted, so we can get the number of combinations that contain 1 with sum(comb[1,]==1) and that is 2,925. The set of 4x7 matrices cannot use the same combination more than once, so 2,925 is the maximum possible number of matrices and there may be fewer. As a first approach to finding them, you could take the first combination comb[, 1] which is 1, 2, 3, 4. Now add a second combination that does not include 1:4 and then a third combination that does not include any in the first two combinations and finally a fourth that does not include any in the first three combinations. Actually this is easy since we will just take 1:4, 5:8, 9:12, 13:16, 17:20, 21:24, 24:18.

> cols <- sapply(c(1, 5, 9, 13, 17, 21, 24), function(x)
+  head(which(comb[1,]==x), 1))
> cols
[1]     1  9850 15631 18656 19981 20406 20471
> comb[,cols]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    5    9   13   17   21   24
[2,]    2    6   10   14   18   22   25
[3,]    3    7   11   15   19   23   26
[4,]    4    8   12   16   20   24   27

But now it gets more complicated. While building the second matrix, we have to make sure that it does not use any combinations that have already been used.  Combinations used on earlier matrices may be necessary to complete later matrices and that is why the number of sets may be less than 2,925. This sequential approach would guarantee to obtain matrices meeting the OP's criteria, but would not necessarily produce the maximum number of matrices possible. 

-------------------------------------
David L Carlson
Department of Anthropology
Texas A&M University
College Station, TX 77840-4352

-----Original Message-----
From: R-help [mailto:r-help-bounces at r-project.org] On Behalf Of John McKown
Sent: Monday, December 15, 2014 9:23 AM
To: Kathryn Lord
Cc: r-help
Subject: Re: [R] create matrices with constraint

On Fri, Dec 12, 2014 at 11:00 AM, Kathryn Lord <kathryn.lord2000 at gmail.com>
wrote:

> Dear all,
>
> Suppose that I have natural numbers 1 through 28.
>
> Based on these numbers, choose 4 numbers 7 times without replacement and
> make a 4 by 7 matrix, for example,
>
>
​After a relaxing weekend, it came to me that these 4x7 matrices are really
just a subset of all the possible permutations of the vector 1:28, recast
as  4x7 matrices. Of course, there are factorial(28) (about 3*10^29 ) such
4x7 matrices. But given your constraints, I think that these can be
subsetted to only those permutations in which the values in each row are
sorted in ascending (or descending) order. I am fairly certain that this
subset would be exhaustive for your purposes. I not really certain how big
that subset would be. I think it would be 1/168th ( 1 out of 7*factorial(4)
) of the 3*10^29 permutations, or about 1.8*10^27. Which is still way to
big to actually instantiate all at once. You might be able store such a
thing in a huge data base. If you're lucky, you have access to a massive
supercomputer so that you can get the results before the heat death of this
universe. (exaggeration?)

Two R libraries seems to address this. One is combinat. The other is
permute.​ The permute library seems, to me, to be the more likely
candidate. It contains a "how()" function which __appears to me__ to
perhaps be a way to subset the permutations as they are being generated.
But all that I get from reading the documentation is a bad headache. I
never studied combinatorics. And I got a milder headache trying to read the
Wikipedia article on it.

​I am curious about what you will do with such a set of matrices, once you
have them. If you are permitted to say.

-- 
​
While a transcendent vocabulary is laudable, one must be eternally careful
so that the calculated objective of communication does not become ensconced
in obscurity.  In other words, eschew obfuscation.

Maranatha! <><
John McKown

	[[alternative HTML version deleted]]

______________________________________________
R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.