14
\$\begingroup\$

A cyclic difference set is a set of positive integers with a unique property:

  1. Let n be the largest integer in the set.
  2. Let r be any integer (not necessarily in the set) greater than 0 but less than or equal to n/2.
  3. Let k be the number of solutions to (b - a) % n = r where a and b are any members of the set. Each solution is an ordered pair (a,b). (Also note that this version of modulo makes negative numbers positive by adding n to it, unlike the implementations in many languages.)
  4. Finally, if and only if this is a cyclic difference set, the value of k does not depend on your choice of r. That is, all values of r give the same number of solutions to the above congruence.

This can be illustrated with the following example:

Cyclic difference set: {4,5,6,8,9,11}
0 < r <= 11/2, so r = 1,2,3,4,5
r=1: (4,5) (5,6) (8,9)
r=2: (4,6) (6,8) (9,11)
r=3: (5,8) (6,9) (8,11)
r=4: (4,8) (5,9) (11,4)  since (4-11)%11=(-7)%11=4
r=5: (4,9) (6,11) (11,5)

Each value of r has the same number of solutions, 3 in this case, so this is a cyclic difference set.

Input

Input will be a list of positive integers. Since this is a set property, assume that input is not sorted. You can assume that n is at least 2, although k may be zero.

Output

Your program/function should output a truthy value if the set is a cyclic difference set, or a falsey value otherwise.

Test Cases

Valid cyclic difference sets:

10,12,17,18,21
7,5,4
57,1,5,7,17,35,38,49
1,24,35,38,40,53,86,108,114,118,135,144,185,210,254,266,273
16,3,19,4,8,10,15,5,6
8,23,11,12,15,2,3,5,7,17,1

(data source, although their convention is different)

Invalid cyclic difference sets:

1,2,3,4,20
57,3,5,7,17,35,38,49
3,4,5,9
14,10,8
\$\endgroup\$
  • 1
    \$\begingroup\$ Can a and b be the same member (not necessarily a ≠ b)? \$\endgroup\$ – Erik the Outgolfer Feb 9 '18 at 16:24
  • 2
    \$\begingroup\$ @EriktheOutgolfer if b and a are the same number, then (b-a)%n = 0, but 0 isn't one of the values that you're looking for solutions for. So there's not an explicit prohibition on them being the same number, but they never will be. \$\endgroup\$ – PhiNotPi Feb 9 '18 at 16:27
  • 1
    \$\begingroup\$ I'd really prefer it if 7 7 7 was invalid input. A set doesn't repeat values \$\endgroup\$ – Ton Hospel Feb 9 '18 at 18:24
  • 1
    \$\begingroup\$ @TonHospel Done and done. 7 7 7 was a requested by another user, but I've removed it because it is not a set. \$\endgroup\$ – PhiNotPi Feb 9 '18 at 18:54
  • 1
    \$\begingroup\$ Golfing idea: we don't need to bound r by 0 < r <= max(input)/2, but instead 0 < r < max(input) because we can obtain r > max(input)/2 cases by simply flipping the subtraction in r <= max(input)/2 cases. \$\endgroup\$ – JungHwan Min Feb 9 '18 at 20:53
9
\$\begingroup\$

Jelly, 14 7 bytes

_þ%ṀṬSE

Try it online!

How it works

_þ%ṀṬSE  Main link. Argument: A (array of unique elements / ordered set)

_þ       Subtract table; yield a 2D array of all possible differences of two
         (not necessarily distinct) elements of A.
  %Ṁ     Take the differences modulo max(A).
    Ṭ    Untruth; map each array of differences modulo max(A) to a Boolean array
         with 1's at the specified indices. Note that all 0's in the index array
         are ignored, since indexing is 1-based in Jelly.
     S   Take the sum of these arrays, counting occurrences.
      E  Test if all resulting counts are equal.
\$\endgroup\$
5
\$\begingroup\$

Husk, 13 bytes

