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]

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

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...
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 se mi viene in mente qualcosa di meglio lo posto

[gamberetto]

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...
Thanks!!

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]

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...

[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

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

Scusate per i post pesantissimi e inutili di prima !!!
PS: naturalmente non mi assumo nessuna responsabilità se è tutto sbagliato!!!
PS2: non ho visto il tuo ultimo post... costosa in che senso????

[Delta9]

Io questo problema l'avevo risolto l'anno scorso...
Non mi ricordo come, sto tentando di capirlo. Intanto se vuoi ho il codice

Code: Select all

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

Code: Select all

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]

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][c][d][e][f][g][h] ==> 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?