Next

Morph 2 U.S. states into 2 other states
• the problem
• all combinations of X things taken Y at a time
• comparing strings
• design 1
• implementation 1
• design 2
• implementation 2
• design 3
• implementation 3
•

# "all combinations"

### The formula for "all combinations of X things taken Y at a time" is ... ```X * (X - 1) * (X - 2) ... [Y terms worth] / Y ! ``` Consider:  all combinations of 6 things taken 3 at a time ```6 * 5 * 4 / 3 ! = 6 * 5 * 4 / 3 * 2 * 1 = 20 ``` How can we produce all these combinations?

#### Here is the first 2/6 of a possible combinations implementation: 3 nested loops. In the output below, most of the combinations have repeated digits ('x') or are duplicates ('d'). Notice that the first legal combinations in each group are: 123, and 234. How can we fix this approach to only yield "legal" combinations?

```int main() {
int array[] = { 1, 2, 3, 4, 5, 6 };
for (int i=0; i < 2; ++i) {
for (int j=0; j < 6; ++j) {
for (int k=0; k < 6; ++k)
cout << array[i] << array[j] << array[k] << ' ';
cout << '\n';
}
cout << '\n';
}
}

//  x   x   x   x   x   x        x   x   d   d   d   d
// 111 112 113 114 115 116      211 212 213 214 215 216
//  x   x                        x   x   x   x   x   x
// 121 122 123 124 125 126      221 222 223 224 225 226
//  x   d   x                    d   x   x
// 131 132 133 134 135 136      231 232 233 234 235 236
//  x   d   d   x                d   x   d   x
// 141 142 143 144 145 146      241 242 243 244 245 246
//  x   d   d   d   x            d   x   d   d   x
// 151 152 153 154 155 156      251 252 253 254 255 256
//  x   d   d   d   d   x        d   x   d   d   d   x
// 161 162 163 164 165 166      261 262 263 264 265 266
```

### How about adapting the inner loops to not "visit territory" already visited by outer loops ("j = i + 1" and "k = j + 1"), and instrumenting the outer loops to not duplicate work reserved for inner loops ("i < 4" and "j < 5")?

```int main() {
int array[] = { 1, 2, 3, 4, 5, 6 };
for (int i=0; i < 4; ++i) {
for (int j=i+1; j < 5; ++j)
for (int k=j+1; k < 6; ++k)
cout << array[i] << array[j] << array[k] << ' ';
cout << '\n';
}
}

// 123 124 125 126 134 135 136 145 146 156
// 234 235 236 245 246 256
// 345 346 356
// 456
// 6 * 5 * 4  /  3 * 2 * 1  =  20
```

# Combinations

```int main() {
int count = 0;
for (int i=0; i < 49; ++i)
for (int j=i+1; j < 50; ++j)
count++;
cout << "total combinations is " << count << '\n';
}

// total combinations is 1225
// 50 * 49  /  2 * 1
```

# Comparing

### Here is a small demonstration of sorting strings ...

```int main() {
string array[] = { "red", "dare", "dear", "deer", "read", "road", "dread" };
string sorted;
for (int i=0; i < 7; ++i) {
sorted = array[i];
sort( sorted.begin(), sorted.end() );
cout << sorted << '\t' << array[i] << '\n';
}  }

// der     red
// deer    deer
```

### Here is a small demonstration of sorting state combinations ...

```string states[] = {
"alabama", "alaska", "arizona", "arkansas", "california",
"colorado", "connecticut", "delaware", "florida", "georgia",
"hawaii", "idaho", "illinois", "indiana", "iowa",
"kansas", "kentucky", "louisiana", "maine", "maryland",
"massachusetts", "michigan", "minnesota", "mississippi", "missouri",
"newmexico", "newyork", "northcarolina", "northdakota", "ohio",
"oklahoma", "oregon", "pennsylvania", "rhodeisland", "southcarolina",
"southdakota", "tennessee", "texas", "utah", "vermont",
"virginia", "washington", "westvirginia", "wisconsin", "wyoming" };

int main() {
string  pairing, sorted;
for (int i=0; i < 3; ++i)
for (int j=i+1; j < 4; ++j) {
sorted = pairing = states[i] + states[j];
sort( sorted.begin(), sorted.end() );
cout << sorted << '\t' << pairing << '\n';
}     }

// aaaaaabilmnorz   alabamaarizona
```

# Solution 1

```int main() {
vector<string>  pairing(1225), sorted(1225);

// Load all two-state combinations in an array
for (int i=0, m=0; i < 49; ++i)
for (int j=i+1; j < 50; ++j, ++m) {
sorted[m] = pairing[m] = states[i] + states[j];
// Sort each combination and store it in a different array
sort( sorted[m].begin(), sorted[m].end() );
}
// Take each entry in the sorted array
for (int i=0; i < sorted.size()-1; ++i)
// ... and compare it to every other entry in the sorted array
for (int j=i+1; j < sorted.size(); ++j)
if (sorted[i] == sorted[j])
cout << pairing[i] << " ... " << pairing[j] << '\n';
}

To see the answer, select/highlight from here to END
northcarolinasouthdakota ... northdakotasouthcarolina
END
```

# multimap example

```int main() {
multimap<string,string>  mapping;
string                   pairing, sorted;

for (int i=0; i < 49; ++i)
for (int j=i+1; j < 50; ++j) {
sorted = pairing = states[i] + states[j];
sort( sorted.begin(), sorted.end() );
mapping.insert( make_pair( sorted, pairing ) );
}

multimap::iterator iter = mapping.begin();
for (int i=0; i < 15; ++i, ++iter)
cout << iter->first << '\t' << iter->second << '\n';
}

// aaaaaabcehlmmssssttu  alabamamassachusetts
// aaaaaabcfiillmnor     alabamacalifornia
// aaaaaabchillmnnoorrt  alabamanorthcarolina
// aaaaaabchillmnoorstu  alabamasouthcarolina
// aaaaaabdhklmnoortt    alabamanorthdakota
// aaaaaabdhklmoosttu    alabamasouthdakota
```

# Solution 2

```int main() {
multimap<string,string>  mapping;
string                   pairing, sorted;

// Load all sorted pairings into a self-sorting multimap
for (int i=0; i < 49; ++i)
for (int j=i+1; j < 50; ++j) {
sorted = pairing = states[i] + states[j];
sort( sorted.begin(), sorted.end() );
// all insertions are maintained in alphabetical order
mapping.insert( make_pair( sorted, pairing ) );
}

// Find adjacent pairings that are equal
multimap<string,string>::iterator it1 = mapping.begin(),
it2 = mapping.begin();
for (++it2; it2 != mapping.end(); ++it1, ++it2)
if (it1->first == it2->first)
cout << it1->second << " ... " << it2->second << '\n';
}
```

# Solution 3

```int main() {
map<string,string>  mapping;
string              pairing, sorted;

for (int i=0; i < 49; ++i)
for (int j=i+1; j < 50; ++j) {
sorted = pairing = states[i] + states[j];
sort( sorted.begin(), sorted.end() );

// If this sorted pairing has not already been loaded, then load it
if (mapping[sorted].empty())
mapping[sorted] = pairing;

// Otherwise, report the match
else
cout << pairing << " ... " << mapping[sorted] << '\n';
}
}
```

impl