Binary Algorithm

[dopamine]

EDIT:

 

I just realized, let me try and simplify this...I need to create a function as follows:

 

function getCombinations($numBits, $numTrue){
    //perform magic to return array of all combinations of $numTrue of binary number of length $numBits
}

 

-------------------------------------------------------------------------------------------------------------

 

 

 

Hi All,

 

This is more of a logic question than anything, but since I am trying to figure it out in PHP I thought this would be as good a place as any.

 

I am trying to come up with a way to do the following:

 

 

1. I am given a pseudo-random integer value that may range from say....20 to 60.

 

2. This pseudo-random number represents how many bits will be in a somewhat random binary number.

 

3. One combination of bits of that length will solve my problem but I don't know which combination it is.

 

4. Here is the most important point:  I know there will always be substantially fewer 1's in the binary number  (Lets guess 3-10 out of whatever the length of the binary number is)

 

 

So in the interest of time, I need to find this number as fast as possible.

 

I am trying to pull something out of my brain from college, as far as what type of known algorithm would perform this operation.  Let me give you an example using 4 bits.

 

 

Step 0 ---------all combinations with 0 bits true  (Don't need this step, but here for consistency)

0000

 

Step 1 ---------all combinations with 1 bit true

1000

0100

0010

0001

 

Step 2 ---------all combinations with 2 bits true

1100

1010

1001

0110

0101

0011

 

 

Step 3 ---------all combinations with 3 bits true (Probably wouldn't get here since we have reached > 50% bits true)

1110

1101

1011

0111

 

Step 4 ---------all combinations with 4 bits true (Probably wouldn't get here since we have reached > 50% bits true)

1111

 

 

 

So if you can imagine a potentially 60 bit value, to iterate one-by-one from start to the finish would take far too long.  Because of this, I have to leverage the fact that I know there are always substantially fewer 1's than 0's

 

I imagine because the length of the binary string varies, that I will want a recursive function....I just can't seem to pull it out of my head!!!! 

 

 

Does this sound like a familiar algorithm to anyone?  I have been in the mean time studying binary operators to see if I can find something there.

 

 

 

 

 

 

 

 

[Psycho]

So, basically, you need to know how many bits in the value are true, correct?

[dopamine]

No, I need to generate all the possible number of bits could potentially be true.

 

Given a length of a binary number, and a said number of bits are true.

 

 

So if length of binary number = 10, and if I want all combinations where 3 bits are true.

 

I hope that makes sense, I know, it's a weird question.

 

EDIT:

----------------------------------------------------

 

Actually, it looks like I just want a combination function.....hmmm still pondering.

[Psycho]

Ah ok, I had already created a solution for my first interpretation. I really can't think of a solution other than to create a loop. Let me see what I can come up with.

[dopamine]

Thank you

 

I am trying several types of permutation and combination functions right now, but am not yet finding what I am after.

[gizmola]

This is what you are looking for:  http://en.wikipedia.org/wiki/Combinatorial_number_system

 

You can use "Combinadics" to help you. 

 

There is an article about solving this problem but unfortunately it's c# code, but at least the problem and solution is layed out with code:  http://msdn.microsoft.com/en-us/library/aa289166%28v=vs.71%29.aspx

 

You'd have to port it.

 

[dopamine]

I found my answer here finally!

 

http://cogo.wordpress.com/2008/01/08/string-permutation-in-php/

 

I totally forgot what the difference between permutations and combinations was...

 

So in this case, I could use his code utilizing the array_unique example provided.

 

So if I permute the string 1100 I get:

 

Array
(
    [0] => 1100
    [2] => 1010
    [3] => 1001
    [5] => 0110
    [7] => 0101
    [10] => 0011
)

 

 

 

Thank you for taking your time to look into this!

 

 

Regards

[dopamine]

Hmmm, never mind

 

While this function does do what I want, it dies when I throw large binary strings at it due to memory usage by PHP.  I even upped it to 2 gigs in the ini, and still not happy.

 

Back to the drawing board!

 

 

[dopamine]

Well I suppose it would be impolite to keep this going.

 

I solved my problem, when I discovered the combination, even though it was >60 bits, only contained 2 trues.  So it didn't take as long after all.

 

 

Thanks again for all help.