-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjohnsonTrotterMain.cpp
More file actions
150 lines (122 loc) · 4.5 KB
/
johnsonTrotterMain.cpp
File metadata and controls
150 lines (122 loc) · 4.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include "johnsonTrotterHeader.h"
#include <string>
#include <cstring>
#include <array>
#include <iostream>
using namespace std;
void printPermutations(string word, int permutations ) {
// Input: word can be any string of characters, presorted in lexiographic order;
// permutations is an integer number of permutations that you would like to compute
int wordLength = word.length();
char wordArray[wordLength-1];
int directionArray[wordLength-1]; // 0: Left, 1: Right
int mobilePosition;
char currentMobileElementValue;
strcpy(wordArray, word.c_str());
for(int i = 0; i < wordLength; i++) {
directionArray[i] = 0;
}
for(int k = 0; k < permutations; k++) {
printPermutationRow(word, wordArray);
mobilePosition = mobileElementFinder(word, wordArray, directionArray);
if(mobilePosition != -1) {
NULL;
} else {
break;
}
currentMobileElementValue = wordArray[mobilePosition];
swapValues(mobilePosition, directionArray, wordArray);
changeDirection(currentMobileElementValue, word, wordArray, directionArray);
}
}
void changeDirection(char currentMobileElementValue, string word, char wordArray[], int directionArray[]) {
for(int i = 0; i < word.length(); i++) {
if(wordArray[i] > currentMobileElementValue) {
if(directionArray[i] == 0) {
directionArray[i] = 1;
} else if (directionArray[i] == 1) {
directionArray[i] = 0;
}
}
}
}
int mobileElementFinder(string word, char wordArray[], int directionArray[]) {
int mobilePosition = -1; // Establishing base value
for(int i = 0; i < word.length() - 1; i++) {
for(int j = i+1; j < word.length(); j++) {
if(wordArray[i] > wordArray[j]) {
if((i == 0 && directionArray[i] == 0) || (i == (word.length()-1) && directionArray[i] == 1)) {
continue;
}
// If i is facing left:
if(directionArray[i] == 0) {
if(i != 0 && (wordArray[i] > wordArray[i-1])) {
if(mobilePosition == -1 || wordArray[mobilePosition] < wordArray[i]) { // If the previous mobile element is the default value, or a smaller element, then change
mobilePosition = i;
}
}
}
// If i is facing right:
else if(directionArray[i] == 1) {
if(i != (word.length()- 1) && (wordArray[i] > wordArray[i+1])) {
if(mobilePosition == -1 || wordArray[mobilePosition] < wordArray[i]) {
mobilePosition = i;
}
}
}
}
else {
if((j == 0 && directionArray[j] == 0) || (j == (word.length()-1) && directionArray[j] == 1)) {
continue;
}
// If j is facing left:
if(directionArray[j] == 0) {
if(j != 0 && (wordArray[j] > wordArray[j-1])) {
if(mobilePosition == -1 || wordArray[mobilePosition] < wordArray[j]) {
mobilePosition = j;
}
}
}
// If j is facing right:
if(directionArray[j] == 1) {
if(j != (word.length()-1) && (wordArray[j] > wordArray[j+1])) {
if(mobilePosition == -1 || wordArray[mobilePosition] < wordArray[j]) {
mobilePosition = j;
}
}
}
}
}
}
return mobilePosition;
}
void swapValues(int mobilePosition, int directionArray[], char wordArray[]) {
char tempCharacter;
char tempDirection;
if(directionArray[mobilePosition] == 0) {
tempCharacter = wordArray[mobilePosition-1];
tempDirection = directionArray[mobilePosition - 1];
wordArray[mobilePosition-1] = wordArray[mobilePosition];
directionArray[mobilePosition-1] = directionArray[mobilePosition];
wordArray[mobilePosition] = tempCharacter;
directionArray[mobilePosition] = tempDirection;
}
else if(directionArray[mobilePosition] == 1) {
tempCharacter = wordArray[mobilePosition + 1];
tempDirection = directionArray[mobilePosition + 1];
wordArray[mobilePosition + 1] = wordArray[mobilePosition];
directionArray[mobilePosition + 1] = directionArray[mobilePosition];
wordArray[mobilePosition] = tempCharacter;
directionArray[mobilePosition] = tempDirection;
}
}
void printPermutationRow(string word, char wordArray[]) {
for(int i = 0; i < word.length(); i++) {
cout << wordArray[i];
}
cout << endl;
}
int main(int argc, char**argv) {
printPermutations("StringGoesHere", 1); // Words must be tested that are already in lexiographic order
return 0;
}