如何用Python获取字符串的可能排列？

Question

我想写一段Python代码，来获取一些字符字符串的可能排列组合。

我举两个例子来说明我想做的事情。

例子1：假设我有一个字符字符串，我写下了

my_list=['1','2','3','4']

我想得到的是从左边开始配对的3种可能的排列，也就是说

['1', '2', '3','4'], ['1', '3', '2', '4'], ['1', '4', '2', '3'] 

所以，第一个值 '1' 可以和 '2'、'3' 或 '4' 配对，然后剩下的配对是 '3'、'4' 或 '2'、'4' 或 '2'、'3'。

例子2：假设我有一个字符字符串，我写下了

my_list=['1','2','3','4','5','6']

我想得到的是从左边开始配对的15种可能的排列，也就是说

['1', '2', '3', '4', '5', '6'],
['1', '2', '3', '5', '4', '6'],
['1', '2', '3', '6', '4', '5'],
['1', '3', '2', '4', '5', '6'],
['1', '3', '2', '5', '4', '6'],
['1', '3', '2', '6', '4', '5'],
['1', '4', '2', '3', '5', '6'],
['1', '4', '2', '5', '3', '6'],
['1', '4', '2', '6', '3', '5'],
['1', '5', '2', '3', '4', '6'],
['1', '5', '2', '4', '3', '6'],
['1', '5', '2', '6', '3', '4'],
['1', '6', '2', '3', '4', '5'],
['1', '6', '2', '4', '3', '5'],
['1', '6', '2', '5', '3', '4']

这里我们也有和第一个例子一样的配对方式。

我还想获取更长字符串的可能排列（比如8个、10个字符等）。我想用Python，因为一个8个字符的字符串会有105种可能的排列，从左边开始配对。当然，我希望有一段代码可以处理任意长度的字符串。

第一个例子并不太难，但我在第二个例子上遇到了很多困难。对于第一个例子，我尝试使用字符对。我定义了一个列表my_list，然后为第一个配对再定义一个列表。接着，我从my_list中移除第一个配对，得到的字符串是将第一个配对和my_list剩下的部分连接起来。以下是第一个例子的代码：

my_list_a = ['1', '2', '3', '4']
my_list_b = ['2', '3', '4']

for i in range(1,len(my_list_b)+1):
    tmp_list=['2', '3', '4']
    c = [my_list_a[0],my_list_a[i]]
    tmp_list.remove(my_list_a[i])
    print(c+tmp_list)

我尝试将这段代码调整到第二个例子，但到目前为止还没有成功。我看到可以使用itertools来处理排列组合，但我没有成功用它来实现我的目的。

Answer 1

这里有一个算法可以帮助你完成任务：

def generate_permutations_left(input_list):
    permutations = [input_list.copy()]  # Include the original list

    for i in range(1, len(input_list) - 1):
        # Swap elements and save the list
        input_list[i], input_list[i + 1] = input_list[i + 1], input_list[i]
        permutations.append(input_list.copy())

        # Back to original order
        input_list[i], input_list[i + 1] = input_list[i + 1], input_list[i]

    return permutations

在每次循环中，它会把当前的元素和列表中的下一个元素交换位置，然后保存这个修改过的列表，最后再把原来的顺序恢复回来。

Answer 2

在作者的反馈后，我更新了我的回答，给出了正确的解决方案。

a = ['1','2','3','4','5','6']

def get_pairs(a, exc_val: int = None):

    if exc_val is not None:
        a = a[:exc_val] + a[exc_val+1:]

    if len(a) <=2:
        return [a]
    
    a0 = a.pop(0)
    t = [[a0, k] + b  for i, k in enumerate(a) for b in get_pairs(a,i)]
    return t

get_pairs(a)

Answer 3

简单的递归，使用仍然可用的值和已经构建的部分输出：

def pair(unpaired, paired=[]):
    if not unpaired:
        print(paired)
    for i in range(len(unpaired) - 1):
        first, *rest = unpaired
        pair(rest, paired + [first, rest.pop(i)])

pair(['1','2','3','4','5','6'])

输出（在线尝试这个!）：

['1', '2', '3', '4', '5', '6']
['1', '2', '3', '5', '4', '6']
['1', '2', '3', '6', '4', '5']
['1', '3', '2', '4', '5', '6']
['1', '3', '2', '5', '4', '6']
['1', '3', '2', '6', '4', '5']
['1', '4', '2', '3', '5', '6']
['1', '4', '2', '5', '3', '6']
['1', '4', '2', '6', '3', '5']
['1', '5', '2', '3', '4', '6']
['1', '5', '2', '4', '3', '6']
['1', '5', '2', '6', '3', '4']
['1', '6', '2', '3', '4', '5']
['1', '6', '2', '4', '3', '5']
['1', '6', '2', '5', '3', '4']