1

I’m writing an algorithm that needs to be put in formal notation. It takes two inputs and iterates over:

  • $(1, 2), (1, 3), (1, 4), ..., (1,n)$,
  • then $(2, 3), (2, 4), (2, 5), ..., (2,n),$
  • then $(3, 4) (3, 5), (3, 6), ... (3,$n$),$
  • … and all the way to ($n - 1$, $n$).

The items are taken from a table of size $n^2$, but the operations performed on them will be commutative. They need to be performed in a strict order to avoid duplicates. The results of the process will be added to a list, each of which will be checked against all previous results in order, again, to avoid duplicates. However, within the results list order doesn’t matter.

I’m imagining something that looks like a nested big-sigma “sum from $1$ to $n$”, but this isn’t addition; it’s iterating over the top-right half of a square table to produce the members of a list. How do I formally write this?

Wrzlprmft
  • 5,718
Russ Johnson
  • 179

1 Answers1

2

As order doesn’t matter to you, but uniqueness does, the object you want to describe is a set, as sets can contain any item at most once and do not have a notion of order. There are different ways to do describe your set:

  • Describe the set by constraints:

    $$ \big\{ (i,j) ~ \big |~ i,j∈ℕ; 1≤i<j≤n \big\}.$$

    This reads as: The set of all pairs $(i,j)$, where $i$ and $j$ are natural numbers and $1≤i<j≤n$. If it is clear from context that $i$ and $j$ are natural numbers, you can leave that detail out and just write:

    $$ \big\{ (i,j) ~ \big |~ 1≤i<j≤n \big\}.$$

  • Describe the set as a union of simpler sets, using a big-cup notation:

    $$ \bigcup_{i=1}^{n-1} \big\{(i,i+1), (i,i+2), …, (i,n)\big\} = \bigcup_{i=1}^{n-1} \bigcup_{j=i+1}^{n} \big\{(i,j)\big\} .$$

    The big-cup notation ($\bigcup$) relates to the big-sigma notation ($Σ$) like the set-union symbol ($∪$) to the plus symbol ($+$). The left-hand side is closest to your own description, but mixes ellipses (“…”) and a more formal notation. The right-hand side is obviously more concise. It makes two unions over sets containing only one pair.

Wrzlprmft
  • 5,718