Newsgroup: it.comp.lang.c
Titolo: Cerco urgentemente algoritmo C

Sto cercando un algoritmo C che, ,dato un array a n valori booleani, lasci
invariate le posizioni contenenti zero(false), mente per le altre generi
tutte le possibili combinazioni.Mi spiego meglio con un esempio:
    n=3             pos0  pos1  pos2 
                     1     0     1
Dato questo vettore l'algoritmo dovrebbe generare i seguenti 3 vettori
                     1     0     0   
		     0     0     1	
                     0     0     0
                   ( 1     0     1 ) <- l'abbiamo gia' 
dove la posizione 1 e' rimasta invariata e le alte hanno assunto di volta
in volta i possibili valori 0/1.
Ringrazio gia' da ora chi possa essermi utile nella mia ricerca.
Fabio Mascelloni.

tutte le possibili combinazioni.Mi spiego meglio con un esempio:
Ti suggerisco:
1. conta quante posizioni sono non-zero, sia questo il valore K
2. genera i 2-alla-K valori richiesti "contando in binario" da 0 a
     2-alla-K-meno-1
    -- per ogni valore cosi` generato, "spalma" i bit nelle
        posizioni non-zero dell'array originale
OK, questo non e` in C, bensi` in pseudo-codice.  Per
tradurre in C possiamo ipotizzare ad esempio di generare
nella fase 1 un array ausiliario che per ogni posizione
non-zero dice il corrispondente indice nell'array originale.
Permettimi per chiarezza di dichiarare le variabili solo
via via che le inizializzo, come in C++: dovrai poi solo
riportare tutte le dichiarazioni all'inizio...:
    void perFM(char array_org[], int n) {
        if(n<0) esci_con_errore();
        int nonzeri = 0;
        int i;
        for(i=0; i<n; ++i)
            if(array_org[i]) ++nonzeri;
        int* aux = malloc(sizeof(int)*nonzeri);
        int j;
        for(i=j=0; i<n; ++i)
            if(array_org[i]) aux[j++] = i;
Adesso possiamo generare l'array su cui fare le
combinazioni e inizializzarlo alla prima (tutti zeri):
        char* combi = malloc(n);
        for(;;) {
            fatta_combinazione(combi, n)
supponendo che la fatta_combinazione sia la
funzione che devi chiamare per ciascuna
combinazione generata.
Adesso incrementiamo il numero binario
rappresentato implicitamente nell'array combi:
            j=0;
            while(j<nonzeri) {
                char* p = combi+aux[j];
                if(0==*p) {
                    *p = 1; break;
                } else {
                    *p = 0; ++j;
                }
            }
            if(j==nonzeri) break;
        }
    }
Non ho testato questo codice, quindi, mi
raccomando, provalo!-)
Alex

 tutte le possibili combinazioni.
Potresti fare una cosa del genere (poniamo che n sia il numero delle
posizioni del tuo array):
1. Usare come base per la generazione un numero (int o long a seconda di
n).
2. Far variare questo numero da 0 fino a 2 alla n.
3. Ognuno di questi valori lo trasformi in binario mettendo ogni cifra
in un elemento di un array con numero di elementi pari a quello di
partenza.
4. Controlli se la combinazione ottenuta soddisfa i requisiti e cioč se
contiene gli zeri al posto giusto (lo confronti con l'array di
partenza).
5. Se la combinazione č valida la memorizzi in una matrice e cosě via.
Spero di essere stato chiaro.
EMG

Spero di essere stato chiaro.
Secondo me si`, e anche perfettamente corretto, ma il tempo di
esecuzione potrebbe essere un problema, essendo O(2**n),
cioe` proporzionale a 2 alla n [lunghezza totale dell'array di
partenza], mentre con l'algoritmo che ho postato ieri si dovrebbe
girare in tempo O(2**nonzeri) cioe` proporzionale a 2 alla NZ
(NZ<=n, essendo il numero di non-zeri nell'array di partenza).
Usare un vero numero, inoltre, puo` dare problemi se n>32 (o
comunque del numero di bit agevolmente supportati sulla
macchina); l'algoritmo che ho postato ieri, in teoria, funziona
invece per qualsiasi array rappresentabile sulla macchina (sara`
naturalmente lentissimo se NZ e` molto elevato, ma questo e`
inevitabile, poiche` 2**NZ e` proprio il numero di combinazioni
da generare, quindi O(2**NZ) un limite inferiore all'efficienza
di qualsiasi algoritmo risolva questo problema).  OK, immagino
che questa sia piu` che altro una preoccupazione teorica!-)
Alex

tutte le possibili combinazioni.
Secondo me, l'approccio piu' semplice e' quello ricorsivo :
#include <stdio.h>
typedef unsigned char BOOLEAN ;
void reset_start_array( BOOLEAN a[] )
{
     while (*a)
     {
	   *a = (*a == '0') ? 'x' : '0';
	   ++a;
     }
}
void put_combination( BOOLEAN a[] )
{
    while (*a)
    {
	  if ( *a == 'x')
	     putchar('0');
	  else
	     putchar( *a );
	  ++a;
    }
    printf("\n");
}
void get_combination( BOOLEAN a[], int level )
{
	if (*a)
	{
	   if (*a == 'x') get_combination( a+1, level+1 );
	   else
	   {
	      *a = '0'; get_combination( a+1, level+1 );
	      *a = '1'; get_combination( a+1, level+1 );
	   }
	}
	else put_combination( (a - level) );
}
void main( void )
{
    BOOLEAN bool_array[8] = "01011001";
    reset_start_array( bool_array );
    get_combination( bool_array, 0 );
}
Andrea, mica uno qualunque...
--------------------------------------------------
"Ho cambiato signature, si vede ?"
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

     BOOLEAN bool_array[8] = "01011001";
Hai scritto 8 ma l'inizializzatore č da 9. Non ricordo cosa succede in
questi casi al '\0' finale. Per sicurezza sarebbe meglio inizializzare
elemento per elemento.
EMG

Hai scritto 8 ma l'inizializzatore h da 9.
Giusto, "distraction error"  :) ...
Skyscraper
----------------------------------------------------------------
"Sopra il camper la capra campa, sotto il camper la capra crepa"


Andrea Laforgia (andrea_...@CHITIHACHIESTONIENTEbigfoot.com) wrote:
: Un bel giorno, tutt'a un tratto Fabio Mascelloni si mise a scrivere :
: >Sto cercando un algoritmo C che, dato un array a n valori booleani, lasci
: >invariate le posizioni contenenti zero(false), mentre per le altre generi
: >tutte le possibili combinazioni.
: Secondo me, l'approccio piu' semplice e' quello ricorsivo :
[ snip ]
Pero' e' davvero necessario marcare con 'x' gli zeri ?
Ho riscritto il programmino cosi', e mi pare che vada:
------------------------------------------------------
#include <stdio.h>
typedef unsigned char BOOLEAN;
void get_combination(BOOLEAN a[], int level)
{
        if (a[level]) {
                if (a[level] == '0') {
                        get_combination(a, level + 1);
                } else {
                        a[level] = '0';
                        get_combination(a, level + 1);
                        a[level] = '1';
                        get_combination(a, level + 1);
                }
        } else {
                printf("%s\n", a);
        }
}
int main()
{
        BOOLEAN bool_array[] = "01011001";
        get_combination(bool_array, 0);
        return 0;
}
------------------------------------------------------
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

Ho riscritto il programmino cosi', e mi pare che vada:
[snip]
Credo che sia la versione migliore che si possa considerare.
