3 ms·
> I suppose the remaining cards could relatively easily be repurposed as RNG for nonce generation I spent better part of a hour trying to google this to no ava
by zokier 9y ago
> I suppose the remaining cards could relatively easily be repurposed as RNG for nonce generation
I spent better part of a hour trying to google this to no avail. How do you convert random permutation of n items into random number <n! ? Intuitively it feels like it should be possible, if not even easy, but I can't figure it out.
edit: yay, finally found a lead: "rank of a permutation" and "lehmer code". So I guess it is doable, have to check how they would actually work in application
- e12e 9y ago[ed: no, that's not right. With two cards, you can have red-back or black-red. I guess that'd translate to N bits for 2 n cards, but it's not quite trivial... For four, we have: rrbb, rbrb, rbbr, bbrr, brbr, brrb etc] I think I'm misunderstanding you - but say you have 2n cards, n red, n black. If you shuffle them, you have 2n random bits, read from first to last? (this is assuming it's feasible to actually randomly shuffle cards).
- HelloNurse 9y agoNo, in this application cards are all distinct, not merely half red and half black. There are n! permutation of a deck of n cards, and a uniformly chosen random permutation contains entropy equal to the base 2 logarithm of n!. Both choosing a random permutation given a supply of random bits and, as noted in the parent post, extracting random bits from a given random permutation are nontrivial computational problems leading to interesting algorithms; shuffling cards or tiles is a good practical shortcut to obtain a random permutation more directly.
- e12e 9y agoIndeed. I was attempting to induct from basic principles - as in two distinct cards.. But gp's right - it's not trivial. Unsure if it's simple :)
- KMag 9y agoYou'll want to basically perform the reverse of a Fisher-Yates shuffle. Instead of generating a random number, you look at which card needs to be swapped with the Kth card in the deck to make the top K to N positions of the deck in sorted order. If deck is a list holding a permutation of the numbers 0 to N - 1, it looks something like: random_value = 0 for i in range(len(deck)-1, 0, -1): index = deck.index(i) random_value += index random_value *= i deck[index], deck[i] = deck[i], deck[index] The above is a one-minute prototype and may or may not work. When I get some time, I'll actually test the above code, but it's close to doing the right thing. The above naive implementation is O(N^2). Your end result is a sorted deck, and random_value is a number that when repeatedly mod'd and divided by the appropriate index to generate a "random" number during a Fisher-Yates shuffle would produce your original permutation. In practice, you'd implement the algorithm in O(N) by first doing a single linear scan to build an index (actually just held in an array) of cards to their positions. Also, you wouldn't actually perform the swap, since you never look at deck[i] after performing the swap. You just do deck[index] = deck[i]. So, at the end, you won't wind up with deck being sorted.