Tre numeri - II

[Erich]

Feedback: non funziona

Cordialmente, Alex

Aglia! Nel senso che calcola l'output sbagliato o ti da qualche errore di esecuzione?

[axpgn]

Sul codice non metto bocca
Mentre per l'output, già per $n=7$ ce n'è uno di troppo.

Cordialmente, Alex

[Erich]

Ciao, scusa se ci ho messo un po' ma sono stato impegnato e non volevo rispondere prima di avere un'altra soluzione da proporre.

L'errore dovrebbe essere nel punto in cui rimuovo le terne equivalenti (non uniche), ma direi che l'idea di base sia giusta, no?
In effetti mi hai ben indirizzato per trovare l'errore, non avevo notato che per $n=7$ si ha ['7+0+0', '6+1+0', '5+2+0', '5+1+1', '4+3+0', '4+2+1', '3+3+1', '2+2+3', '1+4+2'] con le tuple evidenziate equivalenti.

Ho dato una sistematina al codice, ed ecco una nuova lista di output:

Testo nascosto, fai click qui per vederlo

# n = 0 --> 0
# n = 1 --> 1
# n = 2 --> 2
# n = 3 --> 3
# n = 4 --> 4
# n = 5 --> 5
# n = 6 --> 7
# n = 7 --> 8
# n = 8 --> 10
# n = 9 --> 12
# n = 10 --> 14
# n = 11 --> 16
# n = 12 --> 19
# n = 13 --> 21
# n = 14 --> 24
# n = 15 --> 27
# n = 16 --> 30
# n = 17 --> 33
# n = 18 --> 37
# n = 19 --> 40
# n = 21 --> 48
# n = 177 --> 2700
# n = 180 --> 2791

(se qualcuno fosse interessato anche alla lista dei risultati la chieda o esegua lo script con Python)

Ecco il codice, adesso sicuramente più comprensibile:

Testo nascosto, fai click qui per vederlo

Codice:

#!/usr/bin/python

import sys
import os

DEBUG = 0   # 0 = none, 1 = verbose, 2 = debug

class Terna:

   terna = {}
   string = ""

   def __init__(self, n1,n2,n3):
      try:
         values = [int(n1),int(n2),int(n3)]
         self.string = str(n1)+"+"+str(n2)+"+"+str(n3)
         values.sort()
         if DEBUG > 1: print(str(values))
         values_dict = {}
         for i in xrange(0,3):
            value = values[i]
            if(not value in values_dict):
               times = values.count(value)
               values_dict[value] = times
         self.terna = values_dict
      except:
         print("Error: worng Terna constructor!")
         exit(1)

   def equivalentTo(self, AltraTerna):
      res = True
      for val in self.terna:
         try:
            if self.terna[val] != AltraTerna.terna[val]:
               res = False
         except:
            res = False
      return res

class TreNumeri:

   permutations = { "cardinality":0, "set": [ Terna(0,0,0) ] }
   unique_perms = { "cardinality":0, "set": [ Terna(0,0,0) ] }
   n = 0

   def __init__(self, number):
      if(number==0):
         print("Storing n=0!")
      self.n = int(number)
      self.permutations = self.getPermutations()
      self.unique_perms = self.getDiffTernas()
      self.printResponso()

   def printResponso(self):
      uniqueTernasOutput = ""
      temp = 0
      for uT in self.unique_perms["set"]:
         temp += 1
         uniqueTernasOutput += "["+uT.string+"] "
         if temp == 5:
            temp = 0
            uniqueTernasOutput += "\n# "
      if DEBUG>0: print("#########################################")
      print("# \tn = "+str(self.n)+" --> "+str(self.unique_perms["cardinality"]))
      if DEBUG>0:
         print("#########################################")
         print("# We've found "+str(self.unique_perms["cardinality"])+" unique sets of three positives")
         print("# numbers such that their sum is "+str(self.n)+":")
         print("#########################################")
         print("# "+uniqueTernasOutput)
         print("#######################################")

   def getPermutations(self):
      # Generating and storing all possible permutations of integers such that their sum is self.n
      n = self.n
      permutations = []
      for x in xrange(0,n):
         permutations.append( Terna(n-x,x,0) )
         for y in xrange(0,x):
            permutations.append( Terna(n-x, x-y, y) )
      if DEBUG>0:
         outPrint = ""
         for te in permutations:   outPrint += "["+te.string+"] "
         print("We've "+str(len(permutations))+" permutations:\n"+outPrint)
      return { "cardinality": len(permutations), "set" : permutations }

   def getDiffTernas(self):
      # Storing a new permutations set and cleaning it from equivalents ternas
      res_set = list(self.permutations["set"])
      for t1 in self.permutations["set"]:
         t1_has_been_checked = False
         for t2 in res_set:
            if t1.string == t2.string or t1.equivalentTo(t2):
               if t1_has_been_checked:
                  res_set.pop( res_set.index(t2) )
               else:
                  t1_has_been_checked = True
      if DEBUG>0:
         outPrint = ""
         for te in res_set: outPrint += "["+te.string+"] "
         print("We've "+str(len(res_set))+" unique permutations:\n"+outPrint)
      return { "cardinality": len(res_set), "set" : res_set }

