Issue with repetition in Permute function

Question

I am running a Permute function but I am having issue getting the same results like this, how can I prevent this from happening?

red|red|white
white|red|red

Public buffer As New List(Of String)
Public Sub Permute(ByVal Root As String, ByVal Depth As Integer, ByVal Buffer1 As List(Of String))
    Dim data_array As String() = {"red", "blue", "white"}
    For Each myStr As String In data_array
        If Depth <= 1 Then
            Buffer1.Add(Root & myStr)
        Else
            Permute(Root & myStr & ",", Depth - 1, Buffer1)
        End If
    Next
End Sub

score 1 · Accepted Answer · edited May 23 '17 at 10:27

Bjørn-Roger Kringsjå did the heavy lifting for this in converting some C++ code to VB in this great answer.

The original works to permute string characters. I modified it to work with strings (something I have been meaning to do) and allows you to specify the separator. You could just return a List(Of String()) or similar and use String.Join from the calling code.

Public NotInheritable Class Permutation

    Public Shared Function Create(array As String(), sep As String) As List(Of String)
        Return Permutation.Create(array, False, sep)
    End Function

    Public Shared Function Create(array As String(), sort As Boolean,
                                  sep As String) As List(Of String)
        If (array Is Nothing) Then
            Throw New ArgumentNullException("array")
        ElseIf ((array.Length < 0) OrElse (array.Length > 13)) Then
            Throw New ArgumentOutOfRangeException("array")
        End If
        Dim list As New List(Of String)
        Dim n As Integer = array.Length
        Permutation.Permute(list, array, 0, array.Length, sep)
        If (sort) Then
            list.Sort()
        End If
        Return list
    End Function

    Private Shared Sub Permute(list As List(Of String), array As String(),
                               start As Int32, ndx As Int32, sep As String)
        Permutation.Print(list, array, ndx, sep)
        If (start < ndx) Then
            Dim i, j As Integer
            For i = (ndx - 2) To start Step -1
                For j = (i + 1) To (ndx - 1)
                    Permutation.Swap(array, i, j)
                    Permutation.Permute(list, array, (i + 1), ndx, sep)
                Next
                Permutation.RotateLeft(array, i, ndx)
            Next
        End If
    End Sub

    Private Shared Sub Print(list As List(Of String), array As String(),
                             size As Int32, sep As String)
        Dim tmp As New List(Of String)
        If (array.Length <> 0) Then
            For i As Integer = 0 To (size - 1)
                tmp.Add(array(i))
            Next
            list.Add(String.Join(sep, tmp))
        End If
    End Sub

    Private Shared Sub Swap(array As String(), i As Int32, j As Int32)
        Dim tmp As String
        tmp = array(i)
        array(i) = array(j)
        array(j) = tmp
    End Sub

    Private Shared Sub RotateLeft(array As String(), start As Int32, n As Int32)
        Dim tmp As String = array(start)
        For i As Integer = start To (n - 2)
            array(i) = array(i + 1)
        Next
        array(n - 1) = tmp
    End Sub
End Class

Note: my mods will coexist fine with Mr Kringsjå's original code as overloads. Usage:

Dim data = {"red", "blue", "white"}

Dim combos = Permutation.Create(data, ", ")

Results:

red, blue, white
red, white, blue
blue, red, white
blue, white, red
white, red, blue
white, blue, red

score 0 · Answer 2 · answered May 18 '16 at 03:05

What you are doing is selecting one of { "red", "blue", "white" } Depth times. So if you called Permute("", 5, buffer) you would get the following:

red,red,red,red,red 
red,red,red,red,blue 
...
white,white,white,white,blue 
white,white,white,white,white

That 3 to the power of 5 selections.

If you want to just get all the possible permutations of { "red", "blue", "white" } then do this:

Public Function Permute(ByVal data As IEnumerable(Of String)) As IEnumerable(Of String)
    If data.Skip(1).Any() Then
        Return data.SelectMany( _
            Function (x) Permute(data.Except({ x })).Select( _
                Function (y) x & "," & y))
    Else
        Return data
    End If
End Function

...and call it like this:

Dim results = Permute({ "red", "blue", "white" })

The results I get are:

red,blue,white 
red,white,blue 
blue,red,white 
blue,white,red 
white,red,blue 
white,blue,red

It would be trivial then to prepend the Root value to these results.

Issue with repetition in Permute function

2 Answers2