约翰逊·特罗特算法
我试图在Java中实现Johnson
Trotter算法，以便解决Euler项目上的问题。我看了看，但据我所知，我已正确实现了所有内容，您知道这是错误的，否则我不会问这个问题:)
基本算法如下：
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
第一次交换后它没有改变
任何帮助都会很棒，如果您对我的风格有意见/建议，也将不胜感激，谢谢。
抱歉，很长的帖子。
回答：
尽管您没有在此处发布完整的代码（如何确定元素是可移动还是不可移动是很有帮助的），但我怀疑您的错误来自此处：
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;
}
自算法说find the largest mobile element K。
另外，我怀疑您的isMobile方法有问题，但不能确定。
希望这可以帮助！
以上是 约翰逊·特罗特算法 的全部内容， 来源链接： utcz.com/qa/407531.html
