Newsgroup: it.comp.www.php
Titolo: algoritmo combinatorio

Secondo voi qual'è l'algoritmo migliore per far stampare una
combinazione di stringhe del tipo:
ho 5 lettere: a g t j d, voglio far stampare tutte le combinazioni
(senza ripetizioni ovviamente). C'è qualche link che spiega questi
algoritmi?
Grazie
-- 
Per rispondermi togli il cappello

 (senza ripetizioni ovviamente).
Utilizza 5 for innestati od una funzione ricorsiva. Conta in base 5 da
0 a 5^5.
-- 
I am what I am, I do what I can
Sei un newbie? Leggi questo 
http://url.repository.biz/go/3C
Vuoi supportarmi? 
http://url.repository.biz/go/3E
Do. Or do not. There is not try.

0 a 5^5.
Penso di aver quindi risolto cosě, non so se č la soluzione ottimale
(con 3 lettere):
$x=array('a','b','c');
for($i=0; $i<3; $i++){
	for($j=0; $j<3; $j++){
	if($j!=$i)
		for($g=0; $g<3; $g++){
		if($g!=$i and $g!=$j){
		echo $x[$i]."".$x[$j]."".$x[$g];
		echo "<br>";



In questo modo però non si evitano le ripetizioni. Lui chiede le 
combinazioni senza ripetizione.
Cooper
-- 
BlueWare WebAgency
  [Internet:] 
http://www.blueware.it
  [icq:] 146-781-935
  [msn:] 
coo...@blueware.it
 

 combinazioni senza ripetizione.
Mi sembra piu' che evidente che basti un IF per evitarle ...
-- 
I am what I am, I do what I can



Vero, ma non è detto che sia ugualmente evidente anche per chi ha chiesto :) 
Comunque non è solo una questione di if (di certo non è soltanto una if).
Mettendo cinque cicli per  ognuno di essi generi valori compresi fra 0 e 4 e 
oltre a scartare le combinazioni doppie bisogna anche scartare quelle 
situazioni che contengono la ripetizione della lettera 000 = AAA  012 = ABC 
; 222 = CCC etc.
Cooper.
PS: Ho dato per scontato alcuni passaggi che da programmatore avrai 
sicuramente compreso dai tre esempi di sopra.


 soltanto una if).  
Se scrivo che e' 1 (un) if allora e' 1 (un) if.
<?php 
$chars = array ('a', 'g', 't', 'j', 'd');
$cicles = array ();
for ($cicles[0] = 0; $cicles[0] < 5; $cicles[0]++) {
  for ($cicles[1] = 0; $cicles[1] < 5; $cicles[1]++) {
    for ($cicles[2] = 0; $cicles[2] < 5; $cicles[2]++) {
      for ($cicles[3] = 0; $cicles[3] < 5; $cicles[3]++) {
        for ($cicles[4] = 0; $cicles[4] < 5; $cicles[4]++) {
          if ((substr_count (implode ('', $cicles), '0') == 1) &&
              (substr_count (implode ('', $cicles), '1') == 1) &&
              (substr_count (implode ('', $cicles), '2') == 1) &&
              (substr_count (implode ('', $cicles), '3') == 1) &&
              (substr_count (implode ('', $cicles), '4') == 1)) {
               print ($chars[$cicles[0]] . 
                      $chars[$cicles[1]] . 
                      $chars[$cicles[2]] . 
                      $chars[$cicles[3]] . 
                      $chars[$cicles[4]] . '<br />');				
          }
        }
	  }
	}
  }
}
?>


 
perdonate l'intrusione e la furtivita' ma ho pochissimo tempo..
la funzione sotto postata genera tutte le combinazioni possibili esaminando
in modo ricorsivo una stringa e registrando le combinazioni in un array..
la scelta della stringa invece di un'array come vedete e' stata un'po'
sofferta ma come ho gia' detto non ho tempo a disposizione..
anche se uso la ricorsivita' il numero massimo delle funzioni richiamate
ricorsivamente non dovrebbe superare mai il numero pari alla lunghezza
della stringa meno uno..
da notare e' che se si inserisce una stringa con caratteri eguali verranno
considerati entrambi come indipendenti l'uno dall'altro generando
combinazioni duplicate..
il codice non e' completamente testato
<?php
function &gen($chars, $result = array(), $pre = '') {
  if (strlen($chars) == 2) {
    $result[] = $pre . $chars;
    $result[] = $pre . $chars{1} . $chars{0};
    return $result;
  } else if (strlen($chars) == 1) {
    return array($pre . $chars);
  } else if (strlen($chars) < 1) {
    return array("No chars to elaborate");
  }
  for ($i = strlen($chars)-1; $i >= 0; $i--) {
    $newChars = substr($chars, 0, $i) . substr($chars, $i+1);
    $newPre = $pre . $chars{$i};
    gen($newChars, &$result, $newPre);
  }
  return $result;
}
$res = gen('agtjd');
print_r($res);
?>
-- 
www.iuz-lab.info

 
perdonate l'intrusione e la furtivita' ma ho pochissimo tempo..
la funzione sotto postata genera tutte le combinazioni possibili esaminando
in modo ricorsivo una stringa e registrando le combinazioni in un array..
la scelta della stringa invece di un'array come vedete e' stata un'po'
sofferta ma come ho gia' detto non ho tempo a disposizione..
anche se uso la ricorsivita' il numero massimo delle funzioni richiamate
ricorsivamente non dovrebbe superare mai il numero pari alla lunghezza
della stringa meno uno..
da notare e' che se si inserisce una stringa con caratteri eguali verranno
considerati entrambi come indipendenti l'uno dall'altro generando
combinazioni duplicate..
il codice non e' completamente testato..



Ciao Setec, la tua soluzione per quanto corretta non va bene, quoto 
dall'autore:
--------------
ho 5 lettere: a g t j d, voglio far stampare tutte le combinazioni
(senza ripetizioni ovviamente).
--------------
La soluzione da te presentata, va bene solo in un caso e cioè soltanto nel 
momento in cui sono soddisfatte le seguenti condizioni:
1) La stringa sia di lunghezza fissa pari a 5 lettere;
2) Tutte le lettere componenti la stringa siano diverse;
Però come dice l'autore del thread, devono essere combinazioni senza 
ripetizione, per qui bisogna assumere che nella stringa data vi siano 
lettere ripetute più volte (e questo entra in contrasto con la condizione 2 
di cui sopra).
Inoltre l'autore fa un esempio con una stringa di 5 lettere, ma non dice 
espressamente che la stringa ha 5 lettere, per cui bisogna assumere che la 
stringa sia composta da n lettere (e anche questo entra in contrasto con la 
condizione 1 di cui sopra).
Ma a prescindere da questo, la soluzione da te presentata non va bene anche 
per il tipo di approccio, infatti, nel caso in cui anzichè 5, vi fossero 
state 1000 lettere, te avresti scritto il codice mettendo 1000 for uno 
dentro l'altro? spero proprio di no :)
In qualità di programmatore, mi sorprende che questa volta non ti sei messo 
nel caso peggiore e ti sei limitato a considerare solo quello migliore.
Infatti considerando una stringa di n lettere distinte per forza di cose, 
non possono esserci combinazioni con ripetizione.
Adesso comprenderai perchè ti dissi che una if non era sufficiente. Certo 
per la tua soluzione si, ma la tua soluzione alla luce delle considerazioni 
fatte sopra, non può considerarsi un "algoritmo" per questa classe di 
problemi in quanto prendi in considerazione come si è potuto ben vedere 
soltanto un caso particolare (5 lettere, lettere tutte distinte).
L'algoritmo per le combinazioni senza ripetizioni chiede che il numero di 
lettere contenute nella stringa non sia definito a priori e al tempo stesso 
considera che le lettere contenute nella stringa possono anche ripetersi.
Infatti, alla domanda: voglio conoscere tutte le combinazioni senza 
ripetizione che è possibile generare dalla parola PIPPO, la tua soluzione 
non diventa più applicabile.
Cooper.


 2) Tutte le lettere componenti la stringa siano diverse;
