3 ms·

I was wondering recently about how you might solve shuffling with constraints - no two cards of the same suit next to each other, 3s at least 4 spaces apart, et

I was wondering recently about how you might solve shuffling with constraints - no two cards of the same suit next to each other, 3s at least 4 spaces apart, etc. My first thought was you'd just maintain a set of valid candidates for the next random card, with backtracking if you get stuck, but there must be better ways.

fotbr 6y ago
I had a similar problem, several constraints (dozen or so, iirc), data set of a few thousand items. I thought about finding an elegant solution, but in the end decided that just doing a (psuedo-)random selection of the remaining set and then running through the resulting ordered list checking each one for all the constraints (ie, random sort). As soon as it failed a hard constraint, or failed > x soft constraints, toss the list and do another random sort. Ugly, but it worked. Chose this solution because 1) I knew how big the data set would be, and I knew it would not change size enough to matter; 2) The other, very jr developer could understand the method; 3) The constraints, while semi-complex, were simple to check; 4) would be needed once or twice a year, could run completely off-line, and could be started well in advance of when it was needed; 5) and finally computers are fast & cheap, while my time is finite and valuable As a result, the decision that "brute force" running on any available workstation for a weekend was an acceptable solution. In it's lifetime, I think the longest time it took to find an acceptable solution was a few hundred thousand sorts, finished in a few minutes. It's now been retired as the program it supported went away. I wish I'd had the time to explore better, more proper solutions, but at the time, quick and dirty and done was more important.
hansvm 6y ago
For arbitrary constraints it's problematic. Suppose you have a programming language capable of expressing a filter `(shuffle_result) => valid`. On average across all possible such functions you'll need at least `factorial(n_cards)` bits just to express the filters. Of course, many special cases you care about can be expressed much more simply. E.g. with the adjacent-suits example you can deterministically generate such decks pretty easily by appropriately composing uniform integer partition sampling, uniform combination sampling, and uniform permutation sampling. For a standard 52-card deck you can basically lay out suit#1, then suit#2, do a little finicky magic to make sure suit#3 is placed uniformly in such a way that a solution exists (at least one always will), and then fill the remaining slots with suit#4.

fotbr 6y ago

I had a similar problem, several constraints (dozen or so, iirc), data set of a few thousand items. I thought about finding an elegant solution, but in the end decided that just doing a (psuedo-)random selection of the remaining set and then running through the resulting ordered list checking each one for all the constraints (ie, random sort). As soon as it failed a hard constraint, or failed > x soft constraints, toss the list and do another random sort. Ugly, but it worked. Chose this solution because 1) I knew how big the data set would be, and I knew it would not change size enough to matter; 2) The other, very jr developer could understand the method; 3) The constraints, while semi-complex, were simple to check; 4) would be needed once or twice a year, could run completely off-line, and could be started well in advance of when it was needed; 5) and finally computers are fast & cheap, while my time is finite and valuable As a result, the decision that "brute force" running on any available workstation for a weekend was an acceptable solution. In it's lifetime, I think the longest time it took to find an acceptable solution was a few hundred thousand sorts, finished in a few minutes. It's now been retired as the program it supported went away. I wish I'd had the time to explore better, more proper solutions, but at the time, quick and dirty and done was more important.

hansvm 6y ago

For arbitrary constraints it's problematic. Suppose you have a programming language capable of expressing a filter `(shuffle_result) => valid`. On average across all possible such functions you'll need at least `factorial(n_cards)` bits just to express the filters. Of course, many special cases you care about can be expressed much more simply. E.g. with the adjacent-suits example you can deterministically generate such decks pretty easily by appropriately composing uniform integer partition sampling, uniform combination sampling, and uniform permutation sampling. For a standard 52-card deck you can basically lay out suit#1, then suit#2, do a little finicky magic to make sure suit#3 is placed uniformly in such a way that a solution exists (at least one always will), and then fill the remaining slots with suit#4.