[RESOLVED] [2005] Find All Binary Combinations...

[circuits2]

I have read all of the past posts but did not find any that were directly related to what I am trying to do here, save maybe one or two.

Start with 2 numbers, we'll say 15 and 23 for now but they will be variable in the actuall application. I want to find all combinations of a 23 bit binary word that have exactly 15 1's. I know from the code below that there are 170,544 of them. However, I was wondering if there is a better or more efficient way to do this than my attempt as shown. It takes approx. a minute and a half, which isn't too bad considering there are over 8,000,000 combinations.

Private Sub SuggestNewWorker_DoWork(ByVal sender As Object, ByVal e As System.ComponentModel.DoWorkEventArgs) Handles SuggestNewWorker.DoWork

	Try

		Dim fdrMax As Integer = 15
		Dim fdrInv As Integer = 23
		Dim combos As Integer = 0
		Dim binWord As String = “”
		Dim foundHighs As Integer = 0
		Dim starter As Int64 = 2 ^ (fdrMax – 1)
		Dim stopper As Int64 = 2 ^ (fdrInv – 1)
		Dim volume As Int64 = stopper – starter
		Dim progMark As Integer = CInt(stopper \ 100)
		Dim progCheck As Integer = 0
		Dim progRep As Integer = 0

		For runner As Int64 = starter To stopper Step 1
			For cnt As Integer = 1 To fdrInv
				If runner And (2 ^ (cnt – 1)) Then
					binWord = “1” & binWord
					foundHighs += 1
				Else
					binWord = “0” & binWord
				End If
			Next cnt

			If foundHighs = fdrMax Then
				combos += 1
			End If

			If progCheck = progMark Then
				progRep += 1
				Me.SuggestNewWorker.ReportProgress(progRep)
				progCheck = 0
			Else
				progCheck += 1
			End If

			binWord = “”
			foundHighs = 0
			Application.DoEvents()
		Next Runner

	Catch ex As Exception
		MessageBox.Show(ex.Message)
	End Try
End Sub

[18experience]

Just one idea, don't start at 1 everytime. The first number that will have the number of 1's you are looking for is 2^X (X beging 15 in this case). So, that cuts out all the number before 2^15. That isn't great, unless the number of 1's you are looking for happens to be fairly close to the max (23 in this case). However, this might get you thinking.

If 2^15 is this first, then 2^16 will have 15 combinations of numbers with 15 1's. That is this string, "111111111111111", with a single 1 from it replaces with a zero and a 1 tacked onto the beginning. Meaning:
"1" & "111111111111110"
"1" & "111111111111101"
"1" & "111111111111011"
"1" & "111111111110111"
"1" & "111111111101111"
"1" & "111111111011111"....

That should knock out half of your numbers, in this case. It is starting to look like this is going to be recursive.

[circuits2]

If you look at my code, you will see that I am already doing what you suggested. I.E. The first combination will be 00000000111111111111111 and the last combination will be 11111111111111100000000. I am also using recursion already. The question is not how to do it, but if you can do it faster than I already am. Thank you for the post though.

[benmartin101]

try this for checking the number of times 1's show up:

Private Function func1(ByVal str As String, ByVal val As Integer) As Boolean
        Dim x() As Char = str.ToCharArray
        Dim upper As String = val - 1
        Dim num As Integer
        For i As Integer = 0 To upper
            num = num + Convert.ToInt32((x(i).ToString()))
        Next
        If num = val Then
            Return True
        End If
        Return False
    End Function

str is the string of the bit combination (23 in your example), and val is the number of 1's (15 in your example)

edit: str is the "000000111", etc. Returns true if it has the correct number of 1's.

[18experience]

Oops, I guess I jumped the gun on that one. I didn't scroll down. Well, one thing that would speed it up is completely removing any use of a string. You may have to get creative, but it always faster to use integers and such when you can.

[circuits2]

I'm not exactly sure that would be any faster. I did notice, though, that you used Int32 instead of Int64. The number 23 is variable and could exceed the limit of Int32.

I think if I have to call a function from inside the routine, then it would actually take longer to process. Especially when the code is so brief.

[circuits2]

Oops, I guess I jumped the gun on that one. I didn't scroll down. Well, one thing that would speed it up is completely removing any use of a string. You may have to get creative, but it always faster to use integers and such when you can.

I removed the string from the code shown above and gained a little speed. Not significant though...

I think it may be as fast as I'm going to get.

[Shaggy Hiker]

What do you want to do with these things once you get them? You could calculate the number that exist fairly readily, but I assume you want to do something more with them.

A couple of suggestions:

