Überprüfen Sie die zyklischen Differenzsätze

14

Eine zyklische Differenzmenge ist eine Menge positiver Ganzzahlen mit einer eindeutigen Eigenschaft:

  1. Sei ndie größte Ganzzahl in der Menge.
  2. Sei reine ganze Zahl (nicht unbedingt in der Menge) größer als 0, aber kleiner oder gleich n/2.
  3. Geben Sie kdie Anzahl der Lösungen an, (b - a) % n = rfür die aund für bdie Sie Mitglieder der Gruppe sind. Jede Lösung ist ein geordnetes Paar (a,b). (Beachten Sie auch, dass diese Version von modulo negative Zahlen positiv macht, indem sie hinzugefügt nwird, im Gegensatz zu den Implementierungen in vielen Sprachen.)
  4. Wenn dies eine zyklische Differenzmenge ist, khängt der Wert von nicht von Ihrer Wahl von ab r. Das heißt, alle Werte von rgeben die gleiche Anzahl von Lösungen für die obige Kongruenz an.

Dies kann anhand des folgenden Beispiels veranschaulicht werden:

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)

Jeder Wert von rhat die gleiche Anzahl von Lösungen, in diesem Fall 3, so dass dies eine zyklische Differenzmenge ist.

Eingang

Die Eingabe ist eine Liste positiver Ganzzahlen. Da es sich um eine Set-Eigenschaft handelt, wird davon ausgegangen, dass die Eingabe nicht sortiert ist. Sie können davon ausgehen , dass nzumindest 2, wenn auch kNull sein kann.

Ausgabe

Ihr Programm / Ihre Funktion sollte einen Wahrheitswert ausgeben, wenn es sich bei dem Satz um einen zyklischen Differenzsatz handelt, oder einen Falschwert, wenn dies nicht der Fall ist.

Testfälle

Gültige zyklische Differenzmengen:

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

( Datenquelle , obwohl ihre Konvention unterschiedlich ist)

Ungültige zyklische Differenzsätze:

1,2,3,4,20
57,3,5,7,17,35,38,49
3,4,5,9
14,10,8
PhiNotPi
quelle
1
Kann aund bdarf das gleiche Mitglied sein (nicht unbedingt a ≠ b)?
Erik der Outgolfer
2
@EriktheOutgolfer wenn bund asind die gleiche Zahl, (b-a)%n = 0aber 0 ist nicht einer der Werte, für die Sie nach Lösungen suchen. Es gibt also kein ausdrückliches Verbot, dass sie dieselbe Anzahl haben, aber sie werden es niemals sein.
PhiNotPi
1
Ich würde es wirklich vorziehen, wenn 7 7 7ungültige Eingabe war. Ein Satz wiederholt keine Werte
Ton Hospel
1
@TonHospel Fertig und fertig. 7 7 7wurde von einem anderen Benutzer angefordert, aber ich habe es entfernt, weil es kein Satz ist.
PhiNotPi
1
Golfen Idee: wir nicht brauchen , gebunden rdurch 0 < r <= max(input)/2, sondern 0 < r < max(input)weil wir erhalten r > max(input)/2durch einfaches Umdrehen der Subtraktion in Fällen , r <= max(input)/2Fällen.
JungHwan Min

Antworten:

9

Jelly , 14 7 Bytes

_þ%ṀṬSE

Probieren Sie es online!

Wie es funktioniert

_þ%ṀṬ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.
Dennis
quelle
5

Schale , 13 Bytes

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

Probieren Sie es online!

Die drei hochgestellten 1s scheinen verschwenderisch ...

Erläuterung

Ë#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
Zgarb
quelle
4

Wolfram Language (Mathematica) , 53 52 Bytes

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

Probieren Sie es online!

Beachten Sie , wir nicht das max Element durch zwei aufgrund der Symmetrie teilen müssen (wir Zählungen aller modulos überprüfen kann 1zu max(input) - 1).

Erläuterung

#~Permutations~{2}

Nehmen Sie alle Länge-2-Permutationen der Eingabe.

#-#2&@@@

Finde die Unterschiede von jedem

Mod[ ... ,Max@#]

Modifiziere das Ergebnis um das maximale Element der Eingabe.

Counts@

Finden Sie die Frequenzen jedes Elements.

SameQ@@

Gibt zurück, ob alle Zahlen gleich sind.

JungHwan min
quelle
4

Python 3 , 86 84 81 Bytes

-3 Bytes danke an JungHwan min

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

Probieren Sie es online!

Stange
quelle
3

JavaScript (ES6), 87 Byte

Gibt 0 oder 1 zurück .

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

Testfälle

Arnauld
quelle
3

Perl, 68 67 66 Bytes

Enthält +2fürap

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

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}

Probieren Sie es 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.
}
benj2240
quelle
2

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 ist die Funktion, die die Prüfung durchführt. Es werden nur alle Unterschiede und Zählungen berechnet.

stolzer haskeller
quelle
letin einem Pattern Guard statt whereein Byte zu speichern: Probieren Sie es online!
Laikoni