Re: Binary Shuffling

On Nov 25, 7:15 pm, The Ghost In The Machine
<ew...@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
In sci.physics, DouglasEagleson
<eaglesondoug...@xxxxxxxxx>
wrote
on Sun, 25 Nov 2007 12:19:12 -0800 (PST)
<77b78e25-1f77-47e5-987d-2569daf5b...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>:





1 1 1 1 0 0 0 0

A four one word is given. It has also four zero's, making a binary
word. A shuffle will make all the permutations of all the
combinations. This particular combination being four 1's and four 0's.

My question how to shuffle the set?

How is a special shuffle constructed to shuffle all binary's!!!!

A special reference is needed, my thinking I guess. Because each
duplicate 1 or 0 is a combination word, not a permutation word.

ABCDOIUY to replace 11110000 makes a purmutation

One method is to use a pick-and-delete, a destructive
method that picks items and deletes them from the input,
while setting them in the output.

This can be implemented as follows (in C):

char inp[8] = {'1','1','1','1','0','0','0','0'};

int genshuffle( char out[8])
{
for(int i = 8; i > 1; i--)
{
int r = makerand(i);
out[i-1] = inp[r];
for(int j = r+1; j < i; j++)
inp[j-1] = inp[j];
}
out[0] = inp[0];
}

where makerand(n) generates a random integer from 0 to n-1;
the implementation thereof is left to the interested reader.

Various modifications are easily done, among them first
copying the input to the output, then picking the
desired bit in the output and swapping.

If you're more interested in enumerating all possible
shuffles into a list, one can count from 0 to 11110000
and select all numbers containing 4 bits. One easy
way to count the bits is this little hack:

int numbits(int n)
{
int c = 0;

while(n != 0)
{
n &= n-1;
c++;
}

return c;
}

This works because the last 1 bit in n is followed by all 0s,
and is replaced by a 0 bit followed by all 1s in the subtraction.
The AND then eliminates that last 1 bit.

--
#191, ewi...@xxxxxxxxxxxxx
Been there, done that, didn't get the T-shirt.

--
Posted via a free Usenet account fromhttp://www.teranews.com- Hide quoted text -

- Show quoted text -

The shuffle is a random style. It appears correct.
I would feel confident in its use in a deterministic fashion of the
distribution was selectable. As long as each number is hit once in a
shuffle cycle, say.

I will try them out thanks.

Binary shuffling is a hard thing form me to grasp sometimes. I will
also try to make one from a parity generator.

DOug
.

Relevant Pages

  • Re: Better use of random number genator bits?
    ... This on average is a total of about 2880 bits to shuffle a deck (of course ... Let's choose a random 32-bit unsigned integer and check if it is ... int i, j, n; ... randnum_UL = KISS; ...
    (sci.math)
  • Re: [C][OT] erroneous fprintf output
    ... If you want to do it by random selection use a standard shuffle ... > ahead so that the square roots of a consecutive pair will both get added ... > same pile could be quite interesting, ... void shuffle(int array, int size); ...
    (alt.comp.lang.learn.c-cpp)
  • shuffle loses/duplicates objects in LinkedList
    ... the shuffle() the LinkedList is totally mangled, ... I'm using the GCC java compiler - might be interesting to see what happens ... // Simple Class which just contains an int. ... public class Int implements Comparable ...
    (comp.lang.java.help)
  • Re: Binary Shuffling
    ... In sci.physics, Douglas Eagleson ... A shuffle will make all the permutations of all the ... duplicate 1 or 0 is a combination word, not a permutation word. ... int genshuffle(char out) ...
    (sci.physics)
  • Re: Implementaion of random.shuffle
    ... Shuffle the sequence x in place. ... this implies that most permutations of a long sequence ... If it were to turn out that your concerns were genuine that you might end up posting a patch to the issue tracker and possibly then involving the developers. ... Now you have to ask yourself whether your surmise is genuinely correct (in which case the documentation may contain a bug) or whether the documentation is indeed correct and you are in error. ...
    (comp.lang.python)