Алгоритм Джонсона Троттера
Обзор:
Я пытаюсь реализовать алгоритм Джонсона Троттера в Java, чтобы решить проблему с Project 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
не меняется после первого обмена
Любая помощь будет отличной, даже если у вас есть комментарии / указания по поводу моего стиля, это также будет высоко оценено, спасибо.
Извините за длинный пост.
4 ответа
Решение
Хотя вы не публикуете здесь полный код (как вы решите, является ли элемент мобильным или неподвижным, было бы полезно), я подозреваю, что ваша ошибка происходит здесь:
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 метод, но не может быть уверен.
Надеюсь это поможет!
Я посмотрел на предложенную ссылку с ускорением 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;
}
Вот код Java для алгоритма Джонсона Троттера
открытый класс 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);
}
}
Вы даже можете загрузить полный исходный код Java для этого, с ускорением Even отсюда