Re: Perl Translation

Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]> writes:

> I was surprised to see such a short solution can still work for every N, but 
> it seems to be the case. (passes all the tests in my Test-Suite.t and also 
> works for every number up to 380 or so).

It's actually quite a nice, simple solution, and I believe it is
equivalent to the method of arranging N-1 points in a circle and one
point "at infinity" that was discussed earlier.

(Warning: I now go on to assume a basic abstract algebra background)

Essentially, all you need to have a way of coming up with a tournament
for N players is a family of functions f_0, f_1, ... f_{N-2} on the
integers 0..N-1 that satisfies these three properties:

[]  f_i(f_i(x)) = x for all i, x

[]  f_i(x) != x for all i,x

[]  For a, b in (0..N-1), with a != b, there is exactly one i such
    that f_i(a) = b

Now, one way to do this is to find a family of functions for a smaller
value of N and use those functions to build up functions for higher
N.  Both your solution and mine took this approach.  (Mine by doing
something to go from N to 2*N, and a different algorithm to go from N
to 2*N-2.  Yours used what I think is the same algorithm to go from N
to 2*N, and then some algorithm I still haven't dug through to go from
N to N*p, where p is some prime that isn't 2)

However, another way to do this is to find a family of functions g_0,
g_1, ..., g_{N-2} on (0..N-2) such that:

[]  g_i(g_i(x)) = x

[]  g_i(x) = x if and only if x = i.

[]  For a, b in (0..N-1), there is exactly one i such that
    f_i(a) = b 
    (In other words, given a and b you can determine i)

Then, you define f_i as:
    f_i(x) = g_i(x), if x != i and x != N-1
    f_i(i) = N-1
    f_i(N-1) = i

Looking at the conditions on g_i, the first condition suggests that
one way to do things is to impose some sort of group structure on the
numbers (0..N-2) and then set:  (I use values inside square brackets
to mean the number considered as an element of the group)

g_i(x) = [i] * [i] * ([x]^(-1))

Where the multiplication and ^(-1) are the group operations.  (of
course, this works only if there are no two distinct a and b such that
[a]*[a] == [b]*[b])

Now, the easiest group to impose on (0..N-2) is the group you get by
using addition modulo N-1.  This then leads to:

g_i(x) = (2*i - x) % (N-1)

Note that this way of looking at things gives us a few other
possibilities, but none as general or as elegant as this solution.

For example, going back to the conditions on the f_i we see that we
could have a solution if we imposed a group structure on (0..N-1) such
that
  [a] * [a] == [group identity]
for all a.  That is, if every element in the group were order 2.
Then, we could define f_i as:
  f_i(x) = [i] * [x]

Now in general, for arbitrary N, there isn't such a group, but for the
special case when N is a power of 2, there is such a group: the
integers 0..N-1 with the group operation being XOR.  This leads to
this section in my solution:

  if (($n & ($n-1)) == 0) {
    # power of 2 - special-case this
    return mapr {
        my($a) = $_;
        mapr {$a^$_} [0..$n-1]
      } [1..$n-1];
  }

> One thing that delayed me was the fact that I translated the loops to 
>
> for my $d (0 .. $m)
>
> Instead of
>
> for my $d (0 .. ($m-1))
>
> Apparently the (0 ... m) operator in Ruby does not evaluate "m" itself, as 
> opposed to Perl.

Ruby has both a .. (two dot) operator and a ... (three dot operator).
The .. operator behaves as perl does, but the ... operator, as you
observed, leaves off the upper limit.  This is convenient for cases
like this:
  l = somelist.length
  (0...l).each { |x| #whatever 
  }

I had to translate his version to perl for my verifier too, and got
caught on the same thing.