使用 itertools 在 python 中列出（仅移动 2 项，排列）

Question

我的第一门编程语言是 C++，我刚刚接触 python，我正在寻找一种从列表中切换数字的方法，在 C++ 中，这将使用指针通过循环移动它们来完成，但是这次我需要在 Python

中生成列表 A 到列表 B 的所有排列

列表 A（起始列表）和列表 B（结果列表）

A= 1234
B= 4231

程序必须按顺序显示所有可能的组合，同时只移动 2 个数字，直到 A 列表变成 B 列表（以下示例简化为 4 个数字，可能不会显示所有组合)

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

为了完成这个，我找到了 itertools 模块，它包含很多功能，但到目前为止还没有实现很多功能，下面的代码可以满足它的需要但是它不会成对或按顺序移动数字

import itertools

from itertools import product, permutations
A = ([1,2,3,4])  
B = ([4,2,3,1])  

print "\n"
print (list(permutations(sorted(B),4)))

我正在考虑添加一段时间 ( A != B ) 然后停止排列，我已经尝试过这个但是我不熟悉 pythons 语法，任何关于我如何完成这个的帮助将不胜感激

Answer 1

我假设输入列表的排序并不是真正需要的，

from itertools import permutations
A = ([4, 3, 2, 1])
B = ([1,2,4, 3])

def print_combinations(start, target):
    # use list(permutations(sorted(start), len(start))) if sorting of start is really required
    all_perms = list(permutations(start, len(start)))
    if tuple(target) not in all_perms:
        # return empty list if target is not found in all permutations
        return []
    # return all combinations till target(inclusive)
    # using list slicing
    temp = all_perms[: all_perms.index(tuple(target)) + 1]
    return temp


print print_combinations(A, B)

Answer 2

不是很清楚你在问什么。我认为您正在寻求一种 pythonic 方式来交换列表中的两个元素。在 Python 中，通常将数据结构分为不可变和可变。在这种情况下，您可以谈论元组或列表。

假设您要交换元素 i 和 j，其中 j 更大。

对于不可变元组，pythonic 方法将通过像这样的切片生成一个新的元组：

next = (current[:i] + current[j:j+1] + current[i+1:j]
                    + current[i:i+1] + current[j+1:])

对于可变列表，虽然它在 Python:

中更漂亮，但它会像 C++ 一样做很多事情

list[i],list[j] = list[j],list[i]

或者，您可能会询问如何解决排列问题，在这种情况下，答案是 itertools 并没有真正提供太多帮助。我会建议深度优先搜索。

Answer 3

假设您问的是解决这个排列问题的最佳方法 - 这里有一个不同的答案：

将所有排列视为一个集合。 itertools.permutations 按某种顺序生成所有这些排列。如果您想找到所有或部分排列，这正是您想要的。但这不是你要找的。您正试图通过这些排列找到 paths。 itertools.permutations 以和顺序生成所有排列，但不一定是您想要的顺序。当然不是所有订单：它只生成一次。

因此，您可以生成所有排列并将它们视为网络的节点。然后你可以 link 节点，只要它们通过一次交换连接，就可以得到一个图。这称为置换面体。然后您可以对该图进行搜索以找到您感兴趣的从 a 到 b 的所有无循环路径。这当然是可能的，但并不是真正的最佳选择。提前构建整个图是一个不必要的步骤，因为它可以很容易地按需生成。

这里有一些 Python 代码可以做到这一点：它通过在需要时为节点生成邻居来生成对排列面体的深度优先搜索。不过它不使用 itertools。

a = (1,2,3,4)
b = (4,2,3,1)

def children(current):
    for i in range(len(a)-1):
        yield (current[:i] + (current[i+1],current[i]) +
                   current[i+2:])

def dfs(current,path,path_as_set):
    path.append(current)
    path_as_set.add(current)
    if current == b:
        yield path
    else:
        for next_perm in children(current):
            if next_perm in path_as_set:
                continue
            for path in dfs(next_perm,path,path_as_set):
                yield path
    path.pop()
    path_as_set.remove(current)

for path in dfs(a,[],set()):
    print(path)

如果你真的对使用itertools.permutations感兴趣，那么你要研究的对象其实是：

itertools.permutations(itertools.permutations(a))

这会生成通过排列集的所有可能路径。您可以通过拒绝任何不是从 a 开始并且包含不是单一交换的步骤来解决这个问题。但这是一个非常糟糕的方法：这个列表很长。

Answer 4

我想下面是一种更简单的方法，我在列表中遇到了几乎相同的问题（想要交换的号码）（将列表的副本附加到自身列表 = 列表 + 列表然后运行 :

from itertools import combinations_with_replacement
mylist = ['a', 'b']    
list(set(combinations_with_replacement(mylist + mylist, r=2)))

结果： [('a', 'b'), ('b', 'a'), ('b', 'b'), ('a', 'a')]

使用 itertools 在 python 中列出（仅移动 2 项，排列）

Lists in python using itertools (moving only 2 items, permutations)

python

list

permutation