# Verify Cyclic Difference Sets

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

• Can a and b be the same member (not necessarily a ≠ b)? Feb 9 '18 at 16:24
• @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. Feb 9 '18 at 16:27
• I'd really prefer it if 7 7 7 was invalid input. A set doesn't repeat values Feb 9 '18 at 18:24
• @TonHospel Done and done. 7 7 7 was a requested by another user, but I've removed it because it is not a set. Feb 9 '18 at 18:54
• 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. Feb 9 '18 at 20:53

# 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.


# 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


# 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.

# Python 3, 8684 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!

# 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]))

# Perl, 6867 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"


# 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!

# 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.
}


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

• let in a pattern guard instead of where saves a byte: Try it online! Feb 11 '18 at 23:31