In base a quanto indicato da L'Ignorante nel suo post entrambe le
condizioni sonosoddisfatte.



L'Ignorante, chiede:
a) un algoritmo; il tuo non è un algoritmo ma una possibile soluzione;
b) combinazioni senza ripetizioni, considerando lettere tutte distinte, è 
normale che non vi siano ripetizioni, per cui bisognava NECESSARIAMENTE 
assumere il caso in cui vi fossero delle ripetizioni.
Certo per quello che chiedeva l'ignorante ha sbagliato a fare l'esempio, ma 
la richiesta: COMBINAZIONI SENZA RIPETIZIONI non lascia dubbi in quanto 
rafforzato dalla parola: OVVIAMENTE.
Inoltre hai considerato l'esempio di 5 lettere e se fossero state 
1000?avresti messo 1000 for uno dentro l'altro?
Con questo voglio dire, che la soluzione da te presentata per quanto 
funzionante sotto precise condizioni in realtà non è buona per  il tipo di 
approccio usato.
Non dimenticare che se anzichè 5 lettere ne avessi avute 3 soltanto anche 
tutte diverse, e quindi dall'array ne avrei tolto 2, alla fine l'output 
sarebbe stato con delle combinazioni ripetute più volte per ogni variante.


 L'Ignorante, chiede:
