New answers tagged randomized-algorithms
3
Firstly, a frame challenge:
A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds
You don't need the algorithm to run in a few seconds. You need output in a few seconds. I don't see that there's anything stopping you from setting a brute force layout cruncher running on a computer in the ...
3
This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, independently of previous songs. According to the coupon collector problem, if you have $n$ songs in your list and want to hear all of them, you will have to wait for roughly $n\ln n$ songs to be played. By that ...
2
One possible solution to make this as simple as possible to quickly get a working algorithm would be as follows. The simplest layout is of course 12C (12 curved tracks all with the same orientation (relative to each other), and forming a simple circle. This will be the basis upon which we can build on.
So the basic algorithm will be to maintain the 360 ...
1
The approach is right, however, you are missing a little detail. Karger's algorithm runs on multigraphs. Hence, two vertices can have more than one edge between them and hence, the probability of contracting them the disjoint sum of the probability of contracting any of the edges between them which is the number of edges between them over the total number of ...
Top 50 recent answers are included
