[RESOLVED] String Permutations

[DanielLH]

Hi,

I'm trying to create every permutation of 'injecting' spaces into a string.

For example...

An example input would be "ABC". Each permutation cannot start or end with a space, so there are 4 possible permutations... (i think ??)

"ABC"
"AB C"
"A BC"
"A B C"

I've tried something along the following, but not having much luck.

(pseudocode)

MinPerm = Len(strInput)
MaxPerm = Len(strInput) * 2 -1 (minus 1 prevents last character from having a suffixed space)

For Loop = MinPerm To MaxPerm
Binary = GetBinaryString(Loop)
For BinLoop = 1 to Len(Binary)
If Mid(Binary,BinLoop,1) = 0 Then
Output = Output & Mid(position in input string, followed by a space)
Else
Output = Output & Mid(position in input string WITH NO SPACE)
End If
Next

Print Output
Output = ""
Next

I nearly lost the will to live, trying to figure this out so any help would be really appreciated.

[jemidiah]

One way to make this IMO far more intuitive is to consider this algorithm: for each slot where a space *may* get put, write down a 1 if a space is included there or a 0 if it is not. Ex:

"ABC" = "00"
"AB C" = "01"


Using this method you can easily see that each permutation corresponds to a binary string of length StrLen - 1. There are then 2^(StrLen - 1) possible permutations, since there are 2^(StrLen - 1) distinct binary strings of length StrLen - 1. Here, this translates to 2^3-1 = 2² = 4 different permutations, as you have written.

You should be able to get the rest yourself. If you need help feel free to ask


Edit: Doh! I read your code after I posted, looks like you've already thought of this, more or less. Could you explain where the trouble you're having lies? From inspection I'm not sure if MinPerm and MaxPerm are getting initialized correctly, though your inner loop looks fine.

[Shaggy Hiker]

It looks like minPerm will be incorrect. If the input string is a single character, minperm will be 1 when it should be 0. Therefore, I believe you should be using len-1 for minPerm, and to be consistent, len-2 for maxPerm.

EDIT: On further thought, I'm not sure about maxPerm. If you use len-2, the loop will run 1 time for a single character string, because minPerm will be 0, and maxPerm will be 0. That may not be correct. There will be one string, but it will be the input string. This will be the case for all loops, but it seems to me that the case with no spaces is kind of special. The code in the loop will need to be able to handle that.

[Logophobic]

MinPerm will always be zero. MaxPerm will always be 2 ^ (Len(strInput) - 1) - 1
Another problem I see with the pseudocode is that GetBinaryString needs to return a string of appropriate length, including leading zeros. Also, the code never adds the final character to the output, which needs to be done after the BinLoop loop.

Here is working code. Instead of a binary string, I have simply used a bit flag with the loop variable to see if a particular bit is on or off. I have also used a buffer string instead of building the output with concatenation.

Private Sub InjectSpaces(strText As String)
  Dim lngPerm As Long
  Dim lngPermCount As Long
  Dim lngPos As Long
  Dim lngSpaces As Long
  Dim lngBit As Long
  Dim strBuffer As String
  
  strBuffer = strText & strText ' Make the buffer large enough
  lngPermCount = 2 ^ (Len(strText) - 1) ' Total number of permutations
  For lngPerm = 0 To lngPermCount - 1
    lngBit = 1 ' or: lngBit = lngPermCount \ 2
    lngSpaces = 0
    For lngPos = 1 To Len(strText) - 1
      Mid(strBuffer, lngPos + lngSpaces, 1) = Mid$(strText, lngPos, 1)
      If (lngPerm And lngBit) <> 0 Then
        lngSpaces = lngSpaces + 1
        Mid(strBuffer, lngPos + lngSpaces, 1) = " "
      End If
      lngBit = lngBit * 2 ' or: lngBit = lngBit \ 2
    Next lngPos
    Mid(strBuffer, lngPos + lngSpaces, 1) = Mid$(strText, lngPos, 1)
    Debug.Print Left$(strBuffer, lngPos + lngSpaces)
  Next lngPerm
End Sub

I may be stating the obvious here, but for the lngBit variable, you can use either the commented assignments or the uncommented assignments, but not one of each. The difference is the direction the spaces are injected (either from the left of the string, or from the right), which you can see in the output.

The following adaptation of the above code may be useful.

Private Function InjectRandomSpaces(strText As String) As String
  Dim lngPerm As Long
  Dim lngPermCount As Long
  Dim lngPos As Long
  Dim lngSpaces As Long
  Dim lngBit As Long
  Dim strBuffer As String
  
  strBuffer = strText & strText ' Make the buffer large enough
  lngPermCount = 2 ^ (Len(strText) - 1) ' Total number of permutations
  lngPerm = Int(Rnd * lngPermCount)
  lngBit = 1 ' or: lngBit = lngPermCount \ 2
  lngSpaces = 0
  For lngPos = 1 To Len(strText) - 1
    Mid(strBuffer, lngPos + lngSpaces, 1) = Mid$(strText, lngPos, 1)
    If (lngPerm And lngBit) <> 0 Then
      lngSpaces = lngSpaces + 1
      Mid(strBuffer, lngPos + lngSpaces, 1) = " "
    End If
    lngBit = lngBit * 2 ' or: lngBit = lngBit \ 2
  Next lngPos
  Mid(strBuffer, lngPos + lngSpaces, 1) = Mid$(strText, lngPos, 1)
  InjectRandomSpaces = Left$(strBuffer, lngPos + lngSpaces)
End Function

[DanielLH]

Many thanks for everyones help! Sanity restored!