# Compiti per casa

## skypjack

Salve a tutti,

quello che sto per proporre non è un problema legato a Gentoo quanto legato alla programmazione.

Se chiuderete la discussione, lo capirò, ma se non la chiuderete ne sarò più felice, anche perchè è un problema su cui ragiono da giorni e forse perchè sto perdendo la testa per problemi fisici o forse perchè sto perdendo la testa e basta non ne vengo a capo!

Allora, ho un vettore di 9 elementi che possono contenere i valori da 0 a 8 senza ripetizioni (cioè il vettore contiene una delle possibili permutazioni del set 012345678), senza eccezioni. Ho una struttura hash in cui inserisco il vettore associato ad una marchio che lo contraddistingua.

Ora, dovrei:

- poter dire se nell'hash esiste già il vettore (non conoscendo il marchio associato, se esistente)

- recuperare il vettore passando il solo marchio (se esiste un'associazione)

Si deduce che, per permettere di svolgere in modo efficace ed efficiente le due funzioni sopra, il marchio deve essere generato come computazione degli elementi del vettore legati alla loro posizione (il solo modo per distinguere due vettori diveris è valutare i dati elementi, che sono sempre gli stessi permutati, considerando appunto la loro posizione relativa, elemento che distingue).

Le ho provate di tutte, ma non riesco a trovare una funzione che mi produca un marchio, a partire da quanto sopra, senza collisioni (il marchio sarà poi elaborato in modulo per generare l'indice per l'inserimento nell'hash, di dimensione minore dello spazio degli indici, altrimenti non avrebbe senso, e qui si avranno collisioni inevitabili, altrimenti non sarebbe un hash!!).

Se qualcuno può/sa aiutarmi a trovare, o almeno a provare la non esistenza di, una funzione che mi generi un marchio sempre diverso per diverse permutazioni del vettore in ingresso, sarei felicissimo. Ovviamente, le dimensioni devono essere limitate in occupazione di spazio: trasformare il vettore in un unsigned long int moltiplicando ogni cella per una potenza del dieci crescente risolve il problema ma mi esaurisce la memoria troppo velocemente!!

Ogni suggerimento è benvenuto...

----------

## Ic3M4n

ma in che linguaggio di programmazione lo staresti facendo questo "coso"?

----------

## djinnZ

 :Shocked: 

sarò distratto ma non ci ho capito niente, forse del codice di esempio commentato sarebbe più chiaro.

----------

## skypjack

Il linguaggio è il C, ma non è rilevante.

Il problema è matematico, più che altro.

Astraendo dal contorno informatico, si riduce a trovare una funzione invertibile (nota, invertibile) che mappa ogni possibile permutazione del vettore:

[0][1][2][3][4][5][6][7][8]

Su N, in valori compresi fra 0 e il numero di permutazioni, che è dato da 9! se non sbaglio. Così, si ottiene un "marchio" diverso per ogni diversa permutazione del vettore di cui sopra, cioè la soluzione del problema.

Il fatto che poi uso questi valori in un hash è secondario, il vero problema è trovare una funzione del genere!!

----------

## djinnZ

L'unica funzione invertibile ed a risultato univoco sulle permutazioni di nove elementi in nove occorrenze che mi viene a mente è generare un intero di 29 bit (è 9^9 non 9!) quindi non puoi far nulla a meno che non definisci degli intervalli discreti e crei una funzione complessa (un poco sulla falsariga di quello che si è fatto per UTF8 tanto per capirci) con tutte le enormi complicazioni che seguono.

Da quel che mi ricordo non ci può essere una soluzione, non puoi creare un hash univoco ed invertibile che abbia un valore inferiore al numero di permutazioni dell'insieme.

Dovresti trattare il "vettore" come un comune numero (in base 9, non 10, attenzione) e convertirlo in binario. Per la conversione non mi ricordo quale ma c'era un'apposita libreria. Considera che un intero a 29 bit ed uno a 32 sono la stessa cosa in termini di allineamento e vedrai che non ne vale la pena.

Altrimenti dovresti cercare qualche vecchio esempio di algoritmo di compressione (ma in tal caso non è univoco) oppure mi viene a mente un qualcosa, forse di Knuth o Wirth, che trattava di algoritmica però, ma è passato davvero troppo tempo.

edit: ma proprio in base 9?  :Twisted Evil:  se ti è possibile adotterei la base 8 che diventa molto più semplice da trattare (ed in questo caso trattasi di banale intero di 24 bit e facilmente convertibile senza calcoli allucinati)

----------

## makoomba

9^9 include le ripetizioni, le permutazioni sono effettivamente 9!

non so se sia possibile trovare una funzione hash perfetta che restituisca quindi un numero compreso tra 0 e 9!-1 senza generare collisioni.

mi viene in mente che, trattandosi di permutazioni, dal computo si può escludere una delle componenti.

01234567 è equivalente a 012345678 perchè l'ultima cifra, essendo "obbligata", non aggiunge alcuna informazione.

es 

assumendo vettori binari di due elementi, le permutazioni sarebbero: 

01 -> 0

10 -> 1

escludendo il secondo elemento, si otterrebbe quindi una funzione hash perfetta.

----------

## skypjack

Mi sembra che la discussione converga sullo stesso risultato da me raggiunto in solitaria, cioè che non vi è soluzione.

L'unica sarebbe avere una funzione reversibile che mappa uno spazio di dimensione 9 in uno spazion di dimensione 1 e restringerla ali elementi utili, il fatto è che per il "principio dei cassetti" (mi pare) questo non è possibile!! Infatti, non è possibilie mappare uno spazio in un altro di dimensione minore senza perdita o in modo tale che la mappatura sia reversibile.

Da questo discende che la mappatura diventa funzione complessa su uno spazio "bucato" generata da uno spazio limitato, ma se tutto questo deve rallentare drasticamente il codice e l'esecuzione tanto vale trovare un metodo "alternativo" per aggirare il problema, schernendolo una volta soprassato!!

----------

## skypjack

 *makoomba wrote:*   

> 01234567 è equivalente a 012345678 perchè l'ultima cifra, essendo "obbligata", non aggiunge alcuna informazione.

 

Mmm... Questa affermazione effettivamente può tornare utile.

Ora penso come, alleggerisce i calcoli in ogni caso di un fattore 1/9 se non altro...  :Very Happy: 

Thanks!!

----------

## mambro

Una soluzione potrebbe essere scrivere un algoritmo che trova le permutazioni e ad ognuna associare un valore incrementale..

tipo.. prendiamo ad esempio 123 fai un algoritmo che lo permuta.. ad esempio che dia un risultato del genere

123

132

213

231

312

321

poi ad ogni permutazione assegni la posizione in elenco.. quindi per calcolare ad esempio l'hash di 231 l'algoritmo farà così:

prende 123

comincia a permutare

123 -->0

132 --->1

213 --->2

231 --->2

ha trovato che sono uguali quindi ritorna 2 come risultato.

per la funzione inversa fa la stessa cosa..

La soluzione fa abbastanza schifo perchè è fattoriale    :Embarassed:   se mi viene in mente qualcosa di meglio lo posto

----------

## gamberetto

 *skypjack wrote:*   

>  *makoomba wrote:*   01234567 è equivalente a 012345678 perchè l'ultima cifra, essendo "obbligata", non aggiunge alcuna informazione. 
> 
> Mmm... Questa affermazione effettivamente può tornare utile.
> 
> Ora penso come, alleggerisce i calcoli in ogni caso di un fattore 1/9 se non altro... 
> ...

 

In realtà l'informazione era già contenuta nel 9! perché hai il prodotto di 9 termini, uno dei quali uguale a 1.

Io direi di pensare il problema in modo ricorsivo:

- se hai 1 (lo zero) elemento allora F([0])=0 e F-1(0) = [0]

- se hai 2 elementi (0 e 1) allora F([0][1])=0 e F([1][0])= 1 ...

- se hai 3 elementi (0,1,2) ==> scelto il primo elemento mi riconduco al caso precedente quindi avrò 3 blocchi di 2=2! ==> 3x2=6 elementi quindi so che se la funzione mi mappa in 4 sarà nel secondo blocco ([1] primo numeto) e il suo secondo elemento ([2][0]) ==> F-1(4)=[1][2][0] (se ordini sempre dal più piccolo al più grande)

- se hai 4 elementi allora.. adesso devo andare, ma se vuoi continuo un'altra volta.

edit: eccomi!

Praticamente associ alla sequenza [n1][n2]...[n9] il numero F([n1]...[n9])=n1 * 8! + n2 *7!  + n3 *6! + ... + n9 * 0!

con 0!=1 come saprai già.

Per tornare indietro fai una funz. ricorsiva del tipo: tu hai il numero N e fai N/8! e scopri a quale primo numero corrisponde, poi fai (N mod 8!)/7! e così via...

Non so se sia l'unica soluzione. Si tratta solo di capire come vuoi contare le permutazioni (come le vuoi ordinare)

Ciao e buon coding!

----------

## skypjack

E se ho 9 elementi come mi muovo?

Non ho seguito bene il tuo ragionamento, forse l'ora tarda e la sveglia mattutina...

Puoi spiegarmi?

----------

## gamberetto

 *skypjack wrote:*   

> E se ho 9 elementi come mi muovo?
> 
> Non ho seguito bene il tuo ragionamento, forse l'ora tarda e la sveglia mattutina...
> 
> Puoi spiegarmi?

 

Ho aggiornato il post precedente, praticamente devi pensare a 9! numeri in fila ognuno dei quali corrisponde a una permutazione. Si tratta solo di ordinarle in modo intelligente. Una cosa intelligente può essere quella di dividere i 9! numeri in 9 blocchi ognuno con un numero diverso (da 0 a 8 ) all'inizio. Poi ogni blocco è formato da 8! elementi che puoi ordinare anch'essi.

Occhio che avevo fatto un errore nella F([n1]..[n9]) di prima:

F([n1]...[n9])=n1 * 9! + n2 *8! + n3 *7! + ... + n9 * 1!

quindi a [4][7][3][0][1][6][2][8][5] corrisponde il numero 1749177

per tornare indietro fai

1) 1749177/9! = 4.8203 ==> il primo numero è il 4

2) (1749177 mod 9!)/8! = 297657/8! = 7.3823 ==> il secondo numero è il 7

