1

I'm trying to solve a specific Cutting stock problem. It all boils down to solving following task, atleast in my solution: I want to find all permutations of a vector of the length n filled with m ones. for example:

(11100) in this case: n=5 and m=3

solution:

11100 11010 11001 10110 10101 10011 01110 01101 01011 00111

I know how to calculate the number of possibilities, but do not know how to get the actual vectors in a smart and efficient way.

I'm working with Vb.Net and am not very experienced in programming. Is there maybe a .Net solution for the problem? If not I would be thankful for your help to develope a custom solution.

Thank you.

Nils
  • 11
  • 1
  • VB.Net is not an inherently math-focused language, so perhaps you could be more specific about the logic behind your problem. As far as logic goes, maybe [this previous question](http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set) could be of use to get you started in writing your code. – Justin Ryan Nov 16 '14 at 10:53
  • Also, there seems to be a good explanation of the logic [here](http://rosettacode.org/wiki/Combinations_with_repetitions). – Justin Ryan Nov 16 '14 at 11:02
  • Thanks Justin, that looks promising. I'm gonna have a closer look in the next couple of days. – Nils Nov 17 '14 at 18:31

1 Answers1

0

I have written a function for you that will do that.

Here is example output:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

Here is the code:

Option Strict On
Option Explicit On
Option Infer Off
Public Class Form1
    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim sb As New System.Text.StringBuilder
        For Each s As String In getPermutations(5, 3).ToArray
            sb.AppendLine(s)
        Next
        Clipboard.SetText(sb.ToString)
        MsgBox(sb.ToString)
    End Sub
    Public Iterator Function getPermutations(m As Integer, n As Integer) As IEnumerable(Of String)
        Dim highest As Integer = CInt(2 ^ m)
        For I As Integer = 0 To highest - 1
            Dim s As String = Convert.ToString(I, 2).PadLeft(m, "0"c)
            If oneCount(s) = n Then
                Yield s
            End If
        Next
    End Function
    Function oneCount(ref As String) As Integer
        Dim result As Integer = 0
        For Each ch As Char In ref
            If ch = "1" Then result += 1
        Next
        Return result
    End Function
    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        getPermutations(3, 1)
    End Sub
End Class
Paul Ishak
  • 1,093
  • 14
  • 19
  • Thank you so much! There were a lot of things I had to look up to understand every detail of your code. I have one question, would it be possibly better -performance wise- to calculate the "right" permutations in the first place and not creating all binaries and picking the ones I need? – Nils Nov 17 '14 at 18:13
  • I don't know to be honest. Maybe you can study the bit pattern and extrapolate a formula from that? I will admit that there seems to be a visible pattern concerning the bits when you look at the results in a sequential list. But determining that pattern will require a bit more work. – Paul Ishak Nov 17 '14 at 23:27