能否通过算法获得初始值的第 n 个唯一的、视觉上唯一的排列（即使按字母顺序排序）？
如果我们有一个初始值，例如0101，唯一的排列将是0011、0110、1100、0101、1010、1001，通过算法，如果我输入数字3，我应该得到唯一的排列例如，直接 1100，无需计算上述排列。直接生成它很重要，因为如果我们有一个初始值 0101011010101010110110010101010101010 并且我们想要获得唯一的排列 82873648234，如果我们生成所有以前的排列，将花费太多时间。有什么方法吗？我在这个论坛上搜索了多个类似的问题，但我无法获得这个具体案例的答案。我们需要直接处理独特的排列，而不生成以前的排列。
我尝试了几种代码选项。例如，这段代码不仅生成一次唯一的排列，而且重复它们并且不起作用。
Private Sub Button5_Click(sender As Object, e As EventArgs) Handles Button5.Click
Dim str As String = "0011"
Dim target As Integer = 4 ' La permutación que quieres generar
Dim arr() As Char = str.ToCharArray()
Array.Sort(arr)
str = New String(arr)
For i = 0 To 5
Dim result As String = FactoradicPermutation(str, i)
MsgBox(result)
Next
End Sub
Function FactoradicPermutation(ByVal str As String, ByVal index As Integer) As String
Dim factoradic() As Integer = ToFactoradic(index, str.Length)
Dim chars As List(Of Char) = New List(Of Char)(str)
Dim result As String = ""
For Each i As Integer In factoradic
result += chars(i)
chars.RemoveAt(i)
Next
Return result
End Function
Function ToFactoradic(ByVal num As Integer, ByVal length As Integer) As Integer()
Dim factoradic(length - 1) As Integer
For i As Integer = 1 To length
factoradic(length - i) = num Mod i
num \= i
Next
Return factoradic
End Function
这就是“只是数数”。我将用 Python 对其进行编码，并且我将使用您的更长的示例
perm = '0101011010101010110110010101010101010'
我们有一些符号集，并且我们有每个符号出现的次数。让我们得到频率分布。 （所有代码均采用 Python 编写。）
def perm_to_freq (perm):
freq = {}
for x in perm:
freq[x] = freq.get(x, 0) + 1
return freq
对于这个例子，我们得到
freq{'0': 18, '1': 19}我们有多少种排列？这就是多项式系数。在这种情况下，它将是
factorial(18+19)/factorial(18)/factorial(19)def multichoose (freq):
answer = 1
prev_count = 0
for count in freq.values():
# This will be 1, 2, ..., count
for i in range(1, count+1):
answer = answer * (i + prev_count) // i
prev_count += count
return answer
在我们的示例中，我们得到
1767263190001现在，如果我们按顺序列出所有这些排列，在哪里可以找到“0101011010101010110110010101010101010”？为了回答这个问题，我们需要计算它之前有多少个排列。逻辑是，每次我们看到下一项时，我们都需要计算在它有一个更小的项之前有多少种排列。所以计数是这样开始的：
First term '0'.
Nothing came before it.
{'0': 17, '1': 19} left.
Second term '1'.
multichoose({'0': 16, '1': 19}) = 4059928950 had a leading 0 came before it.
{'0': 17, '1': 18} left.
Third term '0'.
Nothing more came before it.
{'0': 16, '1': 18} left.
Fourth term '1'.
multichoose({'0': 15, '1': 18}) = 1855967520 more had a 0 before it.
{'0': 16, '1': 17} left.
等等。然后我们只需添加
0 + 4059928950 + 0 + 1855967520 ...这是代码。
def rank_perm (perm):
freq = perm_to_freq(perm)
alphabet = sorted(freq.keys())
answer = 0
for x in perm:
# Look at all that could come before x
for y in alphabet:
if x == y:
# We reached x so stop counting.
break
elif 0 < freq[y]:
# Count everything with a y here.
freq[y] -= 1
answer += multichoose(freq)
freq[y] += 1
freq[x] -= 1
return answer
在我们的示例中，它给出了
5558234991现在要找到哪个排列具有哪个等级，我们只需反转该过程即可。
def unrank_perm (perm, rank):
freq = perm_to_freq(perm)
alphabet = sorted(freq.keys())
answer = []
for i in range(len(perm)):
for x in alphabet:
if 0 < freq[x]:
# How many have x here?
freq[x] -= 1
count = multichoose(freq)
if count < rank:
# Count them, then put x back in.
rank -= count
freq[x] += 1
else:
answer.append(x)
break # Found this one.
return ''.join(answer) # Turn it into a string.
您可以像这样找到前几个排列：
perm = '0101011010101010110110010101010101010'
for i in range(30):
print(unrank_perm(perm, i))
如果我们按照已有的排列查找排列，我们应该得到原始的排列：
rank = rank_perm(perm)
print(perm == unrank_perm(perm, rank))