3) (297657 mod 8!)/7! = 15417/7! = 3.058   ===> il terzo numero è il 3

4) (15417 mod 7!)/6! = 297/ 6! = 0.4125 ==> il quarto numero è lo zero

e così via!

Scusa per l'errore alla funzione: bisogna moltiplicare le cifre in ordine dal 9! all' 1 nella F([n1]...[n9])!

Ciao

PS: dimenticavo di specificare che per "mod" intendo la funzione che ti dà il resto della divisione, quindi 5 mod 3 = 2.

PS2: il numero più grande che si ottiene con quella funzione è 3219686 (mi pare)... troppo grande? Dovrebbero bastare 21bit che in informatica non so se sia tanto o poco!

----------

## skypjack

A parte che non devi preoccuparti a spiegare cose come mod (giusto perchè così puoi parlare più spedito e tecnico) la soluzione mi pare un pò costosa!!

Scusa se te lo dico...   :Sad: 

----------

## gamberetto

Mi correggo ancora vedendo che la funzione che ho pensato non funziona più al quinto stadio... veniva 2 invece di 1.

Se hai la serie [4][7][3][0][1][6][2][8][5] è meglio fare così: devi sommare 9 termini che si ottengono

1) 4 in quinta posizione (partendo a contare da 0) 5 * 8! = 201600

