简单的乐趣#159：中间排列

Question

任务

给您一个字符串s。s中的每个字母出现一次

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

问题

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

“noabcdefgijklymzustvpxwrq”应等于“nmzyxwvutsrqpolkjigfedcba”

“LZYXVutsrqonmeihkCafdgb”应等于“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)