I would appreciate the help of this great community in finding an algorithm (in any programming language, though I have it in Visual Basic) to solve two related problems:

• Counting permutations with repetition, where identical characters are not permuted among themselves, but with the restriction that no two identical characters are adjacent.

• Finding the inverse permutation: given a permutation number, return the corresponding permutation, respecting the same restriction of no adjacent identical characters.
  For example, given the string:

  THE STRING WILL HAVE THE SAME QUANTITY OF EACH CHARACTER.

  “00000000000000000000000000001111111111111111111111111111122222222222222222222222222222222222233333333333333333333333333333333”

Whith an algorithm, I would like to:

• Find the total number of permutations, where no identical characters are adjacent (e.g., no “00”, “11”, “22”, or “33”). When I say “permutations with repetition”, I mean that identical characters are not permuted among themselves.

• Find the inverse: given a permutation number and the base string, determine the corresponding permutation under the same restrictions (no adjacent identical characters).

I have the following Visual Basic code that already works for counting permutations with repetition (but without the restriction of no adjacent identical characters) and for finding the inverse (again, without the restriction):

Function PermToFreq(perm As String) As Dictionary(Of Char, Integer)
    Dim freq As New Dictionary(Of Char, Integer)()
    For Each x As Char In perm
        If freq.ContainsKey(x) Then
            freq(x) += 1
        Else
            freq(x) = 1
        End If
    Next
    Return freq
End Function

Function RankPerm(targetPerm As String) As BigInteger
    Dim freq As Dictionary(Of Char, Integer) = PermToFreq(targetPerm)
    Dim alphabet As List(Of Char) = freq.Keys.ToList()
    Dim rank As BigInteger = 0

    For i As Integer = 0 To targetPerm.Length - 1
        For Each x As Char In alphabet
            If freq(x) > 0 AndAlso x < targetPerm(i) Then
                freq(x) -= 1
                rank = BigInteger.Add(rank, Multichoose(freq))
                freq(x) += 1
            End If
        Next
        freq(targetPerm(i)) -= 1
    Next

    Return rank + 1 ' Add 1 because rank starts from 1, not 0
End Function

Function Multichoose(freq As Dictionary(Of Char, Integer)) As BigInteger
    Dim answer As BigInteger = 1
    Dim prevCount As Integer = 0

    For Each count As Integer In freq.Values
        For i As Integer = 1 To count
            answer = BigInteger.Multiply(answer, (i + prevCount))
            answer = BigInteger.Divide(answer, i)
        Next
        prevCount += count
    Next

    Return answer
End Function

Function UnrankPerm(perm As String, rank As BigInteger) As String
    Dim freq As Dictionary(Of Char, Integer) = PermToFreq(perm)
    Dim alphabet As List(Of Char) = freq.Keys.ToList()
    Dim answer As New List(Of Char)()

    For i As Integer = 0 To perm.Length - 1
        For Each x As Char In alphabet
            If freq(x) > 0 Then
                freq(x) -= 1
                Dim count As BigInteger = Multichoose(freq)
                If count < rank Then
                    rank -= count
                    freq(x) += 1
                Else
                    answer.Add(x)
                    Exit For
                End If
            End If
        Next
    Next

    Return New String(answer.ToArray())
End Function

Thank you for your time and any suggestions you can provide!