如何获取给定列表中所有可能的元素组合？

Question

所以基本上可以说我们有一个列表

['a','b','c','d']

输出必须是：

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
.....

等等

如果我知道不是什么，我就可以编写程序。列表中元素的个数 但列表是由用户给出的（考虑用户给出了唯一元素的列表）。

l = ['a', 'b', 'c', 'd']
for h in l: 
    for i in l:
        ll = [h+i+j+k for j in l for k in l if len([h,i,j,k])==len(set([h,i,j,k]))] 
        for m in ll:
            print(m)

这个程序给了我上面的输出。

如果我想要 3 个元素，我需要删除一个 for 循环，或者如果我想要 5 个元素，我需要添加一个 for 循环。 但程序必须考虑没有。运行时的elems并给出o/p 基本上是任何否的通用算法。元素。

我认为递归是方法，但不知道该怎么做。 也尝试不使用 itertools 的排列方法来完成

任何帮助将不胜感激。

Answer 1

递归版本：

def combinations(items):
    if len(items) <= 1:
        return [items]
    combs = []
    for i, item in enumerate(items):
        others = items.copy()
        others.pop(i)
        for sub_comb in combinations(others):
            whole = [item]
            whole.extend(sub_comb)
            combs.append(whole)
    return combs

elems = ['a', 'b', 'c', 'd']
all_combs = combinations(elems)
for comb in all_combs:
    print(''.join(comb))

它为 3 个元素输出 6 种组合，为 4 个元素输出 24 种组合，为 5 种输出 120 种组合，依此类推。

这是 n!（阶乘），它是 n 不同元素可以产生的 排列的确切数量。

Answer 2

你可以尝试使用 dfs:

def perms(string, current="", visited=None):
    if visited is None:
        visited = [False] * len(string)

    if len(current) == len(string):
        yield current
    else:
        for i in range(len(string)):
            if not visited[i]:
                visited[i] = True
                yield from perms(string, current + string[i], visited)
                visited[i] = False

请注意，这将返回一个生成器表达式，因此您可以输出如下内容：

for perm in perms("".join(["a", "b", "c", "d"])):
    print(perm)

Answer 3

@hedfol 作为生成器的解决方案：

def combinations(src,prefix=[]):
    if len(src) == 1:
        yield prefix+src
    else:
        for i,x in enumerate(src):
            for y in myperm(src[:i]+src[i+1:], prefix+[x]):
                yield y