Newsgroup: it.comp.hardware
Titolo: [OT] Cerco qualcuno che sappia programmare

Scusate l'OT. Ho bisogno di verificare una formula di statistica (voi vi chiederete, perché? Beh, mi piace giocare coi numeri).
La formula è questa:
Data una matrice di ordine n, che può contenere solo 0 o 1 in ciascuna cella, qual è il numero massimo di combinazioni possibili avendo solo la somma di ciascuna riga e la somma di ciascuna colonna?
Allora, 
n = numero delle combinazioni possibili
r = ordine della matrice
K0 = numero di zeri nella riga
K1 = numero di uni nella riga
E calcolo così:
n = P/2 * (r! + P)
dove P è data da
P = r! / (K0! * K1!)
 
Cioè, per farla breve, ..spero.., ho un quadrato diviso in, ad esempio, 3 righe e 3 colonne. Ogni cella può contenere solo 0 oppure 1. Ma io non so il contenuto di ogni cella. So solo la somma di ogni riga e ogni colonna. 
Esempio con una matrice di ordine 3:
http://i.stack.imgur.com/vPTt4.png
 
Io parto con la situazione del quadrato più a sinistra e devo trovare il numero di combinazioni possibili, cioè il quadrato al centro e a destra.
 
Il numero massimo di combinazioni possibili in una matrice di ordine 4 si ha se ho la somma di ciascuna riga e di ciascuna colonna pari a 2, cioè ci sono in ogni riga e ogni colonna due uni e due zeri. E finché c'è da verificarlo con una matrice di ordine 4 ho preso un foglio di carta e ho creato tutte le combinazioni possibili e la mia formula funziona.
Ma se voglio testarla per una matrice di ordine più grande, magari dispari?
 
Vorrei trovare qualcuno che sappia programmare, in un linguaggio efficiente perché temo che al crescere della matrice i calcoli siano davvero enormi, un software a cui gli possa dire quale sia l'ordine della matrice e la somma di ciascuna riga e colonna e lui poi parte a contare tutte le combinazioni possibili inserendo zeri e uni all'interno della matrice.
 
Son disposto anche a offrirgli una birra virtuale se ci riesce ;)

 Son disposto anche a offrirgli una birra virtuale se ci riesce ;)
 
numero dei simboli elevato al numero di celle
nel tuo esempio il numero dei simboli e' 2, poiche' una cella puo' 
contenere zero o uno (due simboli)
il numero di celle nel tuo esempio e' dato dal numero delle righe per il 
numero delle colonne

 numero dei simboli elevato al numero di celle
 
Ma così non tieni conto del fatto che ogni combinazione deve avere come requisito una somma predeterminata (perché io parto dalla somma che risulta sommando ogni uno in ciascuna riga e ciascuna colonna).
 
In una matrice 4x4 secondo la tua indicazione avrei (4x4)^2 combinazioni, cioè 256. Mentre secondo la mia formula dovrebbero esserci solo 90 combinazioni possibili se tengo conto del fatto che in tale matrice di ordine 4 ogni ogni riga contiene solo 2 uni e ogni colonna contiene anch'essa solo due uni (cioè la somma di ciascuna riga e ciascuna colonna è due).
 
Per questo vorrei tanto avere un software che banalmente non faccia altro che contare tutte le combinazioni semplicemente inserendo in ordine crescente un numero binario nella matrice finché non trova quelli che soddisfino la somma delle righe e delle colonne

 avere come requisito una somma predeterminata
 
Infatti, questo non l'ho considerato perche' non e' chiaro cosa intendi, 
quante siano queste somme e quale ne sia la logica.

>>>>  
http://www.bb2002.it
 :)  <<<<<
........... [ al lavoro ] ...........

 nonnò, 2^(4x4) = 2^64 = 18,446,744,073,709,551,616
 
A casa mia 4x4 fa 16, poi li' non so ;-)

 quante siano queste somme e quale ne sia la logica.
 