2) i numeri che restano (in ordine) sono 01235678 ==> il 7 è in posizione sesta ==> 6*7! = 30240

3) numeri restanti: 0123568 ==> il 3 è in posizione terza ==> 3*6! = 2160

4) 012568 ==> 0 in posizione 0 ==> 0 * 5! = 0

5) 12568 ==> 1 in posizione 0 ==> 0*4! = 0

6) 2568 ==> 6 in posizione 2 ==> 2* 3! = 12

7) 258 ==> 0*2! =0

8 ) 58 ==> 1*1! = 1

9) 5 ==> 0*0! =0

Numero corrispondente = 234013

Vediamo se funziona l'inverso...

1) 234013/8! = 5.803 ==> in posizione quinta c'è il 4 (012345678)

2) (234012 mod 8!) / 7!  = 32413/7! = 6.431 ==> in sesta posizione resta il 7 (contando da 0 e togliendo il 4) (01235678)

3) ... = 2173 / 6! = 3.018055555555555555555555555555 ==> in terza posizione c'è il 3 (0123568)

4) ... = 13 / 5! = 0.1083333333333 ==> in posizione 0 c'è lo 0 (012568)

5) ... = 13/ 4! = 0.54166666666666 ==> in posizione 0 c'è l'1 (12568)

6) ... = 13/3! = 2.166666666 ==> in posizione 2 c'è il 6 (2568)

