12
\$\begingroup\$

Skolem sequences

A Skolem sequence is a sequence of 2n numbers where every number i between 1 and n occurs exactly twice, and the distance between the two occurrences of i is exactly i steps. Here are some examples of Skolem sequences:

1 1
1 1 4 2 3 2 4 3
16 13 15 12 14 4 7 3 11 4 3 9 10 7 13 12 16 15 14 11 9 8 10 2 6 2 5 1 1 8 6 5

The following sequences are not Skolem sequences:

1 2 1 2      (The distance between the 1's is 2, not 1)
3 1 1 3      (The number 2 is missing)
1 1 2 1 1 2  (There are four 1's)

Objective

Write a program, function, or expression to count the number of all Skolem sequences of a given length. More explicitly, your input is an integer n, and your output is the number of Skolem sequences of length 2n. This sequence has an OEIS entry. For n = 0, you may return either 0 or 1. The first few values, starting from 0, are

0, 1, 0, 0, 6, 10, 0, 0, 504, 2656, 0, 0, 455936, 3040560, 0, 0, 1400156768

Rules and scoring

This is code golf. Output format is lax within reason.

\$\endgroup\$
10
  • \$\begingroup\$ Just curious, but what is the 0, 1, 0, 0, 6... in your question? Is that the code snippet, if so what language is that? \$\endgroup\$
    – PhiNotPi
    Jun 14, 2013 at 23:52
  • 2
    \$\begingroup\$ Why is the first item in your output 0? If you're going to admit 0 as a valid input then the output should be 1. \$\endgroup\$ Jun 15, 2013 at 7:52
  • 1
    \$\begingroup\$ Some (including my code) believe that there are zero empty sequences. If 1 makes you feel better, return it. \$\endgroup\$
    – boothby
    Jun 15, 2013 at 10:35
  • 2
    \$\begingroup\$ AFAIK in every context you assume there is one and only one empty sequence/null object/empty set etc/function-to/from-the-empty-set/empty graph/whatever else. \$\endgroup\$
    – Bakuriu
    Jun 15, 2013 at 17:00
  • 1
    \$\begingroup\$ @boothby, did you just call Knuth a fool? \$\endgroup\$ Jun 19, 2013 at 15:08

7 Answers 7

8
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Accepting the faster of tied solutions. \$\endgroup\$
    – boothby
    Jun 21, 2013 at 3:10
6
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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&?(=},,
\$\endgroup\$
2
  • \$\begingroup\$ Damn. Just when I've thought my 48char J solution was good enough to be posted. \$\endgroup\$ Jun 15, 2013 at 9:30
  • \$\begingroup\$ Damn. Our 47-character tie didn't last very long. +1 \$\endgroup\$ Jun 15, 2013 at 10:30
5
\$\begingroup\$

GolfScript, 49 characters

~:/..+?:d(,{d+/base(;:w;/,{.w?)w>1$?=},,/=},,/1=+

Expects the number n on STDIN. This is code-golf - don't try the code with n greater than 5.

\$\endgroup\$
2
  • \$\begingroup\$ Ouch, no greater than 5? \$\endgroup\$
    – boothby
    Jun 17, 2013 at 3:34
  • \$\begingroup\$ @boothby It was the first, direct attempt. We often have to take the decision speed vs. size - and code-golf is about size. That's why I also added the fast version - which originally was much longer but now is even shorter. \$\endgroup\$
    – Howard
    Jun 17, 2013 at 4:54
3
\$\begingroup\$

Husk, 20 19 bytes

₁ḣ
ṁo=¹⁰(moF-¥)uPṘ2

Try it online!

Can be shortened further.

returns 1 for 0.

-1 byte from Jo king.

Explanation

ṁo=ḣ¹`(moF-¥)ḣ¹uPṘ2ḣ
                   ḣ range from 1..n
                 Ṙ2  replicate each element 2 times
               uP    unique permutations of the list
ṁo                   map each permutation to the following two functions
                     and sum the results
     `               flip: f x y = f y x
      (mo   )        map each number to the following:
      (    ¥)ḣ¹      index of each number in 1..n in the permutation
      (  F- )        folded by subtraction
  =ḣ¹                are the differences equal to 1..n?
\$\endgroup\$
0
1
\$\begingroup\$

Sage, 70

This is a little shorter than my original.

sum(1for i in DLXCPP([(i-1,j,i+j)for i in[1..n]for j in[n..3*n-i-1]]))

How it works:

Given a 0/1 matrix, the exact cover problem for that matrix is to find a subset of the rows that sum (as integers) to the all-ones vector. For example,

11001
10100
01001
00011
00010

has a solution

10100
01001
00010

My favorite approach to problems is to cast them to an exact cover problem. Skolem sequences efficiently facilitate this. I make an exact cover problem where solutions are in bijection with Skolem sequences of length 2n. For example, a row of the problem for n=6 is

  a   |  b  
001000|001001000000 # S[b] = S[b+a+1] = a

where a 1 in position a < n means that symbol a is used. The remaining positions correspond to actual locations in the sequence. An exact cover corresponds to each symbol being used exactly once, and each location being filled exactly once. By construction, any symbol k in a location is k spaces away from its partner.

In Sage, DLXCPP is a "dancing links" implementation -- it solves the exact cover problem in an exceptionally graceful manner. It's one of my favorite algorithms ever, and being right at the surface in Sage makes combinatorial enumeration a joy.

\$\endgroup\$
3
  • \$\begingroup\$ Wow, dancing link. Use len(list(...)) will save 4 chars. \$\endgroup\$
    – Ray
    Jun 19, 2013 at 19:29
  • \$\begingroup\$ @Ray My computer would simply die if I computed len(list(...)) for n=16. And it'd utterly kill the runtime. \$\endgroup\$
    – boothby
    Jun 20, 2013 at 3:15
  • \$\begingroup\$ That's right, because converting a generator into a list cost many memory. \$\endgroup\$
    – Ray
    Jun 20, 2013 at 5:10
1
\$\begingroup\$

05AB1E, 22 bytes

ݦ©€DœʒU®εXQ0Úg<}®Q}Ùg

Results in \$0\$ for \$n=0\$.

Try it online or verify the test cases in the range \$[0,4]\$. (Unfortunately times out for \$n\geq5\$.)

Explanation:

Ý                 # Push a list in the range [0, (implicit) input `n`]
 ¦                # Remove the leading 0
                  # (builtin `L` would become list [1,0] for n=0 unfortunately,
                  # resulting in an incorrect result of 3 at the end)
  ©               # Store this list in variable `®` (without popping)
   €D             # Duplicate each, resulting in a flattened list [1,1,2,2,3,3,...,n,n]
     œ            # Get all permutations of this list
      ʒ           # Filter it by:
       U          #  Pop and store the current permutation in variable `X`
        ®         #  Push the ranged list [1,n] from variable `®`
         ε        #  Map it to:
          X       #   Check for each value in list `X`
           Q      #   whether it's equal to the current map value
                  #   (1 if truthy; 0 if falsey)
            0Ú    #   Remove all leading and trailing 0s
              g   #   Pop and get the length of the list
               <  #   Decrease it by 1
         }®Q      #  After the map: check if it's equal to the [1,n] ranged list
      }Ù          # After the filter: uniquify the remaining permutations
        g         # And pop and push the length
                  # (after which this is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.