1) Get rid of the 2^ stuff. A faster technique would be to use bit shifting, which is much quicker than multiplication:

'I don't know your runner and stopper stuff.
dim x as integer
dim n as integer = 1 'You'd need Int64, probably.
 
for x=0 to maxBitSize
 if ((n << x) AND runner)>0 Then 'Actually, I don't know if runner is the right variable.
  'It's a 1, add it.
  foundhighs+=1
 else
  'It's a 0
 end if
next

2) Don't use a string. You mentioned that you got rid of it. Did you do so completely? How did you build your bit string then? If you didn't, then at least you should be using a StringBuilder, because whenever you concatenate to a string, you don't simply add a character to the existing string. Instead, you allocate the memory for a new string that is the size of the old string plus one character, copy the existing string over to the new string, add the new character, and delete the old string. That's none too fast.

[benmartin101]

try this:

My last sample gave the answer in 50 seconds(on my machine), this one gave it to me in 10seconds.

Private Sub Combo(ByVal bit As Integer, ByVal x As Integer)
        Dim str As String = ""
        For i As Integer = 0 To x - 1
            str = str + "1"
        Next
        Dim power As Integer = bit
 
        Dim index As Integer = 0
        For i As Integer = 0 To (2 ^ power) - 1
            Dim bitcombo As String = Convert.ToString(i, 2)
            bitcombo = bitcombo.Replace("0", "")
            If bitcombo = str Then
                index = index + 1 'total number of times it appeared
            End If
        Next
       
    End Sub

bit is corresponds to 23 and x corresponds to 15

[Shaggy Hiker]

Oh yeah, I should mention that I expect that there is a much faster technique than this, which is why I asked what you wanted to do with the results.

In your example, you mentioned a 23 bit string with 15 bits set. Therefore, if you start with...oh heck, lets simplify it down to a 5 bit string with 3 set:

11100

Now, the next two would be to take the last bit, and shift it to the two open possibilities:

11010
11001

Two possibilities = Number total bits-number set bits.

Now, for each of these two, you can take the next bit, and move it to the two possibilities:

10110
10011

and

10101
10011

Now repeat this for the first bit. Thus you have 2 options for the first bit, 2 options for each of those for the second bit, and 2 options for each of those for the third bit. Since 2 is only Total - Set, you can calculate the number of options for all Total and Set.

However, getting all of them is a pain, as the number balloons rapidly as Total - Set gets bigger.

[Shaggy Hiker]

try this:

My last sample gave the answer in 50 seconds(on my machine), this one gave it to me in 10seconds.

Private Sub Combo(ByVal bit As Integer, ByVal x As Integer)
        Dim str As String = ""
        For i As Integer = 0 To x - 1
            str = str + "1"
        Next
        Dim power As Integer = bit
 
        Dim index As Integer = 0
        For i As Integer = 0 To (2 ^ power) - 1
            Dim bitcombo As String = Convert.ToString(i, 2)
            bitcombo = bitcombo.Replace("0", "")
            If bitcombo = str Then
                index = index + 1 'total number of times it appeared
            End If
        Next
       
    End Sub

bit is corresponds to 23 and x corresponds to 15

Nice, using the stringbuilder to create str should be slightly faster, and << in place of the ^ would be VERY slightly faster (it would only be evaluated once).

Wouldn't the length of the bitCombo remove the need for str entirely? After all, str is a bunch of 1's of length x.

[benmartin101]

Yes, your right about the str part. Instead of comparing the two strings, you just compare to make sure it's the proper length, and in that example, 15.

[circuits2]

Thank you both for your suggestions. The string portion is actually needed in later stages so I implemented your StringBuilder idea. I also converted my mathematical calculations to bit shifting, which I had not considered before and am glad you suggested it. All in all you have helped me reduce the processing time from about 90 seconds to approx. 23.

I noticed what seemed to be a fundamental flaw in my calculations and made a slight adjustment. The new version gives me a significantly different answer so I was wondering if either of you could verify my results. When searching for every combination of 15 in a 23 bit word, I now get a result of 490,314 combinations. Before I was getting 170,544.

