Combinatorial Object Generation

• All the subsets of a set (in what order?)
• All the permutations of a set of objects
• All k-subsets of an n-set.
• Partition of an integer n into k parts.

Generating Subsets

• If the set contains the elements a₀, a₁, ..., a_n-1, then we can represent a subset as a binary number of length n, each bit being 0 if the corresponding element is not in the set, and 1 if it is.
• So this means that we have to generate all the numbers between 0 and 2ⁿ-1 in binary representation.
• The algorithm starts from one given subset and generates the next one.

Example

Rank	Binary	Subset
0	0 0 0	{}
1	0 0 1	{3}
2	0 1 0	{2}
3	0 1 1	{2, 3}
4	1 0 0	{1}
5	1 0 1	{1, 3}
6	1 1 0	{1, 2}
7	1 1 1	{1, 2, 3}

Sequential Algorithm

Initial_set() {
  for (i=0; i<n; i++)
    a[i] = 0;
}
Next_set() {
  i=0; 
  while (a[i] == 1) {
    a[i] = 0;
    i++;
  }
  if (i < n)
    a[i] = 1;
}

Parallel Version

• Each process will produce its share of subsets.
• The rank for the subset that each process starts from is r = id * 2ⁿ/np where np is the number of processes.
• To determine what subset they start from, we need to convert the rank to binary.
• The master inputs and broadcasts n.
• All the processes then compute r based on the id, convert it to binary, then use the function Next_set to produce 2ⁿ/np subsets.

Binary Conversion

Binary(r) {
  for (i=0; i<n; i++) {
    if (r % 2 == 0)
      a[i] = 0;
    else
      a[i] = 1;
    r = r/2;
  }
}

Permutations

• There are n! permutations of n objects.
• Necessary in brute force algorithms.
• Sequential algorithm to generate the permutations in lexicographical order.
• If a₁, a₂, ..., a_n and b₁, b₂, ..., b_n are two permutations of the same n objects, then the first one is before the second in lexicographical order if there exists k such that a₁ = b₁, a₂ = b₂, ..., a_k-1 = b_k-1 and a_k < b_k.
• Example: 1 2 4 3 5 < 1 2 5 3 4 with k = 3.

Next Permutation

• Suppose that the objects are in a simple array a from 0 to n-1.
• Find the largest k such that a[k] < a[k+1]. If no such k exists, then this is the last permutation.
• Find the largest m>k such that a[m] > a[k].
• Swap a[k] with a[m].
• Reverse the array between k+1 and n-1.
• [7, 1, 3, 6, 5, 4, 2] -> [7, 1, 4, 6, 5, 3, 2] -> [7, 1, 4, 2, 3, 5, 6]

Sequential Algorithm

Next_permutation(a, n) {
  for (k=n-2; k>=0; k--) 
    if (a[k] < a[k+1]) 
      break;
  if (k < 0) 
    return false; // last permutation
  for (m=n-1; a[m]<a[k]; m--);
  swap(a[k], a[m]);
  for(i=k+1, j=n-1; i<j; i++, j--)
    swap(a[i], a[j]);
  return true;
}

Parallel Algorithm

• A subset of permutations can be generated independently as long as we know the first one.
• It's not easy to divide into a random np number of processes.
• If the number of processes = n, then each process(id) will start with a permutation where the first element is a[id] and all the others are sorted in ascending order after that.
• Store a[id]; shift a[0..id-1] by 1 forward; place stored element in a[0].

Initial Permutation

// Assumes that the elements are in order initially
First_permutation(a, n, id) {
  temp = a[id];
  for (i=id-1; i>=0; i--)
    a[i+1] = a[i];
  a[0] = temp;
}

Several Levels

• Generate all the ordered subsets of 2 elements out of the n in lexicographic order.
• Assign each subset to a separate process.
• All the elements not in the subset are initially placed in order.
• Can be generalized to k levels, where k is the largest number such that n!/(n-k)! <= number of cores.
• One can use a subset generation followed by permutations applied to the subset.

Next Subset of Size m

• Original array a, subset = s.
• Find the largest k for which s[k] != a[m-n+k].
• Let j be an index such that s[k] = a[j].
• Assign s[k] = a[j+1].
• For i from k+1 to m, assign a[i] = a[j+1+i-k].
• Example: n=10, m=4, s=[1, 2, 5, 9]. The next one is [1, 2, 6, 7].
• Each process receives the subset from the previous process. If it’s the last permutation of the subset, then generate the next subset, otherwise generate the next permutation.

Next_subset(a, n, s, m) {
  for (k = m-1; k >= 0; k--) // find k
    if (s[k] != a[n-m+k])
      break;
  if (k < 0)
    return false; // last subset
  for (j=n-m+k-1; a[j] != s[k]; j--); // find j
  s[k] = a[j+1]; 
  for (i=k+1; i < m; i++) 
    s[i] = a[j+1+i-k];
  return true;
}

Lexicographic Order

• Assume np = n!/(n-m)!
• Choose a[0] = a[id*(np/n)]. Extract it with the previous procedure (initial permutation).
• Choose a[1] based on the process rank in the subset of permutations starting with a[0]. Extract it by the same procedure as before.
• Choose a[k] based on the process rank in the subset of permutations starting with a[0..k-1]. Extract each of them with the same procedure.
• Each process can generate their initial permutation independently based on the id.

Extract Element

// Extracts the element from position last and places it in position
// first. Shifts the intermediate elements forward by 1.

Extract(a, first, last) {
  temp = a[last];
  for (i=last-1; i >= first; i--)
    a[i+1] = a[i];
  a[first] = temp;
}

Initial Permutation

// Assuming that np = n!/(n-m)!
Initial_permutation(a, n, m, id, np) {
  rank = id;
  subset_size = np/n;
  for (first=0; first < m; first++) {
    last = first + rank/subset_size;
    Extract(a, first, last);
    rank = rank % subset_size;
    subset_size = subset_size / (n-first-1);
  }
}