Maintenant, nous pensons en n dimensions!

9

La question: étant donné un nombre n≥ 2, combien de paires distinctes de points sur un réseau n-dimensionnel n x n x n x n x n x n ... x n, où les coordonnées vont de 0à n - 1, sont-elles au moins n éloignées? Les paires {(2,1,3,1), (3,2,1,3)}et {(3,2,1,3), (2,1,3,1)}ne sont pas considérées comme distinctes les unes des autres, car elles sont constituées des deux mêmes points dans l'ordre inverse. Notez que le nombre total de paires croît très rapidement. Le nombre de paires au total va 6, 351, 32 640, 4 881 250, 1 088 367 840, etc.

Cas de test:

2 -> 0 (all pairs are at most a distance of sqrt(2) < 2 apart)
3 -> 28 (They must either be (2,2,1) or a permutation apart, or (2,2,2) apart. Each corner
has three non-corner (2,2,1) points corresponding to it. And each corner is associated 
with a corner pair that is a (2,2,2). Thus. 3.5 * 8 = 28.
4 -> 4,888
5 -> 1,501,948
6 -> 486,039,360 (I would like someone to verify this if possible)

Votre code devrait fonctionner pour n <= 5, au moins en théorie. Ne codez pas en dur, c'est une faille standard.

gréé
la source
^ un programme qui peut produire des résultats n=15facilement
Leaky Nun
tinyurl.com/ya2kmb24 <- porté sur C qui peut calculer jusqu'à n=20mais souffre fortement d'un débordement
Leaky Nun
Comment mesurez-vous la distance? Métrique euclidienne? Ou étant donné que c'est un réseau utilisez-vous L_1?
Peter Taylor
@PeterTaylor des cas de test, il est clair que nous utilisons la distance euclidienne all pairs are at most a distance of sqrt(2) apartmais cela devrait être spécifié plus clairement.
Giuseppe

Réponses:

3

MATL , 12 octets

tt:Z^tZPR>~z

Essayez-le en ligne!

Explication

tt   % Implicit input n. Duplicate twice
     % STACK: n, n, n
:    % Range [1 2 ... n]
     % STACK: n, n, [1 2 ... n]
Z^   % Cartesian power. Gives an n^n × n matrix C where each row is a Cartesian tuple
     % STACK: n, C
t    % Duplicate
     % STACK: n, C, C
ZP   % Euclidean distance. Gives an n^n × n^n matrix D of pairwise distances
     % STACK: n, D
R    % Upper triangular part: sets elements below the main diagonal to 0. Call that U
     % STACK: n, U
>~   % Less than or equal? Element-wise. Gives a true-false matrix B
     % STACK: n, B
z    % Number of nonzeros. Implicitly display
     % STACK: number of entries in B that equal true
Luis Mendo
la source
2

Gelée , 14 13 octets

1 octet merci à Dennis.

ṗ⁸Œc_/€ÆḊ€<ċ0

Essayez-le en ligne!

Version maffs rapide

ŒgL€!P:@L!$×P
²S<
ḶœċçÐḟ²ð>0S’2*×⁸ạ⁹$Ѥð€S

Essayez-le en ligne!

Leaky Nun
la source
Quel interprète utilisez-vous pour exécuter cela? Je veux l'essayer mais TIO est trop lent pour n = 5 (expiré après 1 minute) prntscr.com/hqbcph
truqué
@ bushdid911 si vous essayez de dépasser la limite, la limite sera
dépassée
Vous pouvez remplacer æ.`½par ÆḊ€.
dylnan
@ bushdid911 Il peut fonctionner n=5, mais pas en une minute. (cela peut prendre plus que l'âge de l'univers, soyez prudent) Ce n'est pas le code le plus rapide, alors pourquoi prendre la peine de faire fonctionner votre code rapidement?
user202729
1
@ bushdid911 J'ai fait une version plus rapide.
Leaky Nun
2

Python 2 , 137 133 octets

lambda n:sum(n*n<=sum((o[i]-p[i])**2for i in range(n))for o,p in q(q(range(n),repeat=n),repeat=2))/2
from itertools import*
q=product

Mr Xcoder & ovs: -4 octets. Essayez-le en ligne!

dylnan
la source
135 octets . (Pas besoin d'inclure f=)
M. Xcoder
2

J , 40 octets

2%~[:+/^:_]<:[:+/&.:*:"1[:-"1/~#~#:i.@^~

Essayez-le en ligne!

Expirera sur TIO pendant 5 si vous utilisez une précision étendue ( 5xau lieu de 5). Je ne vais pas prendre la peine d'essayer avec 6 sur mon ordinateur car cela va sans doute planter l'interprète.

Vous cherchez des conseils sur le golf, en particulier la partie après la génération des coordonnées. Je pense qu'il devrait y avoir un moyen de retirer certains des bouchons.

]<:[:+/&.:*:"1peut être remplacé de manière équivalente par *:<:[:+/"1[:*:.

Explication

Cette explication se fait sur le REPL (trois espaces indiquent une commande, aucun espace n'indique une sortie). Je vais construire la réponse.

Génération des coordonnées

#~ #: i.@^~ donne toutes les coordonnées qui nous intéressent sur le réseau.

^~est un nombre élevé à lui-même et i.donne la plage [0, n) où n est son entrée. @compose ces fonctions.

   i.@^~ 2
0 1 2 3

#~ copie un numéro seul, par exemple

   #~ 3
3 3 3

#:convertit son argument droit en la base spécifiée par le tableau donné comme argument gauche. Le nombre de chiffres du tableau correspond au nombre de chiffres de cette sortie de base (et vous pouvez avoir une base mixte). Par exemple,

   3 3 3 #: 0
0 0 0
   5 5 #: 120
4 0
NB. If you want 120 base 5 use #.inv
   #.inv 120
4 4 0

Donc, tous ensemble, cela dit énumérer à travers toutes les valeurs de base n (où n est l'entrée) jusqu'à n ^ n, nous donnant effectivement nos coordonnées.

   (#~ #: i.@^~) 2
0 0
0 1
1 0
1 1

Obtention des distances entre chaque paire

D'abord, nous prenons la différence de chaque coordonnée avec toutes les autres en utilisant la dyade /-table et ~-reflexive. Notez que cela ne tient pas compte du fait que l'ordre n'a pas d'importance pour les paires: cela génère des distances en double.

  NB. 2 {. takes the first two elements (I'm omitting the rest).
  2 {. -"1/~ (#~ #: i.@^~) 2
 0  0
 0 _1
_1  0
_1 _1

 0  1
 0  0
_1  1
_1  0

Ensuite, nous utilisons ce verbe +/&.:*:sur chaque coordonnée (at "1, aka rang un). Ce verbe est sum ( +/) sous ( &.:) square ( *:). Under applique le verbe droit (carré) puis recueille ses résultats et le donne comme argument au verbe gauche (somme). Il applique ensuite l'inverse du verbe droit (qui serait racine carrée).

   +/&.:*: 3 4
5
   +/&.:*:"1 ([: -"1/~ #~ #: i.@^~) 2
      0       1       1 1.41421
      1       0 1.41421       1
      1 1.41421       0       1
1.41421       1       1       0

Sans surprise, de nombreuses distances sont les mêmes.

Comptage des distances supérieures ou égales à l'entrée

La dernière partie consiste à voir si la distance est supérieure ou égale à l'entrée utilisant ]<:. Ensuite, tous les résultats sont additionnés à l'aide de +/^:_(somme jusqu'à convergence), en comptant le nombre de valeurs véridiques. Ensuite, cette valeur est divisée par 2 ( 2%~, ici ~signifie échanger l'ordre des arguments fournis à %). La raison pour laquelle nous pouvons diviser par 2 est parce que pour chaque appariement véridique, il y en aura un autre pour l'ordre inversé, sauf pour les appariements qui sont une coordonnée avec lui-même. C'est ok, cependant, car ceux-ci entraîneront une distance de 0.

cole
la source
1
35 octets avec+/@,@(-:@<:+/&.:*:@:-"1/~)#~#:i.@^~
miles