Generate a Monotonic Function

Question

Overview

In this challenge, your task is to randomly generate a monotonic mathematical function between two sets.

Input

Your inputs are two positive integers s and n.

After getting these inputs, your program shall generate a random mathematical function f from the set {0,1,...,s-1}n to {0,1,...,s-1}. In other words, f is a "rule" that takes in an n-tuple of integers between 0 and s-1, and returns one such integer. Additionally, f should be monotonic in the following sense. If A and B are two n-tuples such that A[i] ≥ B[i] holds for every coordinate i, then f(A) ≥ f(B).

The exact distribution of the monotonic functions f doesn't matter, as long as each such function has a positive probability of being generated (assuming a perfect RNG).

Output

Your output shall be an enumeration of the inputs and outputs of f. It shall contain all n-tuples of integers between 0 and s-1 in some order, each one being followed by the corresponding output of f. The exact output format is flexible (within reason).

Examples

The inputs s = 3 and n = 2 might produce the output

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2

It contains all the pairs over the set {0, 1, 2} exactly once, and each one is followed by its f-value. The monotonicity condition is also satisfied. The tuples are given here in lexicographical order, but this is not necessary.

As another example, s = 2 and n = 4 might produce

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1

The following are all possible outputs for s = 2 and n = 2 (up to reordering the tuples); your program should randomly output one of them:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1

Rules and Scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Code with explanation is preferred.

There are no restrictions on time complexity, but I'll give a bonus of -15 % if your solution is always guaranteed to finish in a certain amount of time (depending on the inputs, and assuming a perfect RNG that runs in constant time).

Answer 1

Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstration

Input is in the format:

n
s

Output is in the format:

[[value, tuple], [value, tuple], ...]

Simply generates random possibilities and tests them.

---

Alternative 37 byte version which I believe qualifies for the bonus:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstration

This starts by generating all possible monotonic functions, then outputs one at random. It is much slower, and tops out at 2,2.

Answer 2

CJam, 40 bytes - 15% = 34 bytes

q~1$\m*\1$,m*{W$\.+2m*{:.<2b}%1&!},mR]zp

This approach generates all valid functions and then selects on at random. Run time is at least O(s^2sn), but constant for a given input.

I doubt this is what the OP had in mind, but it is guaranteed to finish in a certain amount of time (depending on the inputs[...]) and therefore qualifies for the bonus.

Try it online in the CJam interpreter.

Answer 3

Julia, 64 bytes (-15% = 54.4)

g(s,n)=(K=rand(0:s-1,ntuple(n,i->s));for i=1:n K=sort(K,i)end;K)

Ungolfed:

function g(s,n)
  # Generates a random n-dimensional array with s per dimension
  # and all values being integers between 0 and s-1
  K=rand(0:s-1,ntuple(n,i->s))
  # Loop over the various dimensions
  for i=1:n
    # Sort in the current dimension
    K=sort(K,i)
  end
  return K
end

This will run quickly, with the only possible issue being with memory for large enough s and n (g(10,10) has to produce a 10^10 array, so obviously it's going to run out of memory - even if each number is one byte, that's 10 gigabytes of data).

Output is 1-based indexing, so to determine the result for a given input, you need to add one to each input value. For example, to find f(1,2,6,0,3), you need to examine K[2,3,7,1,4].