Ho risolto con questa funzioncina ricorsiva:

Public Shared Sub Permuta(ByVal Radice As String, ByVal combi As Integer, ByRef Risultati As List(Of String), ByVal inputarray As String())
For Each voce As String In data_array
If Trim(Radice).Contains(Trim(voce)) Then
Continue For
End If

If combi <= 1 Then
Risultati.Add(Radice + " " + voce)
Else
Permuta(Radice + " " + voce, combi - 1, Risultati, inputarray )
End If
Next
End Sub

dove radice è una stringa che inizialmente è vuota, combi è il numero delle parole da permutare (lo limito a max 4 anche se le parole sono di più per non allungare i tempi di elaborazione, vuol dire che otterrò permutazioni composte da max 4 parole), Risultati è l'array delle permutazioni generate in output e inputarray è l'array delle parole che devono essere permutate.
Non so se matematicamente sia corretto, completo ed esaustivo ma a me pare faccia quello che mi serve per cui mi accontento :-)