How to shuffle cards with restrictions? I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.

For example, i would like to shuffle 4 decks of cards, and make sure:

Any consecutive 4 cards won't come from the same deck.

Surely I can do the fisher-yates-Knuth shuffling first and then filter out bad permutations, but if the restrictions are strong (e.g. any consecutive 2 cards won't come from the same deck), there will be too many failures.

If i don't mind that if it is slightly unbiased, (of course the less bias the better), how should I do?
One way of doing this is to, at each step, draw a random card from all the remaining decks that satisfy the constraints. I would suggest doing this by shuffling all the decks, and then taking the top card from one of the legal decks, picking a deck with probability proportional to the number of cards left in it.

This has the advantages that (a) in the case of no restriction, it is essentially Fisher-Yates-Knuth shuffling, and so gives a completely uniform permutation, and (b) since it favors decks with more cards, it leaves you with a reasonable chance of not ending with a bunch of cards in just one deck.

I suspect this is a reasonably good algorithm to use in practice, depending on what you want it for. However, it is not equivalent to the process of picking a uniform shuffle that satisfies the constraints, as I argue below. 

Suppose you just have two decks, and you have $n/2$ cards in each deck for some large $n$. This question is equivalent to choosing a random way of tiling a length $n$ strip with alternating black or white tiles of length either $1$ or $2$, with the constraint that you have an equal area of black and white. We'll forget both the factor of two that comes from the fact that you can start with either a black or a white tile, and the restriction of equal areas of black and white, since for large $n$ these will contribute lower-order terms. The number of ways of tiling this strip is the $n$th Fibonacci number $F_n$, and the ratio of tiles of length $1$ to those of length $2$ is the golden ratio $\phi=\frac{\sqrt{5}+1}{2}$. You can see this because the last tile is either of length $1$ or length $2$, and for a length $1$ tile, there are $F_{n-1}$ ways of tiling the remaining strip, while for a length $2$ tile, there are $F_{n-2}$ ways. The ratio of the two lengths for the tile ending at position $n$ is thus $F_{n-1}/F_{n-2}$, which converges to $\phi$.

The process I sketched above, of choosing a random card from a legal deck, gives $1$ for this ratio of the number of runs of length $1$ do those of length $2$&mdash;a white card will be followed with equal probability by a white one (making a run of length $2$) or a black one (making a run of length $1$). Thus, it doesn't yield a uniform distribution among shuffles.

ADDED :

Here's an idea that will probably come pretty close to a uniform distribution over all allowed shuffles, although I can't analyze it. Suppose you just have two decks. Start by shuffling each deck. Choose a deck, say A, randomly to start the procedure. Take one card from deck A with probability $1/\phi$ and two cards from deck A with probability $1/\phi^2$. Then do the same for deck B. Keep this up, but adjust the probabilities so that the probability of one card from a deck is $1/\phi \pm \epsilon$, where $\epsilon$ is chosen so that you expect to exhaust the two decks at the same time. For more than two decks, or a restriction to no more than $k$ cards from each deck, you can use the same strategy, but you will have to figure out what the appropriate probabilities for choosing each allowed number of cards in the uniform distribution over allowed shuffles.