Reading

These notes.

Quiz questions

None.

Enumeration

It is not uncommon that we want to iterate over an enumeration of all possible objects. We're used to that when the objects reside explicitly in some data structure (e.g. iterate over all the elements of a linked list). However, another interesting and common scenario is when the objects are not stored objects, but instead are all variations of a given object: e.g. all permutations of a sequence of letters. This lecture just looked at some examples and tried to find patterns in how we could iterate over such sets of objects without having them all stored simultaneously like we're used to.

Printing out all 2-OPTS

#include <iostream>
#include <vector>
using namespace std;

void rev(vector<char> &A, int i, int j)
{
  while(i < j)
    swap(A[i++],A[j--]);
}

void print(vector<char> &A, int n)
{
  for(int i = 0; i < n; i++)
    cout << A[i];
  cout << endl;
}

int main()
{
  vector<char> A;
  char c;
  while(cin >> c)
    A.push_back(c);
  int n = A.size();

  for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
    {
      rev(A,i,j);
      print(A,n);
      rev(A,i,j);
    }
  
  return 0;
}

Printing out all permutations

#include <iostream>
#include <vector>
using namespace std;


void print(vector<char> &A, int n)
{
  for(int i = 0; i < n; i++)
    cout << A[i];
  cout << endl;
}

void allperms(vector<char> &A, int i , int j)
{
  if (i == j) { print(A,A.size()); return; }
  for(int k = i; k <= j; k++)
  {
    swap(A[i],A[k]);
    allperms(A,i+1,j);
    swap(A[i],A[k]);
  }
}

int main()
{
  vector<char> A;
  char c;
  while(cin >> c)
    A.push_back(c);
  int n = A.size();

  allperms(A,0,n-1);
  return 0;
}

Printing out all possible passwords

#include <iostream>
#include <vector>
using namespace std;


void print(vector<char> &A, int n)
{
  for(int i = 0; i < n; i++)
    cout << A[i];
  cout << endl;
}

void genall(char* pswd, int len, vector<char> A)
{
  if (len == 0) { cout << pswd << endl; return; }
  for(int i = 0; i < A.size(); i++)
  {
    pswd[len-1] = A[i];
    genall(pswd,len-1,A);
    // undo not needed
  }
}

int main()
{
  int len;
  cin >> len;
  char* pswd = new char[len + 1];
  pswd[len] = '\0';
  
  vector<char> A;
  char c;
  while(cin >> c)
    A.push_back(c);
  int n = A.size();

  genall(pswd,len,A);
  
  
  return 0;
}

Iterators: making an iterator out of all possible 2-OPTS

#include <iostream>
#include <vector>
using namespace std;

void rev(vector<char> &A, int i, int j)
{
  while(i < j)
    swap(A[i++],A[j--]);
}

void print(vector<char> &A, int n)
{
  for(int i = 0; i < n; i++)
    cout << A[i];
  cout << endl;
}

class Iter2OPT
{
  int i, j, n, oldi, oldj;
public:
  Iter2OPT(int n)
  {
    this->n = n; i = 0; j = 1; oldi = oldj = 0;
  }
  bool hasNext() { return i < n - 1; }
  void next(vector<char> &A)
  {
    // undo old
    rev(A,oldi,oldj);
    rev(A,i,j);
    oldi = i; oldj = j;
    j++;
    if (j == n) { i++; j = i + 1; }
  }  
};

int main()
{
  vector<char> A;
  char c;
  while(cin >> c)
    A.push_back(c);
  int n = A.size();

  Iter2OPT iter(n);
  while(iter.hasNext())
  {
    iter.next(A);
    print(A,n);
  }
  
  return 0;
}