undefined | Better HN

0 pointspinopinopino5y ago0 comments

Studying: differential geometry, poetic edda.

Doing: lifting myself to hell and back and jump rope.

Building: Making maze generators in minetest (before moving them to minecraft)

And trying to figure out if I can find a function that takes two finite consecutive sequences with length N and M of natural numbers, which start by 1 (E.g [1,2,3], but not [1,2,4,5]) and give back a sequence which contain all the numbers starting from 1 up to the NxM, but not necessarily sorted without using the size of the sequences. So I want to number the cross product of the two sequences.

This crap is related to some programming problem I hit.

   t = {1,2,3...} -- <- can be lenght
   s = {1,2,3,4...} <- can be any length
   xs = {} 

   for i,h in ipairs(t) do 
       for j,k in ipairs(s) do 
           q = f(i,j) -- <- I want to know if f is possible 
  to write
           xs[q] = h * k 
       end 
   end

Well the answer is I think no, but I found some functions that work up to a certain number or that work within certain bounds, so how far we can stretch that? And of course it works for the whole set of natural numbers.

0 comments

arnioxux5y ago

Pretty sure the answer is no as a math problem where f is pure. If f returns the same answer each time, the square ending at N,N contains [1, N * N]. Then the rectangle ending at N,N+1 must contain (N * N, N * (N+1)] in the nonoverlapping strip. Ditto for N+1,N. But then for N+1,N+1 all other locations must contain low numbers and there's only a single corner cell left which can contain the rest of the missing numbers between (N(N+1), (N+1)(N+1)]. Unless I made a mistake I don't think any function would work here for N > 1. What were the examples you found?

OTOH as a programming problem you can just cheat and store state somewhere to count the row width. This satisfies your interface requirements (python):

    lastJ = None
    def f(i, j):
        global lastJ
        if i != 0:
            return i * (lastJ + 1) + j
        else:
            lastJ = j
            return j


    N = 3
    M = 5
    seen = set()
    for i in range(N):
        for j in range(M):
            q = f(i, j)
            seen.add(q)
    assert sorted(seen) == list(range(N * M))

pinopinopinoOP5y ago

I am on work, so can't access my home laptop. But this problem is related to pairing functions (but those work for the whole domain of the naturals). It means you need to find a function that walks the numbers in a nice way, like seen here: http://szudzik.com/ElegantPairing.pdf

I think it isn't possible to find a function that works for arbitrary sequences. I know there is a function that works if the sets have the same size (n is size), it is trivial why those work. They have the form n^0 a + n^1 b, where a,b are in [1..n]:

      f :: Integer -> (Integer,Integer) -> Integer 
      f n (i,j) = i + (j - 1)*n
      -- For example: 
      f 3 <$> ((,) <$> [1..3] <*> [1..3])
      [1,4,7,2,5,8,3,6,9]

Now I want to find functions like (n,m is size, n /= m):

      f n m (i,j) = ..

And functions where n maybe chosen but m is between certain bounds. I have found a couple of those by mutilating pairing functions.

I know I can use a counter, but I don't like cheating :p

I need to draw your reasoning on a paper to see it or take some time for it. Little bit busy, working from home, having the kids and stuff :p

1 more reply

j / k navigate · click thread line to collapse