Алгоритм джонсона троттера java

Алгоритм Джонсона Троттера

Я пытаюсь реализовать алгоритм Джонсона Троттера на Java, чтобы решить проблему в Project Euler. Я смотрел и смотрел, но насколько я вижу, у меня все реализовано правильно, что, как вы знаете, неправильно, иначе я бы не задавал этот вопрос 🙂

Базовый алгоритм выглядит так:

Johnson Trotter(n) //Input: A positive integer n //Output: A list of all permutations(0..n) initialize the first permutation with: K //add the permutation to a list 

Я создал объект Element с атрибутами (value, isMobile, Direction) для использования в этом алгоритме. Когда я меняю местами значения, происходит только один обмен, а затем снова и снова печатается исходный порядок.

 public void generatePermutations(int n) < ArrayListpermutations = new ArrayList(); ArrayList elements = new ArrayList(); //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 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 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 elements) < for(Element e : elements) < if(e.isMobile()) return true; >return false; > 

Ожидания: Я ожидал, что алгоритм сделает что-то вроде этого

Фактический

Это то, что он на самом деле делает

Не меняется после первого свопа

Любая помощь была бы замечательной, также, если у вас есть комментарии / указатели о моем стиле, они также были бы очень признательны, спасибо.

Источник

Алгоритм Джонсона Троттера

Обзор: Я пытаюсь реализовать алгоритм Johnson Trotter Algorithm в Java, чтобы я мог решить проблему Project Euler. Я посмотрел и посмотрел, но, насколько я вижу, у меня все реализовано правильно, что, по вашему мнению, неверно, иначе я не стал бы задавать этот вопрос:) Основной алгоритм выглядит следующим образом:

Johnson Trotter(n) //Input: A positive integer n //Output: A list of all permutations(0..n) initialize the first permutation with: K //add the permutation to a list 

Я создал объект Element , который имеет атрибуты (value, isMobile, Direction) для использования для этого алгоритма. Когда я меняю значения, происходит только одна свопа, после чего исходный порядок печатается снова и снова. Код:

 public void generatePermutations(int n) < ArrayListpermutations = new ArrayList(); ArrayList elements = new ArrayList(); //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 elements) < String perm = ""; for(Element e : elements) < perm += Integer.toString(e.getValue()); >return perm; > //finds largest Mobile element and returns it index public int getLargestMobileIndex(ArrayList 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 elements) < for(Element e : elements) < if(e.isMobile()) return true; >return false; > 

он не меняется после первого свопа Любая помощь будет потрясающей, также, если у вас есть комментарии/указатели на мой стиль, они также будут высоко оценены, спасибо. Извините за длинный пост.

Источник

Алгоритм Джонсона Троттера

Я пытаюсь реализовать алгоритм Джонсона Троттера в Java, чтобы решить проблему с Project Euler. Я посмотрел и посмотрел, но, насколько я вижу, у меня все реализовано правильно, что, как вы знаете, неправильно, иначе я бы не задавал этот вопрос:)

Основной алгоритм выглядит так:

Johnson Trotter(n) //Input: A positive integer n //Output: A list of all permutations(0..n) initialize the first permutation with: K //add the permutation to a list 

Я создал Element объект с атрибутами (value, isMobile, Direction) использовать для этого алгоритма. Когда я меняю значения, происходит только один обмен, после чего исходный порядок печатается снова и снова.

 public void generatePermutations(int n) < ArrayListpermutations = new ArrayList(); ArrayList elements = new ArrayList(); //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 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 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 elements) < for(Element e : elements) < if(e.isMobile()) return true; >return false; > 

Ожидания: я ожидаю, что алгоритм сделает что-то вроде этого

фактический

Это то, что он на самом деле делает

не меняется после первого обмена

Любая помощь будет отличной, даже если у вас есть комментарии / указания по поводу моего стиля, это также будет высоко оценено, спасибо.

Источник

Участник:ZeRoGerc

Алгоритм Джонсона-Троттера(англ. Johnson-Trotter algorithm) — алгоритм генерации всех перестановок из [math]n[/math] элементов. Причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.

Идея

Сопоставим каждому элементу перестановки [math]p[i][/math] направление [math]d[i][/math] . Будем указывать направление при помощи стрелок ← («влево») или →(«вправо»). Назовём элемент подвижным, если по направлению стрелки стоит элемент меньше его. Например, для [math] p = \,\;d = \<[/math] ←, →, ←, →, ← [math]\>[/math] , подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. Изначально [math] p = \,\;d = \<[/math] ←, . ,← [math]\>[/math] .

