约翰逊特罗特算法 [英] Johnson Trotter Algorithm

问题描述

概述：

我想实现约翰逊猪蹄算法在Java中，这样我就可以解决的项目欧拉的一个问题。我已经找了又找，但据我可以看到我有一切权利来实现，你知道错了，否则我就不会问这个问题:)

I am trying to implement the Johnson Trotter Algorithm in Java so that I can solve a problem on Project Euler. I have looked and looked but as far as I can see I have everything implemented right, which you know is wrong, otherwise I wouldn't be asking this question :)

基本算法是这样的：

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

我已经创建了一个元素对象具有属性（值，isMobile，方向）来使用这种算法。当我交换价值，只有一个交换发生，在那之后的原始顺序被打印一遍又一遍。

I have created an Element object that has attributes (value, isMobile, Direction) to use for this algorithm. When I am swapping values, only one swap occurs, then after that the original order is printed over and over.

code：

      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;
      }

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

Expectations: I would expect the algorithm to do something like this

启动：

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

等

实际

这是它实际上做

启动：

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

在第一个交换后，不改变

it doesnt change after the first swap

任何帮助将是真棒，此外，如果您有意见/我的风格指针，这些也将是非常美联社preciated，谢谢。

Any help would be awesome, also if you have comments/pointers about my style those would also be much appreciated, Thanks.

抱歉长的帖子。

推荐答案

虽然你没有发布完整的code在这里（你如何决定，如果一个元素是移动或静止的将是有益的），我怀疑你的错误出现从这里开始：

Although you are not posting the complete code here (how you decide if an element is mobile or immobile would be helpful), I suspect your error comes from here:

 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 方法的问题，但不能肯定。

Also, I suspect there are problems for your isMobile method, but cannot be sure.

希望这有助于！

这篇关于约翰逊特罗特算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！