7) ... = 1/2! = 0 ===> prendo il 2 (258 )

8  ) ... = 1/1! = 1 ==> prendo l'8 (58 )

9) ... = 0/0! = 0 ==> prendo il 5  :Smile: 

quindi in realtà il numero massimo che ti serve è il 362879 ... 18bit dovrebbero bastare.

Scusate per i post pesantissimi e inutili di prima !!!   :Embarassed: 

PS: naturalmente non mi assumo nessuna responsabilità se è tutto sbagliato!!!   :Wink: 

PS2: non ho visto il tuo ultimo post... costosa in che senso????   :Question: 

----------

## Delta9

Io questo problema l'avevo risolto l'anno scorso...

Non mi ricordo come, sto tentando di capirlo. Intanto se vuoi ho il codice

```
using namespace std;

#include <iostream>

#define N 9

int alfabeto[N+1] = { 0 };

long long int fatt[N+1] = { 1 };

int main( )

{

  long long int rank;

  cin >> rank;

  for (int i=1; i<=N; i++)

    fatt[i] = i * fatt[i-1];

  for (int i=N; i>0; i--) {

    long long int k = ((rank-1) / fatt[i-1]) + 1;

    for (int j=1; j<=N; j++) {

      if (alfabeto[j] == 0)

        k--;

      if (k == 0) {

        cout << j << endl;

        alfabeto[j] = 1;

        break;

      }

    }

    rank = (rank - 1) % fatt[i-1] + 1;

  }

}

```

È in C++, ma convertirlo in C dovrebbe essere semplice (a parte le dichiarazioni nei for, la lettura e la scrittura non ho usato nulla del C++). Contando i cicli for, dovrebbe essere in O(n^2), quindi abbastanza veloce (dato che n è 9). Prende come input il numero e restituisce la permutazione.

Questo invece fa il contrario

```
using namespace std;

#include <iostream>

#define N 9

int alfabeto[N+1] = { 0 };

long long int fatt[N+1] = { 1 };

int main( )

{

  long long int rank = 0;

  for (int i=1; i<=N; i++)

    fatt[i] = i * fatt[i-1];

  for (int i=N; i>0; i--) {

    int c, k = 0;

    cin >> c;

    for (int j=1; j<=c; j++) {

      if (alfabeto[j] == 0)

        k++;

    }

    alfabeto[c] = 1;

    rank += (k-1) * fatt[i-1];

  }

  rank++;

  cout << rank << endl; 

}

```

Sempre in O(n^2). Tra loro si capiscono, quindi sono ragionevolmente sicuro che funzionano. Ora provo a capire come (evviva il codice non commentato), ma credo sia all'incirca come diceva gamberetto.

Ciao ciao!

P.S. Se vuoi fare copia-incolla del codice, e devi usare la funzione spesso, ti conviene tenerti la tabella dei fattoriali già calcolata...

----------

## Delta9

Rileggendo, bastano gli int al posto dei long long int...

in origine il programma era per sequenze di 20...

