1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

  1. 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); $\}$


  1. 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$.

$\endgroup$
  • $\begingroup$ Hmmm....I am asking about C++ domain. $\endgroup$ – MathWanderer Mar 1 '17 at 12:05
  • $\begingroup$ @MathWanderer everything I wrote about C also applies to C++. With C++ you can do more things (e.g. instead of having a separate rec(), just write monotone(m,n) with two extra default arguments $\ell=0$ and $a=0$), including some slightly more sophisticated things like the use of iterators that would produce more elegant code, at the expense of being accessible to fewer readers. I think that, as it stands, the answer strikes a good balance between being "good" and being "accessible" to people without sophisticated programming backgrounds (this is not, after all, a website devoted to coding). $\endgroup$ – Anonymous Mar 1 '17 at 13:01
2
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you mean by it? How can I determine all possible functions from n x m functions? $\endgroup$ – MathWanderer Feb 28 '17 at 22:45
  • $\begingroup$ Sorry, the answer is $n^m$$ $\endgroup$ – Andrei Feb 28 '17 at 22:47
  • $\begingroup$ Yes, but still I am curious about it. $\endgroup$ – MathWanderer Feb 28 '17 at 22:48
  • $\begingroup$ @lisyarus just showed you how to write the functions. Remember that you don't need an analytical form, but a tabular form. You don't care what the function is doing for numbers not in {1,...,m}. For example, say m=2, and n=1. You have $f(1)=f(2)=1$ as one function. I don't write it as $f(x)=1$ or $f(x)=\sin(2\pi x)+1$ or any other form $\endgroup$ – Andrei Feb 28 '17 at 23:03
  • $\begingroup$ Thank you. Based on your explanation, I do not have to worry if the function is integer-valued function or not, right? I was trying to think about some integer functions as both domain and range are composed of integers, but it seems that I do not have to worry about what function is doing for the numbers. $\endgroup$ – MathWanderer Feb 28 '17 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.