0
$\begingroup$

I want an algorithm (just the idea, not the actual code) to generate a random $n$ by $n$ matrix with binary entries, but with the condition that the number of nonzeros must be a fixed number $c$. Any idea of how I can do that?

The obvious way I thought is starting with a matrix of zeros, and setting $k=1$, then proceeding as:

while $k<=c$

pick a random number $r$ between $1$ and $n^2$

if the entry $A_{ij}$ identified with $r$ isn't $1$, then set it to $1$. and $k \leftarrow k+1$, else pick another number $r$ and repeat the previous step.

However there's no guarantee that this procedure will end, since it could be that it always picked the same entry which is already $1$...

$\endgroup$
  • 4
    $\begingroup$ Depending on your language, there might be a shuffle method for arrays. If there is one, then just make a matrix with $c$ ones and shuffle it. $\endgroup$ – Arthur Jan 24 '15 at 0:24
  • $\begingroup$ Well, I... haven't thought about that. Thanks. $\endgroup$ – karlabos Jan 24 '15 at 0:27
  • $\begingroup$ That would be the simplest way to do it. If you're interested I could post an algorithm to do it from scratch though. $\endgroup$ – Math1000 Jan 24 '15 at 0:28
  • $\begingroup$ Your best option depends on the number of non-zeroes. However the random pick will work reasonably well where $c$ is a low proportion of $n\times n$. $\endgroup$ – Joffan Jan 24 '15 at 0:30
  • 1
    $\begingroup$ In Matlab you're looking for the randperm function to shuffle array indices: rng(1); c=20; n=10; A1=zeros(n,n); A2=A1; A1(1:c)=1; A2(:)=A1(randperm(numel(A1))) $\endgroup$ – horchler Jan 24 '15 at 1:27
1
$\begingroup$

You basically want to identify the set of positions where the entry will be $1$. So you are looking to choose a random set of size $c$ from a set of size $n^2$. There are $\binom{n^2}{c}$ such possibilities, and you want to choose one of them uniformly randomly.

Look at algorithms for choosing a random subset. A simple idea would be to randomly choose a $p_1$ from $\{1,\ldots,n^2\}$ first. Then randomly choose a $p_2$ from $\{1,\ldots,\hat{p_1},\ldots n^2\}$ where the hat indicates to omit that number. Alternatively you could pick a number from $\{1,\ldots n^2-1\}$, and adjust: if the number is less than $p_1$, then it's your $p_2$, and otherwise, that number plus $1$ is your $p_2$. And so on with more $p_i$.

Also, there is actually a nice way to order the subsets represented by $\binom{n^2}{c}$ that is a bit more complicated than I would go into here. With that ordering, you could choose a random integer from $\{1,\ldots,\binom{n^2}{c}\}$ and then use the corresponding subset of the $n^2$ entries. So for example, with $n=5$ and $c=2$, we have $\binom{n^2}{2}=300$. And if you randomly chose a number, say $113$, from $\{1,\ldots,300\}$, there is a quick algorithm to identify the $113$th subset of size $2$ from among all subsets of size $2$.

$\endgroup$
1
$\begingroup$

If you use Matlab, that's already been done for you with the randsample function. You can call it to pick c values from 1 to n^2, without replacement. Those values serve as linear indices of the matrix entries that should be set to 1:

n = 5;
c = 8;
M = zeros(n,n);
M(randsample(n^2,c)) = 1;

If you want to do it more manually: generate a random permutation of the set 1, ..., n^2, and use the first c values as linear indices of the matrix entries that equal 1. The random permutation is obtained manually by generating n^2 random values with uniform distribution (rand function), sorting them, and taking note of the indexing implied by that sorting (second output of sort):

n = 5;
c = 8;
M = zeros(n,n);
[~, perm] = sort(rand(1,n^2));
M(perm(1:c)) = 1;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.