Ah, e in effetti non può non esistere una tale funzione, dato che le permutazioni di 9 elementi sono in numero finito...

Puoi sempre trovare l'hash perfetto di un numero finito di elementi

----------

## Delta9

Sì, ho guardato, e confermo che la mia soluzione è come quella di gamberetto...

Ma dato che ho perso tempo per capirla la spiego...

Forse è meglio dividere in due parti la funzione.

Prima di tutto, associo il mio hash a 8 numeri diversi, a_i, tali che i va da 1 a 8 e 0 < a_i <= i.

Questo lo puoi fare in maniera univoca, ad esempio usando una "base fattoriale", cioè scomponendo il numero n in modo che

n = a_1 + 2! a_2 + 3! a_3 + 4! a_4 + 5! a_5 + 6! a_6 + 7! a_7 + 8! a_8

Ovviamente questo funziona in tutte e due le direzioni.

Seconda fase: costruiamoci la permutazione

tu hai 9 elementi, e vuoi darne una permutazione associata ai tuoi 8 numeri.

Come primo elemento della permutazione, ci metti l'"a_8 -esimo" elemento (li puoi prendere tutti, dato che a_8 va da 0 a 8.

Come secondo elemento, l'"a_7 -esimo" dei rimanenti (che sono 8, quindi è logico che a_7 vada da 0 a 7)

Come terzo elemento prendi l'"a_6 -esimo" dei rimanenti 7

... eccetera

Ti puoi rendere conto che, come hai costruito la permutazione, dalla permutazione data puoi facilmente trovare i tuoi a_i.

Quindi l'applicazione è iniettiva

Dato che iniettiva composta iniettiva fa iniettiva, e dato che l'insieme delle permutazioni e dei possibili hash sono equipotenti, l'applicazione è biiettiva.

Se ci sono dubbi, eccomi!

P.S. Lo so che i programmi sono scritti male, ma ero solo in quinta liceo... (bei tempi!)

----------

## skypjack

Il fatto è che si lavora con fattoriali e con matematica "non precisa", questo non è possibile. Mi spiace.

Se si tratta di alzare il calcolo computazionale e l'occupazione di memoria, preferisco calcolare un long come somma di potenze crescenti del dieci moltiplicate per i valori presenti nel vettore, traendo dal suggerimento sopra posso limitarmi poi ai primi 8 valori. Con calcolo modulare su tali valori, poi, riempio un hash di, per esempio, di celle.

Cercavo qualcosa di più semplice e immediato, ma confermate quanto avevo dedotto: non esiste!!

----------

## Delta9

In che senso scusa? Che roba è la matematica "non precisa"?

La funzione è in tempo O(n^2), è estremamente veloce e funziona...

Non mi è chiaro cosa volevi allora...

----------

## gamberetto

 *skypjack wrote:*   

> Il fatto è che si lavora con fattoriali e con matematica "non precisa", questo non è possibile. Mi spiace.
> 
> Se si tratta di alzare il calcolo computazionale e l'occupazione di memoria, preferisco calcolare un long come somma di potenze crescenti del dieci moltiplicate per i valori presenti nel vettore, traendo dal suggerimento sopra posso limitarmi poi ai primi 8 valori. Con calcolo modulare su tali valori, poi, riempio un hash di, per esempio, di celle.
> 
> Cercavo qualcosa di più semplice e immediato, ma confermate quanto avevo dedotto: non esiste!!

 

Beh.. la mia calcolatricina il fattoriale di 8 lo calcola in una frazione di secondo.

Per l'occupazione di memoria penso sia il minimo che ci sia: associ a 9! combinazioni 9! numeri successivi. Non penso si possa pretendere di più. Se vuoi la biiettività, è questa.

----------

## makoomba

hash perfetta + implementazione 

siamo in 3 a non capire dove sia il problema.

----------

## skypjack

No, scusate, la storia dell'hash vi ha sviato, i valori mi servono univochi non per farne un hash perfetto (l'hashing viene fatto su M valori con M << N, in realtà, con una logica semplice modulare) ma perchè servono come "marchio" della singola permutazione del vettore.

