Python's random.shuffle
uses the Fisher-Yates shuffle, which runs in O(n) time and is proven to be a perfect shuffle (assuming a good random number generator).
It iterates the array from the last to the first entry, switching each entry with an entry at a random index below it.
The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result...
The modern... solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n), compared to O(n2) for the naive implementation. This change gives the following algorithm (for a zero-based array).
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
I'm basing this off of the Algorithms section of the paper, which is kind of hard to understand, so I would appreciate someone else checking this. Also, I hope you're doing this for fun and not planning on using this for real cryptography without thorough analysis by professionals and academics,
The public Boolean function (13) is a series of clauses ANDed together, x -> ^ c_j(x)
. Each clause is a series of subclauses ORed together, x -> V(...)
. And each subclause is an element of the input x_[I(i, j)]
XORed with some sign s(i, j)
.
The signs come from a matrix of Booleans and are chosen randomly as 1 or 0, which is pretty straightforward, but picking the elements out of the input is trickier. The input is a vector of Booleans, and we want a random way to choose which one to put in each subclause. So, we make a matrix of integers size m, k
and call it I
. For each row in this matrix, c_j(x)
has to be true for the private key (since they will be ANDed together). So, generate a row of random integers (from 1
to n
so we don't go out of bounds of the input) and a row of random signs. Each of these should be k
items, since they will be rows of their matrices.
Once we've come up with candidate rows, we need to make sure they satisfy the private key. So, for each index in the row, we derive a subclause for the function c_j
and make sure at least one is true (since they will be ORed together). For example, the first elements might be 5 and 1, so we XOR the 5th element of the private key with 1 and see if it is true. Continue down the rows until at least one is true, and if it is, add the rows to your matrices.
Thinking in the other direction, if you have the matrices I
and s
, you can check a candidate key pretty easily. For each row of the matrices, make sure that with the integer from I
indexing the key, you get a value that can be XORed with the Boolean from s
.
Let's take the rows [1, 3, 2]
and [1, 0, 0]
, and a candidate key [1, 1, 0]
. First, take the first element from the key (1
) and XOR it with 1
. This gives you 0
, so continue on. Take the third element from the key (0
) and XOR it with 0
. This gives 0
, so keep going. Finally, we XOR the second element (1
) and the third sign (0
) to get 1
. Since we got a 1
, these rows work with this key.
Best Answer
Start with a grid of 1x1 cells. Pick a random spot, merge cells a random amount or till it collides with a larger rectangle.
This will get you something similar to the image you provide.
There's a bigger issues if you don't want a number of smaller cells acting as padding between your bigger cells. A comic book for example, wants to minimize the amount of dead space and have at most ~9 cells. You could pick some points and draw some lines and call those your cells.
There are plenty more way to skin a cat.