class main:

   name = ""
   arguments = []

   def __init__(self, argv):
      self.executeOverUserInput(argv)

   def executeOverUserInput(self,argv):
      self.evaluateArguments(argv)
      res = TreNumeri(self.arguments[0])

   def testExecution(self):
      for i in xrange(0,20): TreNumeri(i)
      for i in xrange(1,3): TreNumeri(21**i)

   def evaluateArguments(self,argv):
      self.name = argv[0]
      if(len(argv)<2):
         print("Error: excepting a second argument!")
         exit(1)
      try:
         int(argv[1])
      except:
         if(float(argv[1])): print("The result is 0.")
         else: print("Error: excepting a number as argument!")
         exit(1)
      self.arguments = argv[1:]
      if(len(argv)>2): DEBUG = 1

main(sys.argv)


Le due funzioni "cuore" sono TreNumeri.getPermutations() e TreNumeri.getDiffTernas():

[axpgn]

Bel lavoro, really!

Purtroppo non serve a niente … ovviamente ciò che chiedo è altro

In effetti mi hai ben indirizzato per trovare l'errore, ...

Ero molto bravo a trovare i bug degli altri ... ho pure fatto in tempo a notare che avevi scritto "per $n=6$"

Ecco il codice, adesso sicuramente più comprensibile:

Scherzi, vero? Ovviamente mi riferisco a me stesso … sicuramente sarebbe più apprezzato nella sezione di Informatica.

Cordialmente, Alex

[Erich]

Bel lavoro, really!

Purtroppo non serve a niente … ovviamente ciò che chiedo è altro

Grazie, peccato che lo script aiuti poco nel trovare la formula: sembrerebbe una parabola da come si comporta, ma non sono ancora riuscito a trovarla

In effetti mi hai ben indirizzato per trovare l'errore, ...

Ero molto bravo a trovare i bug degli altri ... ho pure fatto in tempo a notare che avevi scritto "per $n=6$"

Hehe, ed io che credevo d'essere stato veloce nel correggermi

[axpgn]

Giusto per curiosità ( ) , quanto ti ci vorrebbe per trovare la risposta a

$n=12345678901234567890123456789012345678901234567890123456789012345678901234567890$ ?

(sono $80$ cifre, erano $100$ ma non me le scrive tutte )

Cordialmente, Alex

[Erich]

Giusto per curiosità ( ) , quanto ti ci vorrebbe per trovare la risposta a

$n=12345678901234567890123456789012345678901234567890123456789012345678901234567890$ ?

(sono $80$ cifre, erano $100$ ma non me le scrive tutte )

Cordialmente, Alex

Be', diciamo che intanto dipende dalle risorse di calcolo che ho a disposizione; al momento il massimo di cui dispongo sono le circa (se non sbaglio) 25 milioni di operazioni binarie al secondo che mi concede il server dell'università.

Poi, provando ad azzardare un calcolo approssimativo:
a parte le relativamente poche operazioni di inizializzazione, assegnamento e simili, considerando che l'algoritmo prima calcola un numero di combinazioni compreso tra $n^2$ e $n^3$ (spendendo circa $3*n$ (da $3*2^log(n)$) operazioni per ogni terna generata) e dopodiché le confronta una ad una facendo un numero di confronti compreso tra $n^4$ ed $n^9$ (ogni confronto effettua circa $3*n$ (da $3*2^log(n)$) operazioni), per un totale di:
fissati $n^2<r<n^3$ e $n^4<s<n^9$, abbiamo che il numero di operazioni binarie necessarie per risolvere il problema sono:
$r*3*n+s*3*n$

