# 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).

• It might help if you completely enumerate all of the possible functions for a tiny case such as s=2 n=2. I had to read the description a few times to grasp how the randomness would come into play. – Sparr Sep 23 '15 at 18:47
• @Sparr Good idea; edited. – Zgarb Sep 23 '15 at 18:53
• is bounded runtime a requirement? I'm contemplating a solution that produces random functions until it finds a monotonic one. – Sparr Sep 23 '15 at 18:57
• @Sparr I think I'll add a bonus for bounded runtime, so such a solution won't be disqualified. – Zgarb Sep 23 '15 at 19:00
• @Zgarb - perhaps you should make a large bonus for solutions that are both bounded and likely to finish within an hour. – Glen O Sep 24 '15 at 6:46

# 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.

• Nice example with input 3, 2. Unfortunately, I didn't even get a response for 3, 3 in the online pyth executor. Is there an endless loop for this combination?! – bobbel Sep 23 '15 at 21:55
• @bobbel The online executor has a timeout, I think. I try it locally. – isaacg Sep 23 '15 at 23:08
• @bobbel It's not so much an infitie loop has a very slow one. It also works for 2, 4, but not much else. – isaacg Sep 23 '15 at 23:15
• @bobbel I added something even slower. – isaacg Sep 24 '15 at 2:31

# 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(s2sn), 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.

# 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].