通过重复循环3个元素来查找排列 [英] Find permutations by repeatedly cycling 3 elements

问题描述

是否有一种算法可以找到遵循此规则的一系列唯一元素的所有可能排列?

Is there an algorithm to find all possible permutations of a series of unique elements, that follows this rule?

从给定的排列中，必须通过循环3个元素来找到下一个排列.它们可以是任何三个元素.

From a given permutation the next permutation must be found by cycling exactly 3 elements. They can be any three elements.

使用这样的3个循环，只会找到所有排列的子集，但是 应该找到所有可能通过3个周期到达的序列，并且在找到所有可实现的序列之前，不应两次重复发现相同的序列.

With such 3-cycles only a subset of all permutations will be found, but all those that are possible to be reached via 3-cycles should be found, and the same permutation should not be found twice until all reachable permutations have been found.

以下是示例输入:

1,2,3,4,5

输出可能是:

3,1,2,4,5
2,3,1,4,5
4,2,1,3,5
3,4,1,2,5
1,3,4,2,5
4,1,3,2,5
2,4,3,1,5

...等等

以下我尝试产生这种序列的众多算法之一(对于数组 a 和长度 n ):

One of the many algorithms I have tried to produce such a sequence is the following (for array a and length n):

print (a)
for i = 0 to n-1
    for j = i+1 to n-1
        for l = j+2 to n-1 
            for k = j+1 to l 
                cycle a[i],a[j],a[k]
                print (a)
                cycle a[i],a[j],a[k]
                print (a)

这将产生上面打印的系列，然后继续:

This produces the series printed above, but then continues with:

1,2,3,4,5

..这是已经输出的排列.到目前为止，我尝试过的其他任何查找下一个3个周期的算法都未能找到所有 reachable 排列.

.. which is a permutation that was already output. Any other algorithm of finding the next 3-cycle I have tried so far failed to find all reachable permutations.

推荐答案

有这篇旧论文

There is this old paper V. L. Kompel'makher and V. A. Liskovets. Sequential generation of arrangements by a basis of transpositions., which shows that you can generate all permutations by means of simple transpositions and each of this transpositions must swap the first element of the permutation with any of other (so called star shaped basis). For example for S(3) that would be, as the first element (opposed to element 1) is swapped in every step.

123->213->312->132->231->321->[123, Hamiltonian cycle!]

还有一种类似的方法排列，它不在付费墙后面.本文的一个重要见解是，即使必须在每个换位元素1中进行交换，仍然可以生成所有置换而无需重复(元素1在每个步骤中都被交换):

There is also a similar approach A `Hot Potato' Gray Code for Permutations which is not behind a pay wall. An important insight of this paper is, that even if in every transposition element 1 must be swapped, still all permutations can be generated without repetition (element 1 is swapped in every step):

123->213->231->132->312->321->[123, Hamiltonian cycle!]

Knuths的计算机程序设计的艺术"一章生成所有排列"中的另一种算法是通过星形基础遍历所有排列.该算法称为埃里希交换方法".我不要求了解那里发生了什么，这只是算法到Java的翻译.对您来说最有趣的部分是该行:

Another algorithm for cycling through all permutations for the star shaped basis is this one from Knuths "The Art of computer programming", Chapter "Generating all permutations". Algorithm is called "Ehrlich's swap method". I don't claim to understand what is going on there, it is only a translation of the algorithm into java. The most interesting part for you is that line here:

    //swap values to get next permutation:
    swap(per,0,b[k]);

在每个步骤中都有一个换位，并且在每个换位中元素[0]都被交换(->星状).

In every step there is a transposition and in every transposition the element[0] is swapped (->star shaped basis).

import java.util.Arrays;

public class EhrlichPermuter {
    //Follows Knuths "The Art of computer programming", Chapter "Generating all permutations",  "Ehrlich's swap method".
    int n;
    int[] c;
    int[] b;
    int[] per;

    boolean done;

    void initialize(){
        c=new int[n];
        b=new int[n];
        per=new int[n];
        for(int j=0;j<n;j++){
            b[j]=j;
            per[j]=j;
        }
    }

    EhrlichPermuter(int n){
        this.n=n;
        initialize();
    }

    void swap(int[] a, int i, int j){
        int h=a[i];a[i]=a[j];a[j]=h;
    }

    int[] getNextPermut(){
        int[] result=Arrays.copyOf(per, per.length);//remember permutation

        int k=1;
        while(c[k]>=k){
            c[k]=0;
            k++;
            if(k==n){
                done=true;
                initialize();//we got all permutations so far
                return result;//return the last permutation
            }
        }
        c[k]=c[k]+1;

        //swap values to get next permutation:
        swap(per,0,b[k]);

        //flip:
        int j=1; k--;
        while(j<k){
            swap(b,j,k);
            j++;
            k--;
        }

        return result;//return remembered permutation
    }
}

现在辛苦了！

最后一步是:形式(1a)(1b)的任何两个连续换位都可以写为3个元素的循环(1ab).因此，您将跳过带有负奇偶校验的排列.对于热土豆，外观如下

The last step is: Any two consecutive transpositions of the form (1 a)(1 b) can be written as a 3-element cycle (1 a b). Thus you would just jump over permutation with negative parity. For Hot-Potato this looks as follows

123 --(213)-->231--(132)-->312--(321)-->[123, Hamiltonian cycle!]

跳过了()中的排列.

这篇关于通过重复循环3个元素来查找排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！