Quindi detto $C : [(n^3+n^5)*3] < C < [(n^4+n^10)*3]$ - i.e. C compreso tra caso pessimo e caso ottimo - con la possibilità di fare $25*10^6$ calcoli al secondo, e con $n=12345678901234567890123456789012345678901234567890123456789012345678901234567890$, il tempo che ci vorrebbe a calcolarlo, in secondi, è $T$ tale che:
$bot = [(1.88167*10^237)+(2.86797 * 10^395)]*3 = 8.60391 *10^395 [(operazioni)];$
$top = [(2.32305*10^316)+(8.22526 * 10^790)]*3 = 2.46758 *10^791 [(operazioni)];$
$bot<C<top$;

[€dit]: ho notato solo dopo che un modo più semplice per indicare il numero di operazioni necessarie C può essere: $C : [3*n^8 < C < 3*n^14]$

Questo in termini di operazioni nel tempo, significa che avendo la velocità $ lambda = 25*10^6 [(n.operazioni)/(secondi)] $ e dividendo $bot [n.operazioni]$ e $top [n.operazioni]$ per la velocità otteniamo (di tipo $[secondi]*([(operazioni)]/[(operazioni)])$):
$bot = (8.60391 *10^395) / (25*10^6) = 1.14718 * 10^388 [secondi]$
$top = (2.46758 *10^791) / (25*10^6) = 3.29010 * 10^783 [secondi]$
Passando da secondi ad ore:
$bot = (1.14718 * 10^388) / (60^2) = 3.18663 * 10^384$
$top = (3.29010 * 10^783) / (60^2) = 9.13918 * 10^779$
In termini di anni:
$bot = 1.21257 * 10^379$
$top = 3.47761 * 10^774$
$to [1.21257 * 10^379$[anni]$< T < 3.47761 * 10^774 $[anni]$]$

Va da se che, pure se avessi sbagliato qualche calcolo, non ci sarebbe nessun rischio di calcolarlo con questo algoritmo ed il potere di calcolo che ho a disposizione
Va detto però che l'algoritmo: uno non è stato rivisto né è stato progettato per funzionare velocemente, due non solo calcola la cardinalità dell'insieme, ma anche gli elementi che lo compongono

[axpgn]

Uellà che analisi! … ma sei già laureato o ancora studi?

Beh, dai, con la "mia" formula ( ) ci vuole una frazione di secondo su un notebook i5

Il risultato è questo:

$12701315627699030625412792968805568287506985727813341*10^103+$

$+46268759843525938627242500718894554445460556381903165*10^51+$

$+7319260275825661738591939744960131331606106868871621$

(Ho dovuto scriverlo su tre righe perché non lo prende come numero unico … ... e non dite che ho sparato numeri a caso perché tanto nessuno può controllare )

Comunque, la domanda era solo per avere un'idea di quanto potesse essere grande la differenza tra una formula diretta e un processo iterativo, non avevo altri scopi …

Un'ultima domanda (se posso permettermi): lo hai fatto per divertimento o anche come esercitazione?

Cordialmente, Alex

[Erich]

Uellà che analisi! … ma sei già laureato o ancora studi?

Studio ancora, non saprei se purtroppo o per fortuna!

Un'ultima domanda (se posso permettermi): lo hai fatto per divertimento o anche come esercitazione?

Certo, direi in primis per divertimento; poi non avendo quasi mai occasione di lavorare con (il semplice) python è anche un modo per non dimenticarne la sintassi ed i vari trucchetti.

Comunque avrei anche un'approssimazione della formula da proporre: risolvendo il sistema tra la generica equazione di una parabola e tre dei punti del grafo della funzione ottenuti dall'algoritmo di cui sopra, ho ottenuto:
$y = (0.0838378279215)x^2 + (0.403228765364)x + 2.07319757843$
(approssimando il risultato all'intero più vicino)

[axpgn]

Studio ancora, non saprei se purtroppo o per fortuna!

Ho confrontato i risultati della tua funzione con i miei (usando le potenze di dieci da $10^1$ a $10^100$) e già da $10^9$ la differenza percentuale è costante: il rapporto tra la tua e la mia è $1.00605394$

Bel lavoro!

Cordialmente, Alex