约翰逊特罗特算法

Question

概述：

我正在尝试用 Java 实现 Johnson Trotter 算法，以便解决 项目上的问题欧拉。我看了又看，但据我所知，我已经正确实现了所有内容，你知道这是错误的，否则我不会问这个问题:)

基本算法是这样的：

Johnson Trotter(n)
//Input: A positive integer n
//Output: A list of all permutations(0..n)

initialize the first permutation with: <0, <1, <2
//(all elements pointing left)

while ( //there exists a mobile element ) 
     //find the largest mobile element K
     //swap K with the element it points toward
     //reverse the direction of all elements > K 
     //add the permutation to a list

我创建了一个 Element 对象，具有用于此算法的属性(value, isMobile, Direction)。当我交换值时，只发生一次交换，然后一遍又一遍地打印原始订单。

代码：

      public void generatePermutations(int n)
      {
         ArrayList<String> permutations = new ArrayList<String>();
         ArrayList<Element> elements    = new ArrayList<Element>();

         //Initialize the first permutation, 
         //all Elements are mobile and point LEFT
         for(int i = 0; i < n; i++)
         {
            elements.add(new Element(i, true, Direction.LEFT));
         }

         //add initial permutation to the list 
         permutations.add(combineElementsToString(elements));

         while(hasMobileElement(elements))
         {
            //find the largest mobile element
            int maxIndex  = getLargestMobileIndex(elements); 
            Element k     = elements.get(maxIndex);

            //Swap the largest Element with the Element it points to
            if(k.getDirection() == Direction.LEFT)
            {
               //get the index of the element to the left of k
               int leftIndex = (maxIndex - 1) >= 0 ? (maxIndex - 1) : maxIndex;

               Collections.swap(elements, maxIndex, leftIndex);
            }
            else
            {
            //get the index of the element to the right of k
            int rightIndex = 
                (maxIndex + 1) < elements.size() ? (maxIndex + 1) : maxIndex;

               Collections.swap(elements, maxIndex, rightIndex);
            }

            //reverse the direction of all elements larger than K
            for(Element e : elements)
            {
               //System.out.println(e);
               if(e.getValue() > k.getValue())
               {
              Direction opposite = Direction.opposite(e.getDirection());
                  e.setDirection(opposite);
               }
            }

            //add the new permutation to the list
            permutations.add(combineElementsToString(elements));

            if(STOP++ == 10) System.exit(0);
         }
      }

      //converts all the values of the Element 
      //objects then adds them to a String
      public String combineElementsToString(ArrayList<Element> elements)
      {
         String perm = "";

         for(Element e : elements)
         {
            perm += Integer.toString(e.getValue());
         }

         return perm;
      }

      //finds largest Mobile element and returns it's index
      public int getLargestMobileIndex(ArrayList<Element> elements)
      {
         int maxIndex = 0;

         for(int i = 0; i < elements.size(); i++)
         {
            if(elements.get(i).isMobile() && i > maxIndex)
            {
               maxIndex = i;
            }
         }

         return maxIndex;
      }

      //determines if there is a remaining mobile element
      public boolean hasMobileElement(ArrayList<Element> elements)
      {
         for(Element e : elements)
         {
            if(e.isMobile()) 
               return true;
         }

         return false;
      }

期望： 我希望算法做这样的事情

开始：

<0 <1 <2
<0 <2 <1
<2 <0 <1

等

实际

这就是它实际做的

开始：

<0 <1 <2
<0 <2 <1 
<0 <2 <1 
<0 <2 <1 

第一次交换后它不会改变

任何帮助都会很棒，如果你有评论/指针我的风格，这些也将不胜感激，谢谢。

抱歉发帖太长。

Answer 1

尽管您没有在这里发布完整的代码（如何确定元素是移动的还是不动的会有所帮助），但我怀疑您的错误来自这里：

 public int getLargestMobileIndex(ArrayList<Element> elements)
      {
         int maxIndex = 0;

         for(int i = 0; i < elements.size(); i++)
         {
            if(elements.get(i).isMobile() && i > maxIndex) //<---------- It seems that 
            // you should compare the i-th element to the maxIndex-th element, not i and
            // maxIndex
            {
               maxIndex = i;
            }
         }

         return maxIndex;
      }

因为算法说找到最大的移动元素K 。

另外，我怀疑您的 isMobile 方法存在问题，但无法确定。

希望这有帮助！

Answer 2

我查看了 Even 加速的建议链接，认为使用比较的效率不必要地低。我的理解是 Even 的加速意味着你不需要比较。

这是我的代码；这种迭代形式（与递归解决方案不同）允许您调用 getNext 迭代器来生成并返回下一个排列。

// Johnson-Trotter algorithm (http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm)
public class Permuter {
    private int[] perms;
    private int[] indexPerms;
    private int[] directions;
    private int[] iSwap;
    private int N; //permute 0..N-1
    private int movingPerm=N;

    static int FORWARD=+1;
    static int BACKWARD=-1;


    Permuter(int N) {
        this.N = N;
        perms =  new int[N];     // permutations
        indexPerms = new int[N];     // index to where each permutation value 0..N-1 is
        directions = new int[N];     // direction = forward(+1) or backward (-1)
        iSwap = new int[N]; //number of swaps we make for each integer at each level
        for (int i = 0; i < N; i++) {
            directions[i] = BACKWARD;
            perms[i]  = i;
            indexPerms[i] = i;
            iSwap[i] = i;
        }
        movingPerm = N;
    }

    int[] getNext() {
        //each call returns the next permutation
        do{
            if (movingPerm == N) {
                movingPerm--;
                return perms;
            } else if (iSwap[movingPerm] > 0) {
                //swap
                int swapPerm = perms[indexPerms[movingPerm] + directions[movingPerm]];
                perms[indexPerms[movingPerm]] = swapPerm;
                perms[indexPerms[movingPerm] + directions[movingPerm]] = movingPerm;
                indexPerms[swapPerm] = indexPerms[movingPerm];
                indexPerms[movingPerm] = indexPerms[movingPerm] + directions[movingPerm];
                iSwap[movingPerm]--;
                movingPerm=N;
            } else {
                iSwap[movingPerm] = movingPerm;
                directions[movingPerm] = -directions[movingPerm];
                movingPerm--;
            }
        } while (movingPerm > 0);
        return null;
    }

Answer 3

您甚至可以从 此处

Answer 4

的 java 代码

这是 Johson Trotter 算法公共类 PermutationGenerator
{

public void generatePermute(int N)
{
        ModifiedInteger[] permute=new ModifiedInteger[N];
        int noOfPermutation=0;
        for(int i=0;i<N;i++){
            permute[i]=new ModifiedInteger(i,i+1,true);
        }
        System.out.print(++noOfPermutation+" ");
        for(ModifiedInteger element:permute){
            System.out.print(element.value+",");
        }
        System.out.println();
        ModifiedInteger mobile;
        while((mobile=largestMobile(permute))!=null)
        {
            //System.out.println("Largest Mobile is val- "+mobile.value+" index is "+mobile.index);
            swap(mobile,permute);
            //System.out.println("After Swap Largest Mobile is val- "+mobile.value+" index is "+mobile.index);
            reverse(permute,mobile);
            System.out.print(++noOfPermutation+" ");
            for(ModifiedInteger element:permute){
                System.out.print(element.value+",");
            }
            System.out.println();
        }

}
public void reverse(ModifiedInteger[] sequence,ModifiedInteger largestMobile){  
    for(ModifiedInteger element:sequence){
        if(element.value>largestMobile.value){
            element.direction=!element.direction;

        }

    }
}
public void swap(ModifiedInteger largestMobileInteger,ModifiedInteger[] sequence)
{
    ModifiedInteger temp=largestMobileInteger;
    if(largestMobileInteger.direction){
        sequence[largestMobileInteger.index]=sequence[largestMobileInteger.index-1];
        sequence[largestMobileInteger.index-1]=temp;
        sequence[largestMobileInteger.index].index+=1;
        largestMobileInteger.index-=1;
    }
    else{
        sequence[largestMobileInteger.index]=sequence[largestMobileInteger.index+1];

        sequence[largestMobileInteger.index+1]=temp;
        sequence[largestMobileInteger.index].index-=1;
        largestMobileInteger.index+=1;
    }


}
public ModifiedInteger largestMobile(ModifiedInteger[] sequence){
    ModifiedInteger largestMobile=null;
    int count=0;
    for(ModifiedInteger element:sequence){
        if(element.direction&&count!=0&&element.value>sequence[count-1].value)
        {
            if(largestMobile==null){
                largestMobile=element;
            }
            else if(largestMobile.value<element.value){
                largestMobile=element;
            }

        }
        else if(!element.direction&&count<sequence.length-1&&element.value>sequence[count+1].value)
        {
            if(largestMobile==null){
                largestMobile=element;
            }
            else if(largestMobile.value<element.value){
                largestMobile=element;
            }

        }
        count++;
    }

    return largestMobile;



}
//boolean direction-left-true;right-false
public class ModifiedInteger
{
    int value;
    int index;
    private boolean direction;
    ModifiedInteger(int index,int value,boolean direction){
        this.index=index;
        this.value=value;
        this.direction=direction;
    }
    public boolean getDirection() {
        return direction;
    }
    public void setDirection(boolean direction) {
        this.direction = direction;
    }
}
public static void main(String args[]){

    PermutationGenerator obj=new PermutationGenerator();
    obj.generatePermute(5);
}

}