Una logica non c'è, se non quella di voler soddisfare la mia curiosità per una cosa che avevo iniziato ben 16 anni fa ma che non ho mai portato a termine.
 
Riprovo a spiegarlo meglio.  Guarda questa immagine, il primo quadrato sulla sinista:
http://i.stack.imgur.com/vPTt4.png
 
questa è la situazione di partenza dove non so cosa ci sia dentro il quadrato, so solo le somme di ogni riga e ogni colonna (che in quell'immagine ho scritto in binario). Per cui nella prima riga la somma è 2 (10 in binario) e quindi ci possono solo essere due 1 in quella riga. Nella seconda riga può esserci un solo 1 e nella terza riga altre due 1. Guardando le colonne invece, la prima colonna potrà contenere solo un 1, così come anche la seconda, mentre la terza colonna, avendo come somma 3 (11 in binario) ci saranno 3 uno.
Con queste condizioni saranno possibili solo due combinazioni che sono i quadrati di centro e di sinistra.
 
La condizione in cui si potranno avere il maggior numero di combinazioni sarà quella dove in ogni riga e ogni colonna ci sarà lo stesso numero di 0 e di 1, quindi in una matrice di ordine 4 il numero massimo di combinazioni si avrà quando la somma di ogni riga e ogni colonna è 2 (così ogni riga e ogni e ogni colonna avranno sempre due 1 e due 0). Mentre in una matrice avente come ordine un numero dispari, ad esempio 5, il numero massimo di combinazioni si dovrebbe avere quando ogni riga e colonna ha 2 zeri e 3 uni oppure 2 uni e 3 zeri. Ma per verificare che la formula che avevo ricavato era corretta l'unico modo è quello di contare manualmente ogni combinazione. Ma per una matrice di ordine 5 o superiore sarebbe un'impresa folle alla beautifull mind... Per questo vorrei trovare qualcuno che sappia programmare e creare questo software

 La condizione in cui si potranno avere il maggior numero di combinazioni sarà quella dove in ogni...
 
 
Ciao,
se non ho frainteso, la questione è abbastanza semplice e non richiede un programma,
 
larghezza = 3
altezza =3
somma_celle_fisse = 5 // basta contare quelle orizzontali in quanto sono ridondanti con quelle verticali
 
2^(larghezza * altezza - somma_celle_fisse)
 
2^(3 * 3 - 5) = 16 combinazioni
 
Ovvero mi limito a calcolare 2^il_totale_delle_celle_libere che ottengo
con la moltiplicazione altezza per larghezza e sottraendo il totale delle celle non variabili.
 
sempre che ti abbia capito.

 sempre che ti abbia capito.
 
Mmm, no mi sa che non hai capito, lo so, non sono molto bravo a spiegare.
 
La somma che risulta nelle righe e nelle colonne deve essere rispettata e non basta la sola somma delle righe, perché se faccio unamatrice 3x3 così:
|0|0|1|
|0|0|1|
|0|0|1|
come puoi vedere la somma delle righe è sempre 1, ma la somma delle colonne è 0 per le prime due colonne e 3 per l'ultima.
Io devo trovare il numero di combinazioni possibili avendo, per esempio nella matrice 3x3, come somma di ogni riga e di ogni colonna 1. E, sempre per esemplificare, le combinazioni possibili sono 6, cioè:
|0|0|1|
|0|1|0|
|1|0|0|
poi
|0|0|1|
|1|0|0|
|0|1|0|
poi
|0|1|0|
|1|0|0|
|0|0|1|
poi
|0|1|0|
|0|0|1|
|1|0|0|
poi
|1|0|0|
|0|1|0|
|1|0|1|
e infine
|1|0|0|
|0|0|1|
|0|1|0|
Come vedi se sommi ogni riga e ogni colonna ottieni sempre 1. Ma per matrici di ordine molto più grande non è così facile contare! In una matrice 8x8 ad esempio vorrei sapere quante combinazioni possibili ci sono se la somma di ogni riga e di ogni colonna è 4 (cioè ci devono essere quattro uni in ogni riga e ogni colonna). Oppure una matrice 9x9 etc etc...

 9x9 etc etc...
 
Il numero che cerchi è la somma di coefficienti multinomiali. Non 
capisco però perché cerchi un programmatore...
 

 capisco però perché cerchi un programmatore...
 
Perché non ho la più pallida idea di cosa siano i coefficienti multinominali! ^_^!
Per cui volevo arrivare in maniera bruta al risultato... contando cioè una alla volta le soluzioni.
In particolare, in una matrice 15x15 con somma di ogni riga e ogni colonna pari a 7 (oppure 8) quante combinazioni sono possibili? Con la mia formula (quella scritta nel primo post) mi risulta 4,2074*10^15 (con un "virgola 5" finale...).
Se un programmatore riuscisse a far un software che conti le combinazioni una per una, arriverei al numero esatto senza virgola finale!
Perché sembra che la mia formula funzioni bene se il numero di ordine della matrice è pari, ma se è dispari salta fuori un virgola 5 che fa storcere il naso! Non può esistere una mezza combinazione...
 
 

 come puoi vedere la somma delle righe è sempre 1
no è 3
 
 
 |0|0|1| 1
 |0|0|1| 1
 |0|0|1| 1
 0 0 3
1+1+1 = 0+0+3 = 3


Lo e` davvero?
Da quello che ho capito, l'OP vuole che la somma
delle righe *e* delle colonne sia uguale ad una
qualche costante.
Questo implica che le une vincolino le altre,
cioe` se c'e` un "1" come primo elemento della
prima riga, *deve* anche esserci come primo
elemento della prima colonna.
 
Nel caso lo sia davvero (somma dei coefficienti
multinomiali) faresti un esempio?
Lui dice che con 4x4 ha 90 possibili combinazioni.
 
Grazie,
 
bye,
 
-- 
 
piergiorgio


Si, hai ragione, ma la matrice
|x|x|x| 1
|x|x|x| 1
|x|x|x| 1
 0 0 3 
ha solo una possibile combinazione. Mentre se cerco il numero di combinazioni di una matrice tipo
|x|x|x| 1
|x|x|x| 1
|x|x|x| 1
 1 1 1 
è di 6 combinazioni (quelle che ho scritto nel post di prima).
Quindi non basta avere solo la somma delle righe, occorre tenere in considerazione anche la somma delle colonne

 elemento della prima colonna.
 
Più o meno è quello che chiedo.
Faccio un altro esempio.
Mettiamo di avere una matrice 4x4 che abbia queste somme nelle righe e nelle colonne:
|x|x|x|x| 3
|x|x|x|x| 0
|x|x|x|x| 2
|x|x|x|x| 1
 1 1 3 2
 
Se io inizio a contare in binario da 0000000000000000 (sedici zeri da inserire nella matrice) fino a 1111111111111111 troverò x numeri che soddisfano le condizioni (ossia le somme delle righe e delle colonne). E un risultato può essere:
|0|1|1|1| 3
|0|0|0|0| 0
|1|0|1|1| 3
|0|0|1|0| 1
 1 1 3 2
che è il numero binario 0111000010110010 ma ci saranno anche altri numeri che soddisfano questi requisiti.
 
Grazie alla mia formula in unamatrice di ordine 4 con somma di ciascuna riga e colonna uguale a 2
|x|x|x|x| 2
|x|x|x|x| 2
|x|x|x|x| 2
|x|x|x|x| 2
 2 2 2 2
il numero massimo di combinazioni è 90. Ma se applico la formula a una matrice di ordine dispari, mi esce un numero con la virgola... quindi c'è qualcosa che non va, ma voglio sapere di quanto è sballata la formula. E quindi se avessi un software che riempie la matrice contando 0 fino a riempirla tutta di 1, avrò il numero di combinazioni possibili che man mano troverà verificando che il numero soddisfi i requisiti delle somme delle righe e delle colonne.
 
Si inizia a capire meglio?

 Lui dice che con 4x4 ha 90 possibili combinazioni.
 
4x4 cosa??? occorre indicare le somme per riga e colonna!
 


L'esempio che ha fatto l'OP.
 
Una matrice binaria 4x4 dove la somma di ogni
riga e di ogni colonna e` 2.
 
Come si calcola il numero di matrici binarie
4x4 che soddisfano questa condizione?
 
Ovviamente usando i coefficienti multinomiali.
 
Perche`, secondo me, ma potrei sbagliare, questi
non tengono conto della dipendenza fra righe e
colonne... Ripeto, potrei sbagliare...
 
bye,
 
-- 
 
piergiorgio

 colonne... Ripeto, potrei sbagliare...
 
Hai capito cosa voglio fare, ma per verificare un calcolo come fai? Il modo più semplice, anche se non elegante, è testarlo.
 
Ho creato un foglio excel dove in una matrice 4x4 se inserisco gli 1 al posto giusto alla fine ottengo nel quadrato rosso il valore 1, cioè di condizioni soddisfatte per ogni riga e colonna. Provate:
https://docs.google.com/spreadsheets/d/1IUn7vipGvl3_DjyJz9ecyMDFbWbuIxflnS_uqvImIPg/edit?usp=sharing
 
Ovviamente potrei ripetere quel pappardello di roba per 65mila volte (il numero cioè di combinazioni binarie a 16 cifre) e vedere alla fine quante volte sono state soddisfatte le condizioni!
Oppure, ed è quello che chiedevo all'inizio, creare un software che inserisca il numero binario dentro la matrice e che man mano conti le volte che le condizioni vengono soddisfatte.

 Oppure, ed è quello che chiedevo all'inizio, creare un software che inserisca il numero binario dentro la matrice e che man mano conti le volte che le condizioni vengono soddisfatte.
 
Con 4x4 non e` un problema esplorare tutto lo
spazio, sono solo 64K combinazioni.
In realta`, non devi neanche esplorarlo tutto.
 
Considera solo *righe* di 4 elementi con 2 "1".
Vi sono solo 6 possibilita` (contro 16, se si
considera ogni combinazione).
Dato che hai 4 righe, il numero di combinazioni
possibili da esplorare e` 6^4 = 1296.
Ovviamente devi passare le 1296 combinazioni per
verificare quali siano corrette (90, alla fine).
 
Se hai una matrice 6x6 e la somma deve essere 3,
allora avrai, per ogni riga, 20 possibilita`.
Per 6 righe sono 20^6 = 64000000 possibilita`,
sempre da esplorare.
Il che e` molto meno di 2^36...
 
Se la matrice e` 5x5, somma 2, allora sono 10
combinazioni per riga, 10^5 = 100000 combinazioni,
ancora una volta da esplorare per trovare quelle
che soddisfano i requisiti di colonna.
 
Con 8x8 diventa, purtroppo, troppo grande.
 
C'e` pero` un metodo migliore... :-)
 
Si puo` creare lo spazio da esplorare per diagonale.
Nel caso 4x4, per ogni *prima* riga possibile, si
prende una *prima* colonna possibile, ma compatibile.
Cioe` si hanno 6 possibili prime righe, ma data questa,
si hanno solo 3 possibili prime colonne (3 che iniziano
con 0 e tre che iniziano con 1).
Dopo si passa alla seconda riga, con il vincolo della
prima colonna, sono altre 3 possibilita`.
Poi si va alla seconda colonna, che ha le prime due
posizioni vincolate dalle prime due righe.
 
E cosi` via.
 
Credo, non ho verificato, che l'albero cosi` creato
renda esplorabile tutto lo spazio delle possibilita`,
ma in maniera molto efficiente.
 
Il programma, pero`, non te lo scrivo... :-P
 
bye,
 
-- 
 
piergiorgio

 
 
:D 
E pensare che sarei davvero disposto a pagare, una cifra piccola si intende, 10, 20 euro, perché sarebbe un programma davvero poco complesso, ma... se non so programmare, mi devo attaccare


Mah, se avessi tempo (e voglia) lo scriverei per
divertimento...
Altrimenti per molto piu` di 20Euro... :-)
 
Ad ogni modo, magari e` una buona occasione per te
per imparare a programmare.
 
Una possibilita` "leggera" e` guardare verso "python",
la cui velocita` puo` essere discutibile, ma magari e`
facile da imparare ed usare.
 
bye,
 
-- 
 
piergiorgio


ma siamo sicuri che il numero di combinazioni dell'esempio precedente è
90????

 Mah, se avessi tempo (e voglia) lo scriverei per
 
Ho buttato li 20 euro, non so minimamente quanto possa chiedere un programmatore per una cosa simile, spero non sia stato offensivo!
Comunque se mai un giorno volessi darmi una mano scrivimi a galerio chiocciola gmail punto com.
 
Intanto grazie per i suggerimenti, vorrei tanto imparare a programmare (se avessi tempo!)

 90????
 
Si, ho controllato con una ricerca esaustiva
e posso confermare (bug a parte, ma dubito).
 
bye,
 
-- 
 
piergiorgio

 90????
 
A questo punto non ne sono proprio così sicuro. Appena ho tempo e ho per le mani il pc con un po' più di ram, mi metto a generare le combinazioni e a inserirle in excel e vediamo cosa salta fuori. Se riesco lo faccio già stasera

 Intanto grazie per i suggerimenti, vorrei tanto imparare a programmare (se avessi tempo!)
 
Prego,
 
bye,
 
-- 
 
piergiorgio


Dunque la formula che avevo scritto all'inizio si conferma corretta per le matrici di ordine pari, come la 4x4:
 
n = numero delle combinazioni possibili
r = ordine della matrice
K0 = numero di zeri nella riga
K1 = numero di uni nella riga
E calcolo così:
n = P/2 * (r! + P)
dove P è data da
P = r! / (K0! * K1!)

 Dunque la formula che avevo scritto all'inizio si conferma corretta per le matrici di ordine pari, come la 4x4:
 
No, si conferma corretta *solo* per la matrice 4x4... :-)
Hai provato 2x2, con somma 1? Sono solo 2 matrici.
 
A meno di non dimostrare una qualche induzione, chesso`,
che dalla 4x4 si puo`ricavare che per 8x8, con somma "4",
vale 90x4 (non e` vero, ovviamente, ve ne sono almeno 2
di piu`).
 
bye,
 
-- 
 
piergiorgio


boh! io ho fatto due conti e me ne escono tante di più... ma posso 
sbagliare eh!
 


150. chi offre di più?
 

 sbagliare eh!
 
Che conti hai fatto? Per curiosita`...
 
bye,
 
-- 
 
piergiorgio


114
 


non voglio dirlo ora per non influenzare gli altri
se qualcuno mi conferma che ho fatto giusto lo spiego
 

 
 
Uhm, non posso confermare...
 
Cosa ti viene se la somma righe / colonne
viene posta = 1?
Cioe` solo un "1" per ogni riga e colonna.
 
bye,
 
-- 
 
piergiorgio


questa è troppo facile, 4!=24

 questa è troppo facile, 4!=24
 
Perche` 4!?
 
Cioe`, spiega il ragionamento.
 
Io direi:
 
Prima riga, 4 possibilita`.
Seconda riga, 3 possibilita` (si esclude
quella comune alla prima).
Terza riga 2 possibilita` (si escludono
quelle comuni alla prima e seconda riga).
Quarta riga 1 possibilita` (resta solo
un posto libero).
 
Quindi 4!.
 
E` lo stesso ragionamento tuo, oppure ne
hai fatto uno diverso?
 
Inoltre, si applica in qualche modo alla
somma 2, invece che 1?
 
bye,
 
-- 
 
piergiorgio

Il 23/10/2016 16:45, Piergiorgio Sartor ha scritto:

hai ragione tu, per forza bruta sono 90. rivedo un po' dove ho sbagliato

 hai fatto uno diverso?
 
Più o meno è come il tuo. Hai 4 possibilità di piazzare l'uno in prima 
riga, dopodiché 3 l'uno in seconda, 2 l'uno in terza, in quarta hai un 
solo posto disponibile. Ergo 4*3*2*1=24.
 
Torniamo al caso dei totali uguali a due. Ho fatto un programma di 
ricerca esaustiva in VBA, orrendo e non ottimizzato (che riporto in 
calce), che ha sputato la risposta nel giro di... un decimo di secondo?
Ergo penso che anche andando di forza bruta si possa trovare una 
risposta per matrici parecchio più grandi.
 
Per quanto riguarda la derivazione di una formula generale, forse - 
forse - si può procedere per via ricorsiva.
Sia N({r1,...,rn},{c1,...,cn}) il numero delle matrici con elementi zero 
o uno che hanno i totali di riga e di colonna come indicati nelle 
parentesi graffe.
Allora N({2,2,2,2},{2,2,2,2})=6*N({1,1,2,2},{2,2,2})
=6[1*N({0,0,2,2},{2,2})+2*N({0,1,1,2},{2,2})+1*N({1,1,1,1},{2,2})]
=6[1*1+2*4+1*6]=6[1+8+6]=6*15=90.
Forse qualcuno più bravo di me è capace di generalizzare l'algoritmo.
 
 
 
Sub vai()
ct = 0
Dim a(15)
For a0 = 0 To 1
For a1 = 0 To 1
For a2 = 0 To 1
For a3 = 0 To 1
For a4 = 0 To 1
For a5 = 0 To 1
For a6 = 0 To 1
For a7 = 0 To 1
For a8 = 0 To 1
For a9 = 0 To 1
For a10 = 0 To 1
For a11 = 0 To 1
For a12 = 0 To 1
For a13 = 0 To 1
For a14 = 0 To 1
For a15 = 0 To 1
If (a0 + a1 + a2 + a3 = 2 And a4 + a5 + a6 + a7 = 2 And a8 + a9 + a10 + 
a11 = 2 And a12 + a13 + a14 + a15 = 2 And _
     a0 + a4 + a8 + a12 = 2 And a1 + a5 + a9 + a13 = 2 And a2 + a6 + a10 
+ a14 = 2 And a3 + a7 + a11 + a15 = 2) Then
     Debug.Print a0; a1; a2; a3; a4; a5; a6; a7; a8; a9; a10; a11; a12; 
a13; a14; a15; a16
     ct = ct + 1
End If
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Debug.Print ct
End Sub
 

 Forse qualcuno più bravo di me è capace di generalizzare l'algoritmo.
 
Interessante, ci devo pensare (e capire...).
 
bye,
 
-- 
 
piergiorgio

 hai ragione tu, per forza bruta sono 90. rivedo un po' dove ho sbagliato
 
Uffa, ci son appena arrivato anche io a contarli per forza bruta.. usando excel!!! Ahahah


Ho provato a usarlo ma mi da errore... (ho messo da "if" a "then" tutto in una sola riga, ma è normale che ci sia un underscore a un certo punto?) ma mi dice che c'è un errore di "prevista fine istruzione" dopo "Debug.Print a0;". Cosa c'è di sbagliato?

>>>>  
http://www.bb2002.it
 :)  <<<<<
........... [ al lavoro ] ...........

 sbagliato i conti...
 
Hai ragione, sono stato troppo superficiale nel mio giudizio.
 
Si potrebbe cercare solo nel dominio delle matrici che soddisfano i 
vincoli di riga, e poi filtrarli rispetto ai vincoli di colonna.
 
Per esempio, in una matrice 4x4 con tutte le somme di riga e colonna 
uguali a 2, ci sono 4!/2!/2!=6 possibi configurazioni della prima riga, 
ergo 6^4 in totale.
 
In una matrice 8x8 con tutte le somme di riga e colonna uguali a 4, le 
configurazioni tra cui scegliere sarebbero (8!/4!/4!)^8, ovvero poco più 
di mezzo milione di miliardi... boh! :)