通过反复循环3个元素来查找排列

Question

是否有算法可以找到一系列独特元素的所有可能排列,遵循此规则？

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

对于这样的3个循环,将仅找到所有排列的子集,但是应该找到可能通过3个循环到达的所有排列,并且在找到所有可到达的排列之前不应找到相同的排列两次.

这是一个示例输入:

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):

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)

这产生了上面印刷的系列,但接着继续:

1,2,3,4,5

..这是已经输出的排列.到目前为止我找到的任何其他寻找下一个3周期的算法都未能找到所有可达到的排列.

Answer 1

有这篇旧报纸VL Kompel'makher和VA Liskovets.通过换位顺序生成排列.,这表明您可以通过简单的换位生成所有排列,并且每个转置必须将排列的第一个元素与任何其他排列交换(所谓的星形基础).例如,对于S(3),因为第一个元素(与元素1相对)在每个步骤中交换.

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

还有一种类似的方法A"Hot Potato"灰色代码用于排列,它不在付费墙后面.本文的一个重要见解是,即使必须交换每个转置元素1,仍然可以生成所有排列而不重复(每一步都交换元素1):

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

循环通过星形基础的所有排列的另一种算法是来自Knuths的"计算机编程的艺术",章节"生成所有排列".算法被称为"Ehrlich交换方法".我没有声称要了解那里发生了什么,它只是将算法转换为java.最有趣的部分是这一行:

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

在每个步骤中都有一个转置,并且在每个转置中,元素[0]被交换( - >星形基础).

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).因此,您只需跳过具有负奇偶校验的排列.对于Hot-Potato,这看起来如下

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

排除()中的排列.