Find combination of 12 matrix rows, fulfilling certain criterion, from matrix of size 3432 *7
2 visualizzazioni (ultimi 30 giorni)
M=nchoosek(1:14,7) gives matrix of size 3432 * 7.
I want combinations of 12 rows from M, such that each of the 14 numbers in the 12-row combinations has frequency 6.
12 rows with 7 numbers are 84 numbers, and 6 *14 = 84. I think there are several 12-row combinations that fulfill the criterion.
How many such combinations are there and how can I get the row numbers of them?
John D'Errico il 24 Apr 2023
Modificato: John D'Errico il 24 Apr 2023
Finding all possible computations there are would be a computationally hard problem, certainly if you used brute force. It would be intractable at that point. Yes, there are probably many such combinations. However, you need to find only ONE combination, because all others could probably be generated from the first. (That is just conjecture on my part, because I'd need to think about it. And counting the number of possible solutions is an interesting question, probably solvable using group theory.)
Anyway, how would I solve it? First, DON'T use nchoosek. Instead, form it as a binary indicator matrix. We want to find the set of numbers with exactly 7 bits set to 1, from the numbers 0:(2^14-1)
B = dec2bin(0:2^14-1) - '0';
B(sum(B,2) ~= 7,:) = ;
As you can see, there are 3432 rows. Each row is one of the rows that nchoosek would generate.
Now, how can we find ONE solution? That part is also simple, or it should be. (Said, before I solve it.) I'll use a binary ILP solver, thus intlinprog. There will be 3432 binary variables. We want the solution where exactly 12 of them are set to 1, the rest zero. See how this will work.
N = 3432;
intcon = 1:N;
LB = zeros(N,1);
UB = ones(N,1);
f = ones(N,1); % this is pretty much irrelevant, since we just want to find a feasible solution
Aeq1 = ones(1,N);
beq1 = 12; % EXACTLY 12 of the rows will be chosen
Aeq2 = B';
beq2 = repmat(6,14,1); % this enforces that the set chosen will be perfectly balanced
[xsol,fval,exitflag] = intlinprog(f,intcon,,,[Aeq1;Aeq2],[beq1;beq2],LB,UB);
The rows chosen were:
You can now easily enough convert that into an output of the form nchoosek would generate.
Can you generate other random solutions? This should work, to find a different randomly selected set:
f2 = rand(N,1);
[xsol,fval,exitflag] = intlinprog(f2,intcon,,,[Aeq1;Aeq2],[beq1;beq2],LB,UB);
Counting the number of possible solutions, or finding all such possible solutions is another question, as I suggest, probavbly in the realm of group theory, but I have work at home for now. ;-)
David Goodmanson il 25 Apr 2023
Modificato: David Goodmanson il 25 Apr 2023
Once you have a single 12x7 solution you can make many more by random element swapping of elements in that matrix. This will eventually create every possible 12x7, although not in a deterministic fashion. The idea is that for two rows of the 12x7, if element b in row p is not contained in row q, and if element c in row q is not contained in row p, then you can swap elements and get a new solution. The new rows will still have distinct elements and the rule that the number of ones = 6, twos = 6 etc. is not affected.
For each 1x7 row in the matrix, the code below can calculate the row index in the 3432x7 matrix created by nchoosek. Since the total number of rows is only 3432, I chose to use a simple method to determine the row index rather than use some iterative process involving euclidean remainders or the like.
% construct a solution
a = [1:7]+[0:5]';
b = mod([5:-1:1]-[1:6]',12)+1;
c = repmat(13:14,6,1);
n1 = sort([a;[b c]],2)
% 1000 swaps (way more than you really need)
n = n1;
for k = 1:1000
r1 = randi(12);
r2 = randi(12);
c1 = randi(7);
c2 = randi(7);
e1 = n(r1,c1);
e2 = n(r2,c2);
if ~ismember(e1,n(r2,:)) & ~ismember(e2,n(r1,:))
n(r1,c1) = e2;
n(r2,c2) = e1;
n = sort(n,2) % the result
% find the row index for 3432x7 nchoosek, using the 6th row of n as an example
ind = fun(n(6,:))
nch = nchoosek(1:14,7);
nch(ind,:) % agrees with n(6,:)
function ind = fun(rowvec)
% row index of a given nchoosek(14,7) row vector
nch = nchoosek(1:14,7);
nchx = nch*(17.^(7:-1:1))';
nx = rowvec*(17.^(7:-1:1))';
ind = find(nx==nchx);
You can also create another 12x7 matrix nnew from n with with
p = randperm(14);
nnew = p(n)
This changes the elements more quickly than the method above, but it merely maps old numbers into new ones and does not change the basic stucture of n.