Generate Skolem sequences

GolfScript, 48 46 characters

:b,1,{)2\?){{.2$&!{.2$|@@}*.+.4b?<}do;;}+%}@/,

The faster version (try online) - runs reasonable fast, e.g. n=8 takes about two seconds. And the chosen approach takes really few characters.

This version also works with bitmasks. It builts the possible result array from 1 upwards, i.e. for n=3:

1: 000011        000110 001100 011000 110000
2: 010111 101011 101110        011101 110101 111010

While some results (like 000011) have two possible continuations, others (i.e. 001100) have none and are removed from the result array.

Explanation of the code:

:b           # save the input into variable b for later use
,            # make the list 0..b-1 (the outer loop)
1,           # puts the list [0] on top of the stack - initially the only possible
             # combination
{)           # {...}@/ does the outer loop counting from i=1 to b
  2\?)       # computes the smalles possible bit mask m=2^i+1 with two bits set 
             # and distance of those equal to i (i.e. i=1: 11, i=2: 101, ...)
  {          # the next loop starts with this bitmask (prepended to code via
             # concatination {...}+
             # the loop itself iterates the top of the stack, i.e. at this point 
             # the result array                 
             # stack here contains item of result array (e.g. 00000011)
             # and bitmask (e.g. 00000101)
    {        # the inner-most loop tries all masks with the current item in the result set
      .2$&!  # do item and result set share not single bit? then - {...}*
      {
        .2$| # then generate the new entry by or-ing those two
        @@   # push it down on the stack (i.e. put working items to top)
      }*
      .+     # shift the bit mask left by one
      .4b?<  # if still in the range loop further
    }do;;    # removes the remainders of the loop (i.e. item processed and mask)
  }+%        # stack now contains the new result array
}@/
,            # length of result array, i.e. the number of Skolem sequences

GolfScript (46 chars)

:&1,\,{0,2@)?)2&*{2${1$^}%@+\2*}*;+}/{4&?(=},,

This is an expression which takes input on the stack. To turn it into a full program which takes input on stdin, prepend ~

It is fairly inefficient - most of the savings I made in golfing it down from 56 chars ungolfed were by expanding the range of loops in ways which don't introduce incorrect results but do waste calculation.

The approach is bitwise masking of Cartesian products. E.g. (using binary for the masks) for n=4 the ungolfed code would compute the xor of each element in the Cartesian product [00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]. Any result with 8 bits could only be achieved by non-overlapping masks.

In order to optimise for size rather than speed, the code accumulates partial products (S1 u S1xS2 u S1xS2xS3 ...) and makes each product be of 2n elements rather than just the 2n-1-i which can actually contribute to a valid sequence.

Speed

The golfed version runs for n=5 in 10 seconds on my computer, and more than 5 minutes for n=6. The original ungolfed version computes n=5 in less than a second, and n=6 in about 1 minute. With a simple filter on intermediate results, it can compute n=8 in 30 seconds. I've golfed it to 66 chars (as a program - 65 chars as an expression) while keeping the loops as restricted as possible and filtering intermediate collisions:

~:&1,\,{0,\).2\?)2&*@-{.{[\].~^.@~+<{;}*}+3$%@+\2*}*;\;}/{4&?(=},,

J expression, 47 characters

 +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y

Example:

    y=:5
    +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y
10

Takes about 30 seconds for y=:5 on my machine.

the algorithm is as slow as can be:

• ~.(i.!+:y)A.,~>:i.y generates every permutation of 1 2 .. y 1 2 .. y and removes duplicate entries
• ((=&{:+.2-#@])#;.2)\"1 computes:
  • (...)\"1 for every prefix of every row:
    • #;.2 counts the the elements before each occurence of the last element
    • #@] counts the number of counts (i.e. the number of occurences of the last element)
    • =&{: determines the "equality" "of" "last element"s of the count list and of the original list.
    • +. is a logical OR. =&{:+.2-#@] reads "either the last elements [of the count list and the original list] are equal, or there is only one element [in the count list] rather than two".
• */"1 multiplies (logical AND) over the rows of the condition table, determining which permutations are Skolem sequences.
• +/ sums the ones and zeroes together.