L'ignorante scrive: "Penso di aver quindi risolto cosi" proponendo una
soluzione che implementa una permutazione semplice di tre elementi. La
mia soluzione fornisce un metodo per visualizzare una permutazione
semplice di 5 elementi usando 5 for ed 1 if.


 
Ciao, dalla mia esperienza universitaria posso dirti che solitamente gli
algoritmi migliori per stampare permutazioni di stringhe sono gli
algoritmi di BackTracking, che migliorano le loro performance tanto più
il numero di elementi è alto.
dando una rapida occhiata alle tue esigenze ho scritto questo breve codice:
<?php
function back($vet,$sol,$presi,$k,$n)
{
/*Se k =n il vettore soluzione ha tutti gli elementi pieni e quindi può
essere stampato*/
if($k==$n) {
	foreach($sol AS $key=>$val) echo $val;
	echo "<BR>";
	}
else{
	for($i=0;$i<$n;$i++){		
		if($presi[$i]==0){
			$sol[$k+1]=$vet[$i];
			$presi[$i]=1;
			back($vet,$sol,$presi,$k+1,$n);
			$presi[$i]=0;
		}
	}
}
}
/* Inizializzazione array e invocazione funzione*/
//vettore con gli elementi da permutare
$vett=array("a","g","t","j","d");
//vettore soluzione
$sol=array();
//vettore degli elementi presi passo passo
$presi=array("0","0","0","0","0");
back($vett,$sol,$presi,0,5); //invocazione funzione
?>
Non so se questa sia la soluzione ottima e non ho controllato per bene
se genera ripetizioni (ma non mi sembra) comunque è sicuramente una
soluzione che ha un costo di esecuzione inferiore ai 5 for annidati
dell'altra soluzione, inoltre se ti dovessere servire le permutazioni su
100 elementi o su 1000 ti basterà cambiare i vettori $vett e $presi e
nella prima invocazione sostituire il numero 5 con il numero di elementi
che ti serve.
Spero di esserti stato utile, se ti dovesse servire qualche chiarimento
chiedi pure, ciao
Antonello



Ottimo, adesso però me lo studio un po'. Grazie


 il numero di elementi è alto.
[..]
facendo un piccolo test ho notato la funzione back() impiega molto piu'
tempo dell'algoritmo che ho postato..
ma ho dovuto modificare la tua funzione per rendere le due funzioni meglio
comprarabili a livello di prestazioni..
sotto trovi il risultato che ho ottenuto ed il codice che ho utilizzato per
un test piuttosto rudimentale..
back() = 31.
112014055252
 seconds
