# 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, 2018 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, 2018 at 16:27
• I'd really prefer it if 7 7 7 was invalid input. A set doesn't repeat values Feb 9, 2018 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, 2018 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, 2018 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)


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

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, 2018 at 23:31