Writing a Program that Print Out All Possible Monotonic Functions

Question

I am trying to write a program (via C++) that prints out all possible functions $f:\{1,...,m\}\to\{1,...,n\}$ such that if $i\leq j$ then $f(i)\leq f(j)$.

I am really confused because I am not sure if it is possible to write a program that could do so, since there is basically an infinite number of functions that satisfy such condition. Could you help me out?

Answer 1

There are two issues on which the question is a bit unclear.

The first, and really crucial, issue is: which of the following three problems are you trying to solve?

1. Given $n,m$, write a C function void monotone_n_m() that prints all monotone functions $f:\{1,\dots,n\}\to\{1,\dots,m\}$.
2. Write a C function void monotone(int n, int m) that, given $n,m$, prints all monotone functions $f:\{1,\dots,n\}\to\{1,\dots,m\}$.
3. Write a(n infinite-loop) C function void every_monotone() that, for every $m,n$, and every monotone function $f:\{1,\dots,n\}\to\{1,\dots,m\}$, eventually prints $f$.

The distinction between the three is really crucial. 1. is looking for a function that takes no input and runs for a given, fixed time. 2 is looking for a function that takes $(n,m)$ as input, and eventually terminates, but whose running time can be arbitrarily large for sufficiently large $(n,m)$. 3. is looking for a function that takes no input, never terminates, but just keeps spitting out monotone functions - and every monotone function with a finite domain will, sooner or later, be spit out, even if there are infinitely many of them. Let's tackle each of the $3$ problems in turn, below, after dealing with the second issue.

The second issue is: what do you mean by "print a function"? Do you mean print the C code that implements that function? In fact, this is not such a big deal, because any function $f:\{1,\dots,n\}\to\{1,\dots,m\}$ is essentially an integer array a[] of size $n$, such that $f(i)=a[i-1]$ (and note that $f$ is monotone if and only if a[] is sorted, which can be easily checked with a single pass on it). It's not difficult to write a C function void print_foo(int * a, int n) that takes any such array a[] in input and prints another C function int f(int i) returning, on input $i$, $f(i)=a[i-1]$. So, we'll leave it at that, and assume that "printing a sequence of functions" really means "invoking print_foo() on a sequence of integer arrays". Let's dive into the $3$ problems.

---

1. This is easy. void monotone_n_m() has $n$ nested loops for($i_1:1\to m$) $\dots$ for($i_n:1\to m$), and in the inner loop checks if the $n$ element array $a=[i_1,\dots,i_n]$ is sorted (meaning the corresponding function would be monotone); and if (and only if) a[] is sorted print_foo(a,n) gets called to print the corresponding function.

---

2. This is trickier, because in some sense, you need a program with a number of nested loops $n$ that depends on the input! C is not as friendly as other languages (e.g. Lisp!) for this stuff (C++ is somewhat better), but it's still quite doable, e.g. using recursion. To this end, we can write a function void rec(int n, int m, int $\ell$, int * a) with a third argument $\ell$ that informally describes how deep in the nested loops we are (i.e. on which index of the array we are currently operating), and a fourth argument that is an integer array a[]; and simply have monotone(n, m) allocate a[], and then invoke rec(n,m,0,a).

   Informally, rec() starts "positioned" on the first element of the array ($\ell=0$), and assigning to it in turn each value in $\{1,\dots,m\}$, calls itself to take care of the second element; then the third ... and so on. When the recursion reaches the last element, instead of rec() we invoke print_foo() (as in 1. above, if and only if a[] is sorted):

void rec(int n, int m, int $\ell$, int * a):

for($i:1\to m$) $\{$ $a[\ell]=i$; if $(\ell<n-1)$ rec(n,m,$\ell+1$,a); else if (a is sorted) print_foo(a,n); $\}$

---

3. This looks hard, but it's actually very easy: you just have to create an infinite loop that, for every $(n,m)$ eventually calls monotone(n, m) (from 2. above). To enumerate every possible pair $(n,m)$, just consider every possible $sum\geq 2$, and split it into all the $(sum-1)$ possible pairs adding up to $sum$:

void every_monotone():

$sum\gets 2$; repeat forever: $\{$for($i:1\to sum-1$) monotone(i, sum-i); $sum\gets sum+1$;$\}$

---

Note that the code above is inefficient. Monotone functions can be a very small subset of all functions from $\{1,\dots,n\}$ to $\{1,\dots,m\}$, so enumerating all functions and then keeping only the monotone ones can be a huge waste; but it does make the code hopefully a bit easier to understand. To only enumerate monotone functions, instead of having each index range from $1$ to $m$, simply have it range from the value of the previous index (or from $1$ in the case of the first) to $m$.

Answer 2

Ignoring the last condition, just counting the functions that go from {1,...,m} to {1,...,n}: there are n times m functions. For example, there are n functions for which f(x)=1, when x is not 1, there are another n functions for which f(x)=1, when x is not 1, but for which f(2)=2, and so on

Answer 3

First, note that there is a finite number of all posible functions from $\{1\dots m\}$ to $\{1\dots n\}$. So, the number of monotone functions is also finite.

Such a function is just a monotone sequence of numbers $1\dots n$ of length $m$. If you randomly pick up $m$ numbers and sort them, you get such a sequence; any sequence can be built this way. Thus, the problem boils down to listing all sorted $m$-element combinations of numbers from $1 \dots n$ with repetitions.

I'll show a possible way of listing this sequences, leaving the actual algorithm to you.

$$1\dots 1,1$$ $$1\dots 1,2$$ $$\dots$$ $$1\dots 1,n$$ $$1\dots 2,2$$ $$1\dots 2,3$$ $$\dots$$ $$1\dots 2,n$$ $$1\dots 3,1$$ $$\dots$$ $$n\dots n,n$$