$A$ is a $M$x$N$ matrix whose entries are positive. $x$ is a $N$ dimensional binary (i.e. consisting of $0$s and $1$s) vector and the number of $1$s in $x$ is constant. Let $y = Ax$. The distribution of $x$ is given by
$p(x) \propto \prod_{i=1}^M y_i$
where $y_i$ is the $i^{\rm th}$ element of $y$.
How can one fairly and efficiently sample from this distribution?
I'm planning to do Gibbs sampling but its computational complexity is high (drawing a random $x$ is $\mathcal{O}(MN)$). I'm looking for a more efficient sampling method or tricks to make Gibbs faster.