Пример работы алгоритма для n = 3

Псевдокод

 //Элементы нумеруются начиная с 1 p = d = while (true)< print(); // печатаем текущую перестановку // индекс наибольшего подвижного элемента for i = (1 .. n)< if (p[i] - подвижный) and ((id = -1) or (p[i] > p[id])) > if (id = -1) break // не нашли подвижного элемента for i = (1 .. n)< if (p[i] > p[id]) reverse(d[i]) // меняем направление стрелки > swap(id) //меняем элемент p[id], d[id] c элементом по направлению стелки >

Доказательство корректности

Очевидно, что требование о том, что каждая генерируемая перестановка отличается от предыдущей транспозицией двух соседних элементов выполнено исходя из самого алгоритма. Осталось доказать, что таким образом мы сгенерируем все перестановки.

Будем использовать обозначения:

• [math](a,[/math] ← [math])[/math] [math] — [/math] элемент с заданным направлением(компонента).
• [math]P[i][/math] [math] — [/math] перестановка с номером [math]i[/math] .
• [math]P[i]\backslash\\;[/math] [math] — [/math] перестановка с номером [math]i[/math] без элемента [math]a[/math] .

Число [math]n[/math] в перестановке не является подвижным элементом тогда и только тогда, когда первая компонента перестановки есть [math](n,[/math] ← [math])[/math] или последняя компонента есть [math](n,[/math] → [math])[/math] .

Если в перестановке [math]P[i][/math] есть подвижный элемент [math]a \neq n[/math] , то также определены перестановки [math]P[i + 1] . P[i + n][/math] . Причём, [math]P[i + 1]\backslash\ = P[i + 2]\backslash\ = . = P[i + n]\backslash\[/math] .

Теперь докажем основную лемму.

Алгоритм Джонсона-Троттера строит все перестановки из [math]n[/math] элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.

Доказывать будем по индукции. Для [math]n = 1\; — [/math] очевидно. Предположим, что для [math]n — 1[/math] алгоритм строит перестановки корректно. Докажем, что алгоритм будет корректно строить перестановки и для [math]n[/math] элементов. Разобьём все [math]n![/math] перестановок на блоки по [math]n[/math] (подряд). В силу вышедоказанной леммы в каждом блоке [math]P[i]\backslash\ = P[i + 1]\backslash\ = . = P[i + n]\backslash\[/math] , если [math]i\; — [/math] начало группы. Значит, в каждой группе какая-то перестановка из [math]n — 1[/math] элемента дополняется до перестановки из [math]n[/math] всеми возможными способами. Теперь докажем, что на переход между блоками элемент [math]n[/math] никак не влияет. Заметим, что при переходе между блоками [math]n[/math] является неподвижным элементом. В силу нашего утверждения [math]n[/math] стоит либо на первой, либо на последней позиции. Так как [math]n[/math] больше любого элемента, то никакой подвижный элемент не может указывать на [math]n[/math] . В силу этих фактов [math]n[/math] никак не повлияет на переход между блоками. Из этого можно сделать вывод, что при переходе между блоками перестановки строятся так же, как и перестановки из [math]n — 1[/math] элемента, а каждая такая перестановка дополняется до перестановки из [math]n[/math] элементов всеми возможными способами.

Асимптотика

Поговорим об асиптотике. Снова разобьём наши перестановки на блоки по [math]n[/math] элементов. Немного модифицируем алгоритм. Заметим, что в каждом блоке нам нужно искать максимальный элемент только один раз. В остальных случаях этим элементом будет [math]n[/math] . Следовательно, менять направление стрелок нужно тоже только один раз(в остальных случаях менять направления не нужно, так как [math]n[/math] — подвижный элемент, а менять направление стрелок нужно только у бóльших элементов). Следовательно, блок выполняется за [math]O(n) + O(n) + O(n) = O(n)[/math] . Всего блоков [math] -\:(n — 1)![/math] . Общая асимптотика [math]O(n) * (n — 1)! = O(n!)[/math] .

Сравнение с рекурсивным алгоритмом

Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из [math]n — 1[/math] элемента), а только текущую. Следовательно, этот алгоритм потребляет только [math]O(n)[/math] памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее. Это можно строго доказать, но доказательство довольно громозодкое и приводить его мы здесь не будем.

Источник