Men*_*cey 3 algorithm math permutation
初始值的第 n 个唯一的、视觉上唯一的排列（即使按字母顺序排序）是否可以通过算法获得？
\n如果我们有一个初始值，例如0101，唯一的排列将是0011、0110、1100、0101、1010、1001，通过算法，如果我输入数字3，我应该直接得到唯一的排列例如，1100，无需计算上述排列。直接生成它很重要，因为如果我们有一个初始值 0101011010101010110110010101010101010 并且我们想要获得唯一的排列 82873648234，如果我们生成所有以前的排列，将花费太多时间。有什么方法吗？我在这个论坛上搜索了多个类似的问题，但我无法获得这个具体案例的答案。我们需要直接处理独特的排列，而不生成以前的排列。
\n我尝试了几种代码选项。例如，这段代码不仅生成一次唯一的排列，而且重复它们并且不起作用。
\nPrivate Sub Button5_Click(sender As Object, e As EventArgs) Handles Button5.Click\n Dim str As String = "0011"\n Dim target As Integer = 4 ' La permutaci\xc3\xb3n que quieres generar\n Dim arr() As Char = str.ToCharArray()\n Array.Sort(arr)\n str = New String(arr)\n\n For i = 0 To 5\n Dim result As String = FactoradicPermutation(str, i)\n MsgBox(result)\n Next\n\n End Sub\n Function FactoradicPermutation(ByVal str As String, ByVal index As Integer) As String\n Dim factoradic() As Integer = ToFactoradic(index, str.Length)\n Dim chars As List(Of Char) = New List(Of Char)(str)\n Dim result As String = ""\n\n For Each i As Integer In factoradic\n result += chars(i)\n chars.RemoveAt(i)\n Next\n\n Return result\n End Function\n\n Function ToFactoradic(ByVal num As Integer, ByVal length As Integer) As Integer()\n Dim factoradic(length - 1) As Integer\n\n For i As Integer = 1 To length\n factoradic(length - i) = num Mod i\n num \\= i\n Next\n\n Return factoradic\n End Function\n这就是“只是数数”。我将用 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
在我们的示例中，我们得到17672631900. 0这就是 18和 19的排列数1。
现在，如果我们按顺序列出所有这些排列，在哪里可以找到“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))