Python中具有固定前一个元素的排列 [英] permutations with fixed previous element in Python

问题描述

因此，我遇到了列表中固定的前一个元素发生置换的问题.所以，我有列表，它是从1到n的数字的有序序列.

So I encountered a problem of permutations with fixed previous element in list. So, I have list, which is an ordered sequence of numbers from 1 till n.

编辑

这是我的问题的改写: 你能想象树形图吗?因此，第1级-它是顶部(也称为父级)顶点.因此，如果我们有[1、2、3、4]这样的顶点，那么下一步就是进行排列，将所有数字插入位置 n ，这意味着在输出中我们将拥有:

here's a reformuliration of my question: Can you imagine a tree graph? So, 1st level - it's a top (also known as parent) vertex. So, if we have vertex like [1, 2, 3, 4], our next step would be to make permutations, inserting all numbers in the position n, it means that in output we would have this:

1.1 lvl [1, 2, 3, 4]

2.1 lvl [1, 2, 4, 3]

3.1 lvl [1, 3, 4, 2]

4.1 lvl [2, 3, 4, 1]

因此，我们看一下第1.1级，对第n-1个元素进行置换(4是固定的，不参与该级的置换).输出为:

So, then we look at level 1.1 and make permutations of n-1th element ( 4 is fixed and do not take part in permutation on this level). Output would be:

1.1.1 lvl [1, 2, 3, 4]

1.1.1 lvl [1, 2, 3, 4]

1.1.2 lvl [1, 3, 2, 4]

1.1.2 lvl [1, 3, 2, 4]

1.1.3 lvl [2, 3, 1, 4]

1.1.3 lvl [2, 3, 1, 4]

我们采用了1.1.1 lvl并修复了n-2元素(如您所见，没有必要修复第一个元素).因此，在此级别上，我们固定了3和4元素，分别是n-1和n个元素，输出是:

The we took 1.1.1 lvl and fix n-2 element (as you can see there is no point to fix 1st element). So, on this level we have fixed 3, and 4, which is n-1th and nth elemets, outut is:

1.1.1.1 lvl [1, 2, 3, 4]

1.1.1.1 lvl [1, 2, 3, 4]

1.1.1.2 lvl [2, 1, 3, 4]

1.1.1.2 lvl [2, 1, 3, 4]

我们在这里吃过饭了，但还没有结束.继续往上走(1.1.2级).并排列它.在这里，我们固定了第n-1个元素(它是2)和第n个元素(它是4)

We have dinished here, but do not have finish yet. Go on lvl up ( it's level 1.1.2). And permutate it. Here we have fixed n-1th element (it's 2) and nth (it's 4)

1.1.2.1 lvl [1, 3, 2, 4]

1.1.2.1 lvl [1, 3, 2, 4]

1.1.2.2 lvl [3, 1, 2, 4]

1.1.2.2 lvl [3, 1, 2, 4]

在这里完成.在上一级转到.此处固定了1和4.所以，

Finished here. GOTO on upper level. Here fixed 1 and 4. So,

1.1.3.1 lvl [2, 3, 1, 4]

1.1.3.1 lvl [2, 3, 1, 4]

1.1.3.2 lvl [3, 2, 1, 4]

1.1.3.2 lvl [3, 2, 1, 4]

我们已经完成了1.1级并转到2.1，我们在此重复相同的过程.

We have finished the level 1.1 and going to 2.1, where we repeat the same procedure.

所以，问题是:如何在python中做到这一点?

So, the question is: how to do this in python?

推荐答案

结果中的置换都通过交换两个元素而与前一个元素不同.

The permutations in your results all differ from the previous element by swapping two elements.

交换两个元素对应于排列六面体中的一条边.

Swapping two elements corresponds to an edge in a permutohedron.

这表明您正在尝试根据某些条件访问四面体中的顶点.您能用几何术语解释什么标准吗?

This suggests that you are trying to visit the vertices in the permutohedron according to some criteria. Can you explain what the criteria is in geometric terms?

例如，一个可能的问题是如何通过每转仅交换两个元素来生成所有可能的排列.这对应于在四面体上找到哈密顿路径.该问题的答案由 Steinhaus-Johnson- Trotter算法提供了一种O(n)方法，用于从给定位置查找下一个排列.

For example, one possible question is how to generate all possible permutations by swapping just two elements at each turn. This corresponds to finding a Hamiltonian path on the permutohedron. The answer to this question is given by the Steinhaus-Johnson-Trotter algorithm which gives an O(n) method for finding the next permutation from a given position.

编辑

以下是更新后的问题的一些Python代码:

Here is some Python code for the updated question:

def perms(A):
    if len(A)==1:
        yield A
    for i in xrange(len(A)-1,-1,-1):
        for B in perms(A[:i]+A[i+1:]):
            yield B+A[i:i+1]

运行

for a in perms([1,2,3,4]):
    print a

打印以下内容:

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

这篇关于Python中具有固定前一个元素的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！