Here is the current code:

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

     ' CLEAR LAST RESULTS
     Me.Label3.Text = ""

     Dim fdrMax As Integer = 15
     Dim fdrInv As Integer = 23
     Dim combos As Integer = 0
     Dim binWord As New StringBuilder(fdrInv)
     Dim foundHighs As Integer = 0

     ' SET BOUNDARIES
     Dim starter As Int64 = (1 << fdrMax) - 1
     Dim stopper As Int64 = (1 << fdrInv) - 1

     ' START MAIN LOOP
     For runner As Int64 = starter To stopper Step 1

          ' LOOP THROUGH VALUE AND VERIFY SET BITS
          For cnt As Integer = 1 To fdrInv
               If runner And (1 << (cnt - 1)) Then
                    binWord.Insert(0, "1")
                    foundHighs += 1
               Else
                    binWord.Insert(0, "0")
               End If
          Next cnt

          ' IF SET BITS = fdrMax THEN ADD TO COMBOS
          If foundHighs = fdrMax Then
               combos += 1
          End If

          ' RESET WORD AND HIGHS FOR NEXT LOOP
          binWord.Remove(0, fdrInv)
          foundHighs = 0

     Next runner

     Me.Label3.Text = combos & " combinations were found!"

End Sub

[18experience]

When searching for every combination of 15 in a 23 bit word, I now get a result of 490,314 combinations. Before I was getting 170,544.

The number of results is just Combination(23, 15). You can verify your results by solving that. It has to do with factorials and dividing by differences of factorials. It isn't very hard, if you can find the equation.

[circuits2]

Actually, you cannot use that method. Since I am counting in binary, then I am not considering ABC and CAB to be two different combinations. The factorial method, which I agree is quite simplistic, considers rearranged combinations to be different.

I.E.

ABC CAB BCA
Factorials would see this as 3 combinations
Binary sees all three as 1 single combination


Edit: Also, the equation you referred to is 23 x 22 x 21 x 20 .. etc until you have multiplied 15 numbers. It's called permutations.

[18experience]

ABC CAB BCA
Factorials would see this as 3 combinations
Binary sees all three as 1 single combination

You are speaking of permutations there. Order does not matter in combinations, it does matter in permutations.

Think of your problem as 23 spaces, and you have to pick 15 spaces. Thats a combination.

I am almost positive I am right, but either way, just look up both. Your answer is either C(23, 15) or P(23, 15). You can verify which is correct by using two small number like 2 and 6. Work it out by hand and see which equation gives you the correct result.

EDIT: I would look it up myself, but I can't now.

EDIT EDIT: If I remember correctly, P(x, y) is x!/y!. In this case, 23!/15!, or 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16 = 19769460480. This seems pretty big. I don't remember what C(x, y) is, but I do remember that calculating combinations requires calculating permutations.

[circuits2]

You are using C() and P() as though they are functions or methods. I see where they are available in C#, but have not been able to find them in VB. Can you shed any light on this?

[18experience]

Sorry, I wasn't meaning to imply that they are functions or methods in VB, because they are not. I guess I should have just reposted instead of editing twice, but it look above, that is the formula for a permutation.

All you need to do is create a Factorial function, which should be fun, provided you enjoy recursion. You can then use your Factorial function to create a Permutation function, and use that Permutation function to create a Combination function. All a combination uses are permutations, subtraction, and division.

[18experience]

Private Function Fac(ByVal Num As Long) As Long
        If Num <= 1 Then
            Return 1
        Else
            Return Num * Fac(Num - 1)
        End If
    End Function
 
    Private Function Per(ByVal X As Long, ByVal Y As Long) As Long
        Return Fac(X) / Fac(Y)
    End Function

There are factorial and permutation. Don't try Per(23, 15) though, it is causing an overflow. I don't know which datatype to use, but Integer and Long both cannot handle Per(23, 15).

EDIT: You might wanna check, too. I don't remember those formulas very well, but this at least shows you how to do this once you get the formulas that are correct.

[18experience]

EDIT: You might wanna check, too. I don't remember those formulas very well, but this at least shows you how to do this once you get the formulas that are correct.

For instance, I think Per should be:

Return Fac(X) / Fac(X - Y)

[circuits2]

I was able to locate the proper formula online:

Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k)

which was taken from this MSDN article:
http://msdn.microsoft.com/msdnmag/is...n/default.aspx

It confirms my last results of 490,314.


Thanks for the help!

[18experience]

No problem.

Here is a group of function that can do that.

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        MsgBox(Com(23, 15))
    End Sub
 
    Private Function Fac(ByVal Num As Decimal) As Decimal
        'Factorial
        If Num <= 1 Then
            Return 1
        Else
            Return Num * Fac(Num - 1)
        End If
    End Function
 
    Private Function Per(ByVal X As Decimal, ByVal Y As Decimal) As Decimal
        'Permutation
        Return Fac(X) / Fac(X - Y)
    End Function
 
    Private Function Com(ByVal X As Decimal, ByVal Y As Decimal) As Decimal
        'Combination
        Return Per(X, Y) / Fac(Y)
    End Function