简单趣味#159:中间排列

Question

任务

您将看到一个字符串s。s中的每个字母都会出现一次。

考虑通过重新排列s中的字母而形成的所有字符串。在按字典顺序对这些字符串进行排序后，返回中间项。(如果序列的长度为偶数n，则将其中间项定义为第(n/2)项。)

问题所在

嘿伙计们。我完全被困住了..。我有一个算法来计算O(n)中的答案。所有基本测试都通过了。但是我经常失败所有的测试，其中字符串的长度等于23,24,25。一些可怕的事情发生了，总是这样：

“‘noabcdefgijklymzustvpxwrq”应等于“nmzyxwvutsrqpolkjigfedcba”

“‘lzyxvutsrqonmeijhkcafdgb”应等于“lzyxvutsrqonmkjihgfedcba”

我的意思是，它的方向是正确的，但突然出错了。给我一个提示，我应该检查什么或修复什么。非常感谢!

附注:这个execute middlePermutation in under 12000ms给了我解决问题的想法

代码

import math

def middle_permutation(string):
    ans, tmp = '', sorted(list(string))
    dividend = math.factorial(len(tmp)) / 2
    for i in range(len(tmp)):
        perms = math.factorial(len(tmp)) / len(tmp)
        if len(tmp) == 1:
            ans += tmp[0]
            break
        letter = tmp[math.ceil(dividend / perms) - 1]
        ans += letter
        tmp.remove(letter)
        dividend -= perms * (math.floor(dividend / perms))
    print(len(string))
    return ans

以下是一些基本输入

Test.describe("Basic tests")
Test.assert_equals(middle_permutation("abc"),"bac")
Test.assert_equals(middle_permutation("abcd"),"bdca")
Test.assert_equals(middle_permutation("abcdx"),"cbxda")
Test.assert_equals(middle_permutation("abcdxg"),"cxgdba")
Test.assert_equals(middle_permutation("abcdxgz"),"dczxgba")

Answer 1

你离一个好答案不远了。

由于索引为0和1，因此您应该从

dividend = math.factorial(len(tmp)) // 2 - 1

然后选择一个稍偏的字母，将您的代码替换为

letter = tmp[dividend // perms]

另外，因为这里的一切都是整数，所以最好使用'a // b‘而不是math.floor(a / b)。

总而言之，这是你的代码的一个修正版本：

def middle_permutation(string): 
    ans, tmp = '', sorted(list(string)) 
    dividend = math.factorial(len(tmp)) // 2 - 1 
    for i in range(len(tmp)): 
        perms = math.factorial(len(tmp)) // len(tmp) 
        if len(tmp) == 1: 
            ans += tmp[0] 
            break 
        letter = tmp[dividend // perms] 
        ans += letter 
        tmp.remove(letter) 
        dividend -= perms * (dividend // perms) 
    return ans

为了美观起见，我们来概括一下：

def n_in_base(n, base): 
    r = [] 
    for b in base: 
        r.append(n % b) 
        n //= b 
    return reversed(r)

def nth_permutation(s, n):
    digits = n_in_base(n, range(1, len(s)+1))
    alphabet = sorted(s)
    return ''.join(alphabet.pop(ri) for ri in digits)

def middle_permutation(s):
    return nth_permutation(s, math.factorial(len(s)) // 2 - 1)