Ë#m%▲¹×-¹¹ḣ½▲

Try it online!

The three superscript 1s seem wasteful...

Explanation

Ë#m%▲¹×-¹¹ḣ½▲  Input is a list, say x=[7,5,4]
            ▲  Maximum: 7
           ½   Halve: 3.5
          ḣ    Inclusive range from 1: [1,2,3]
Ë              All elements are equal under this function:
                Argument is a number, say n=2.
      ×-¹¹      Differences of all pairs from x: [0,-2,2,-3,0,3,-1,1,0]
  m%▲¹          Map modulo max(x): [0,5,2,4,0,3,6,1,0]
 #              Count occurrences of n: 1
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 53 52 bytes

SameQ@@Counts@Mod[#-#2&@@@#~Permutations~{2},Max@#]&

Try it online!

Note, we don't need to divide the max element by two due to symmetry (we may check counts of all modulos 1 to max(input) - 1).

Explanation

#~Permutations~{2}

Take all length-2 permutations of the input.

#-#2&@@@

Find differences of each

Mod[ ... ,Max@#]

Mod the result by the maximal element of the input.

Counts@

Find the frequencies of each element.

SameQ@@

Return whether all of the numbers are the same.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 86 84 81 bytes

-3 bytes thaks to JungHwan Min

lambda x:len({*map([(b-a)%max(x)for a in x for b in x].count,range(1,max(x)))})<2

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 87 bytes

Returns 0 or 1.

a=>a.map(b=>a.map(c=>x[c=(c-b+(n=Math.max(...a)))%n-1]=-~x[c]),x=[])|!x.some(v=>v^x[0])

Test cases

let f =

a=>a.map(b=>a.map(c=>x[c=(c-b+(n=Math.max(...a)))%n-1]=-~x[c]),x=[])|!x.some(v=>v^x[0])

console.log('[Truthy]')
console.log(f([10,12,17,18,21]))
console.log(f([7,5,4]))
console.log(f([57,1,5,7,17,35,38,49]))
console.log(f([1,24,35,38,40,53,86,108,114,118,135,144,185,210,254,266,273]))
console.log(f([16,3,19,4,8,10,15,5,6]))
console.log(f([8,23,11,12,15,2,3,5,7,17,1]))

console.log('[Falsy]')
console.log(f([1,2,3,4,20]))
console.log(f([57,3,5,7,17,35,38,49]))
console.log(f([3,4,5,9]))
console.log(f([14,10,8]))

\$\endgroup\$
3
\$\begingroup\$

Perl, 68 67 66 bytes

Includes +2 for ap

perl -apE '\@G[@F];pop@G;s:\d+:$G[$_-$&].=1for@F:eg;$_="@G"=~/^1*( 1*)\1*$/' <<< "4 5 6 8 9 11"
\$\endgroup\$
3
\$\begingroup\$

Python 3, 74 bytes

lambda x:len({sum(1+(a+r)%max(x)in x for a in x)for r in range(max(x))})<3

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 81 bytes

->s{n=s.max
(1..n/2).map{|r|s.permutation(2).count{|a,b|(b-a)%n==r}}.uniq.size<2}

Try it online!

Ungolfed:

->s{
  n=s.max
  (1..n/2).map{|r|               # For each choice of r
    s.permutation(2).count{|a,b| # Count the element pairs
      (b-a)%n==r                 #   for which this equality holds
    }
  }.uniq.size<2                  # All counts should be identical.
}
\$\endgroup\$
2
\$\begingroup\$

Haskell, 84 bytes

l s=all((g 1==).g)[1..t-1]where t=maximum s;g j=[1|x<-s>>=(`map`s).(-),x==j||x+t==j]

l is the function that does the check. It just computes all differences and counts.

\$\endgroup\$
  • \$\begingroup\$ let in a pattern guard instead of where saves a byte: Try it online! \$\endgroup\$ – Laikoni Feb 11 '18 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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