【每日一题20220824】排列

兴趣爱好交流 每日一题
1

:magic_wand: 给定非空的字符串，你需要进行排列，得到所有排列并删除重复项（如果存在）

例子：

* With input 'a'
* Your function should return: ['a']
* With input 'ab'
* Your function should return ['ab', 'ba']
* With input 'aabb'
* Your function should return ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

排列的顺序无关紧要。

题目难度：一般
题目来源：https://www.codewars.com/kata/5254ca2719453dcc0b00027d

def permutations(string: str) -> list:
    # your code here


assert sorted(permutations('a')) == ["a"]
assert sorted(permutations('ab')) == ["ab", "ba"]
assert sorted(permutations('aabb')) == ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
assert sorted(permutations('ababc')) == ['aabbc', 'aabcb', 'aacbb', 'ababc', 'abacb', 'abbac', 'abbca', 'abcab', 'abcba', 'acabb', 'acbab', 'acbba', 'baabc', 'baacb', 'babac', 'babca', 'bacab', 'bacba', 'bbaac', 'bbaca', 'bbcaa', 'bcaab', 'bcaba', 'bcbaa', 'caabb', 'cabab', 'cabba', 'cbaab', 'cbaba', 'cbbaa']
2 
def permutations(string: str) -> list:
    path = ''
    road = []
    if len(string) == 1:
        return list(string)

    def proad(string, path):
        if string == '':
            road.append(path)
        for i in range(len(string)):
            item = string[i]
            proad(string[:i] + string[i + 1:], path + item)

    proad(string, path)

    return list(set(road))


assert sorted(permutations('a')) == ["a"]
#print(permutations('ab'))
assert sorted(permutations('ab')) == ["ab", "ba"]
#print(permutations('aabb'))
assert sorted(permutations('aabb')) == ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
assert sorted(permutations('ababc')) == ['aabbc', 'aabcb', 'aacbb', 'ababc', 'abacb', 'abbac', 'abbca', 'abcab',
'abcba', 'acabb', 'acbab', 'acbba', 'baabc', 'baacb', 'babac', 'babca',
'bacab', 'bacba', 'bbaac', 'bbaca', 'bbcaa', 'bcaab', 'bcaba', 'bcbaa',
'caabb', 'cabab', 'cabba', 'cbaab', 'cbaba', 'cbbaa']
3 
def permutations(s):
    res = []
    s=''.join(sorted(s))
    def _inner(l1,tmp):
        if not l1:
            return res.append(''.join(tmp))
        for i in range(len(l1)):
            if i>=1 and l1[i] == l1[i-1]:
                continue
            _inner(l1[:i]+l1[i+1:],tmp + [l1[i]])
    tmp = []
    _inner(s,tmp)
    return res
4 
import itertools
def permutations(string: str) -> list:
    return sorted(list({''.join(i) for i in itertools.permutations(string, len(string))}))
5 
def permutations(string: str) -> list:
    res=[]
    path_list=[]
    s=''.join(sorted(string))
    def proa(str,path):
        if str=='':
            res.append(''.join(path))
        for i in range(len(str)):
            if i >=1 and str[i]==str[i-1]:
                continue
            proa(str[:i]+str[i+1:],path+[str[i]])

    proa(s,path_list)
    return res

assert sorted(permutations('a')) == ["a"]
assert sorted(permutations('ab')) == ["ab", "ba"]
assert sorted(permutations('aabb')) == ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
assert sorted(permutations('ababc')) == ['aabbc', 'aabcb', 'aacbb', 'ababc', 'abacb', 'abbac', 'abbca', 'abcab', 'abcba', 'acabb', 'acbab', 'acbba', 'baabc', 'baacb', 'babac', 'babca', 'bacab', 'bacba', 'bbaac', 'bbaca', 'bbcaa', 'bcaab', 'bcaba', 'bcbaa', 'caabb', 'cabab', 'cabba', 'cbaab', 'cbaba', 'cbbaa']