La soluzione data è percorribile, non fraintendete, ma non è ciò che cercavo e questo implica il mio ultimo post, che non avevo spiegato bene, mea culpa. Da qui la mia affermazione: tanto vale creare il marchio con la produttoria delle potenze del dieci, computazionalmente più veloce che ricalcolarmi i fattoriali ogni volta o mantenermeli in memoria (sono 9 numeri, direte voi, si ma a volte anche un bit è importante!!).

Grazie comunque per l'aiuto.

----------

## skypjack

Ripensandoci, ma non basterebbe valutare il vettore come base nove, e quindi segue che:

[a][b][c][d][e][f][g][h][i]  ==>  K = a*9^0 + b*9^1 + c*9^2 + d*9^3 + ... (etc.) ... + i*9^8

A questo punto, per incastrarlo in un intervallo [0, N] basta calcolare il minimo valore possibile, ovvero l'array: [8][7][6][5][4][3][2][1][0] = M, e sottrarre tale valore M ad ogni altro, come: K' = K - M.

Il massimo valore possibile sarà dato dal valore ottenibile col vettore massimo (ovvero il precedente rovesciato) sottratto M.

In questo modo non dovrebbero esserci ripetizioni e, inoltre, si ha una matematica "precisa", ovvero posso risalire dal singolo valore al vettore che lo ha generato lavorando solo con interi e viceversa, come facilmente intuibile, e un pizzico di aritmetica modulare (direi a occhio e croce).

Non nego che dovrebbero esserci dei "buchi" scoperti nell'intervallo, ma ripeto che non è un problema non essendo queste le chiavi per l'hashing, bensì la loro rappresentazione ancora modulare.

Per ottimizzare il tutto, come osservato in un altro post, essendo l'ultimo (o il primo, dipende dai punti di vista) valore non significativo e privo di aggiunta di informazione, lo si può semplicemente ignorare, rielaborando la teoria sopra, ricalcolando il valore minimo M, che non dovrebbe comunque variare (l'escluso è lo zero, quindi già di per se non aggiungeva contenuto informativo come componente).

Ci ho pensato un pò oggi, mentre studiavo altro, mi è balenata questa soluzione: che ne pensate?

Unica pecca: 9^8 >> 8!

Infatti: 9*9*9*9*9*9*9*9 vs 8*7*6*5*4*3*2*1 !!!!

Ma forse (devo provare) sottraendo il valore minimo M e quindi calcolando la marcatura si dovrebbe contenere l'esplosione!!

Suggerimenti?

----------

## djinnZ

vorrei solo ricordarti che una potenza od una moltiplicazione sono più lente di una addizione su un x86.

----------

## skypjack

Non ho capito, cosa intendi dire?

----------

## makoomba

funziona se non sono un problema i circa 370 milioni di buchi generati dalla funzione.

----------

## djinnZ

a parte i buchi su un processore attuale (mi viene sempre a mente che sul primo computer che ho visto la moltiplicazione era ancora una serie di addizioni) a livello di assembler l'elevazione a potenza prende più cicli di clock di una moltiplicazione o di un fattoriale (se non mi ricordo male, saranno almeno dieci anni che non mi pongo più problemi del genere), quindi una somma di fattoriali è più veloce di una somma di potenze, nella pratica le prestazioni di un algoritmo non dipendono solo dalla sua complessità; il seguito del vecchio discorso che "for(n=1;n=100;n++) a=n/2;" richiede almeno otto volte più tempo di "for(n=0,5;n=100;n++) a=n;", per capirci.

E poi sono certo che c'era una funzione ottimizzata per la conversione da un numero in baseN a binario e conviene usare direttamente quella con un intero a 32 bit, tanto comunque i numeri sono memorizzati secondo la word del processore ed avere un intero di 19 (9!) o di 23 (9^9) bit occupa lo stesso spazio in ram e su disco.

----------

## skypjack

A me in fondo non interessano i buchi ma l'unicità dei valori generati.

Quindi: funziona!?

----------