gen() = 0.13002610206604 seconds
<?php
function &gen($chars, $result = array(), $pre = '') {
  if (strlen($chars) == 2) {
    $result[] = $pre . $chars;
    $result[] = $pre . $chars{1} . $chars{0};
    return $result;
  } else if (strlen($chars) == 1) {
    return array($pre . $chars);
  } else if (strlen($chars) < 1) {
    return array("No chars to elaborate");
  }
  for ($i = strlen($chars)-1; $i >= 0; $i--) {
        $newChars = substr($chars, 0, $i) . substr($chars, $i+1);
    $newPre = $pre . $chars{$i};
    gen($newChars, &$result, $newPre);
  }
  return $result;
}
function back($vet, $sol, $presi, $k, $n, &$res) {
  if ($k == $n) {
    $res[] = implode(NULL, $sol);
  } else {
    for($i=0; $i < $n; $i++){
      if ($presi[$i] == 0){
        $sol[$k+1] = $vet[$i];
        $presi[$i] = 1;
        back($vet, $sol, $presi, $k+1, $n, &$res);
        $presi[$i] = 0;
      }
    }
  }
}
function microtime_float() {
  list($usec, $sec) = explode(" ", microtime());
  return ((float)$usec + (float)$sec);
}
$time_start = microtime_float();
 
$vett = array("1","2","3", "4", "5", "6", "7");
$sol = array();
$presi = array("0","0","0","0","0","0", "0");
$res = array();
back($vett, $sol, $presi, 0, 7, &$res);
 
$time_end = microtime_float();
$time = $time_end - $time_start;
 
echo "back() = $time seconds\n";
$time_start = microtime_float();
 
$res = gen('1234567');
$time_end = microtime_float();
$time = $time_end - $time_start;
 
echo "gen() = $time seconds\n";
?>
-- 
www.iuz-lab.info

[..]
Interessante, ma quando parlavo ti costi d'esecuzione non mi riferivo al
tempo materiale di esecuzione, sempre molto difficile da stimare, perché
a differenza di macchine, di architetture, di implementazioni delle
funzioni usate nel codice (substring e implode),e di carichi del
computer in quel momento, si possono ottenere risultati anche molto
diversi.
Avevo inoltre scritto che il backtracking ottiene valori tanto migliori
quanto più alto è il numero di elementi, difatti facendo circa 5 test
con il tuo codice ma su 14 elementi ho ottenuto valori per il mio
algoritmo intorno a 0.5112087726593 seconds, mentre il tuo è andato
sempre in timeout su 180 sec.
I costi di cui parlavo io infatti sono gli ordini asintotici di
grandezza delle funzioni (cioè stime su valori che tendono
all'infinito), e poi mi riferivo al codice dei 5 for annidati, per il
quale facendo un'analisi a spanne dell'ordine di grandezza asintotico i
5 for annidati sono
dell'ordine di o(n^5), che diventerebbero (n^n) se invece di 5 fossero n
elementi, mentre nel mio l'ordine è di o(n*n!) quindi su 10 elementi
quel codice costerebbe (10^10) > (10*10!), poi torno a ripetere che non
sono sicuro che sia l'ottimo, anche perché quello non è un algoritmo di
backtracking puro, difatti non sfrutta nessuna funzione di taglio per
ridurre le soluzioni ammissibili, ma genera solamente tutte le n!
soluzioni al problema.
Spero di aver chiarito, ciao
Antonello

[..]
Interessante, ma quando parlavo ti costi d'esecuzione non mi riferivo al
tempo materiale di esecuzione, sempre molto difficile da stimare, perché
a differenza di macchine, di architetture, di implementazioni delle
funzioni usate nel codice (substring e implode),e di carichi del
computer in quel momento, si possono ottenere risultati spesso molto
diversi.
Ci tengo a precisare che non voglio smentire i tuoi dati, il mio codice
potrebbe essere anche peggio di così, in realtà i costi di cui parlavo
sono gli ordini asintotici di grandezza delle funzioni, e poi mi
riferivo al codice dei 5 for annidati, per il quale facendo un'analisi a
spanne dell'ordine di grandezza asintotico i 5 for annidati sono
dell'ordine di o(n^5), che diventerebbero (n^n) se invece di 5 fossero n
elementi, mentre nella mia l'ordine è di o(n*n!) quindi su 10 elementi


Chiedo scusa mi è partito una vecchia copia del messaggio di risposta
del tutto involontariamente.
Ciao
Antonello

 Antonello
-- 
www.iuz-lab.info