Newsgroup: it.comp.lang.c
Titolo: Algoritmo del domino pse info

Ciao a tutti e scusate l'OT.
Vorrei creare (in C sotto Linux) un prg che simuli un
comportamento simile al domino.
Esemplificando: ho alcune "cartelle" che contengono
dei numeri a caso. Presi due numeri da due cartelle
diverse dovrei creare tutti i percorsi che mi permettano
di andare dal nr X della prima cartella al numero Y della ennesima.
Tali percorsi sono costituiti dai numeri in comune tra
cartelle (in qualsiasi ordine) che da X portano a Y. 
Cartella A: 1 2 3 4 
Cartella B: 4 5 6 7 
Cartella C: 7 8 9 10 50
Cartella D: 5 22 8 50 200
Dati 1 e 50 il percorso dovrebbe quindi essere 1-4-7-8-50,
1-4-7-50, 1-4-5-50. 
Il fatto che i numeri si possano ripetere, possono esistere
quindi, caso limite, tutte cartelle che contengano i numeri
X e Y o, all'estremo opposto pur esistendo X e Y in cartelle
distinte, non vi sia certezza che esista il collegamento,
mi ha gettato nel "panico". Una funzione ricorsiva probabilmente
andrebbe in stack overflow, pensate a 5-10000 cartelle!
Morale della lunghissima tirata: qualcuno puo' suggerirmi
un algoritmo o approccio per risolvere questo, per me
ostico, problema?
Vi ringrazio per la pazienza e per le eventuali risposte.
Ciao Francesco. 
 
<*>  Appunti Linux per il pinguino che non deve chiedere mai. <*>  
<*>  
http://www.pluto.linux.it
                                <*>

Voilà!!!
Sembrerebbe proprio NP!
Auguri...
--
Alessandro Monti
P.S.
Se invece ho capito male e basta 1 cammino, e non quello minimo, potrebbe
bastare l'algoritmo di Djkstra (o come cavolo si scrive).
--
Alessandro Monti

bastare l'algoritmo di Djkstra (o come cavolo si scrive).
Rileggendo il mio msg mi rendo conto di non essere stato per
nulla chiaro... purtroppo. Il guaio e' che mi servono proprio
tutti i percorsi possibili e i dati sono veramente tanti.
Avevo anche pensato di risolvere con gli array (tipo sistema
esperto) ma verrebbe fuori una matrice di dimensioni
abominevoli. Grazie ancora per l'interessamento!
Ciao Francesco


 [Previous]  [Next]   [Reply]   [Index]  [Home]  [Find]
     * Newsgroups: it.comp.lang.c
     * From: 
pos...@fortezza.paranor.sh
 (Francesco)
     * Subject: Algoritmo del domino pse info
     * Date: Tue, 28 Dec 1999 20:34:15 GMT
     * Organization: [Infostrada]
     * Reply-To: 
pos...@vallombrosa.net
     * User-Agent: slrn/
0.9.5.4
 (UNIX)
------------------------------------------------------------------------
  Ciao a tutti e scusate l'OT.
  Vorrei creare (in C sotto Linux) un prg che simuli un
  comportamento simile al domino.
  Esemplificando: ho alcune "cartelle" che contengono
  dei numeri a caso. Presi due numeri da due cartelle
  diverse dovrei creare tutti i percorsi che mi permettano
  di andare dal nr X della prima cartella al numero Y della ennesima.
  Tali percorsi sono costituiti dai numeri in comune tra
  cartelle (in qualsiasi ordine) che da X portano a Y.
  Cartella A: 1 2 3 4
  Cartella B: 4 5 6 7
  Cartella C: 7 8 9 10 50
  Cartella D: 5 22 8 50 200
  Dati 1 e 50 il percorso dovrebbe quindi essere 1-4-7-8-50,
  1-4-7-50, 1-4-5-50.
Puoi provare cosi', non so se fa propio al caso tuo e non garantisco nulla
sullo stack overflow:
#include<stdio.h>
#include<string.h>
#define	SIZE_ARR_TRACE		( sizeof(dArray)/sizeof(dArray[0]) )
#define DIM			5
#define	XNOTFOUND		999
	int	SeekX		();
	void	ParseRows	( int,int *,int );
	void	CheckDom	(int *,int *);
	void	InitDCA		(int*);
	void	PushDCA		(int *,int);
	int	CheckDCA	(int *,int);
	void	InitDRA		();
	void	PushDRA		(int);
	void	PopDRA		(int);
	int	CheckDRA	(int);
	int	dArray[][ DIM ] =
				{
				{ 1,2,3,4,99	},
				{ 4,5,6,7,98 	},
				{ 7,8,9,10,50 	},
				{ 5,22,8,50,200	}
				};
int	size = SIZE_ARR_TRACE;
int	dim  = DIM;
int	x = 0, y = 0;
int	trIndex = 0;
int	DupRowArray	[ SIZE_ARR_TRACE ];
void	main(int argc,char **argv)
{
	int	trArray		[ 4096 ];
	int	DupColArray	[ DIM ];
	int	xPos = 0;
	int	i = 0;
	if	( (argc < 3) || ( !(x=atoi(argv[1])) || !(y=atoi(argv[2])) ) )
		{
		printf( "Formato parametri di input errato\n" );
		exit(1);
		}
	if	( (xPos = SeekX()) == XNOTFOUND )
		{
		printf( "Parametro iniziale non trovato\n");
		exit(1);
		}
	InitDCA( DupColArray );
	for	( i=0;i<DIM;i++)
		{
		InitDRA( DupRowArray );
		if	( 	(dArray[xPos][i] != x) 	&&
				(dArray[xPos][i] != y)	&&
				(CheckDCA( DupColArray, dArray[xPos][i] ))
			)
			{
			memset( trArray, 0, (size*sizeof(int)) );
			trIndex = 0;
			trArray[trIndex++] = x;
			PushDRA( xPos );
			ParseRows( xPos,trArray,dArray[xPos][i] );
			PopDRA( xPos );
			}
		PushDCA( DupColArray, dArray[xPos][i] );
		}
}
/*------------------------------------------
	Ricerca la riga contenente l'elemento
	da cui iniziare.
--------------------------------------------*/
int	SeekX()
{
	int i = 0;
	int j = 0;
	for	( i=0;i<size;i++ )
		for ( j = 0;j<dim;j++ )
		    if ( dArray[i][j] == x )
			return i;
	return XNOTFOUND;
}
/*--------------------------------------------------
	Dato un elemento facente parte della
	catena cerca nella sua riga i numeri che possono
	far continuare la catena e quando li trova esegue
	ricorsivamente la stessa ricerca.
-----------------------------------------------------*/
void	ParseRows( int  xPos,int *trArray,int Elem )
{
	int i = 0;
	int j = 0;
	int z = 0;
	int w = 0;
	int appIndex = 0;
	int	DupColArray	[ DIM ];
	int	DupRowArray	[ SIZE_ARR_TRACE ];
	for ( w=0,i=++xPos;w<size;w++,i++)
	    {
		i = ( i == size )?0:i;
		if	( CheckDRA( i ) )
			{
			InitDCA( DupColArray );
			for    ( j=0;j<dim;j++)
			       {
			       if	(	(dArray[i][j] != x)	&&
						(dArray[i][j] != y)	&&
						(CheckDCA( DupColArray, dArray[i][j] ))
					)
				  {
				  if ( dArray[i][j] == Elem )
				     {
				     trArray[trIndex++] = Elem;
				     CheckDom( dArray[i],trArray );
				     PushDRA( i );
				     for (z=0;z<dim;z++)
					 {
					if	( dArray[i][z] != Elem )
						{
						appIndex = trIndex;
						ParseRows( i,trArray,dArray[i][z] );
						trIndex = appIndex;
						}
					 }
				     PopDRA( i );
				     }
				  }
			       PushDCA( DupColArray, dArray[i][j] );
			       }
			}
	    }
}
/*---------------------------------------------------
	Controlla se la catena e' finita
-----------------------------------------------------*/
void	CheckDom( int *dArray,int *trArray )
{
	int i = 0, j = 0;
	for	( i=0;( (i<dim) && (dArray[i] != y) );i++ );
	if	( dArray[i] == y )
		{
		printf("\nSequenza:");
		for ( j=0;j<trIndex;j++ )
		    if	(j > 0)
			{
			if	(trArray[j] != trArray[j-1] )
				printf("%d-",trArray[j]);
			}
			else
				printf("%d-",trArray[j]);
		printf("%d\n",y);
		}
}
/*------------------------------------------------
	Inizializza l'array DupColArray per
	il controllo di elementi duplicati
	nella stessa riga
--------------------------------------------------*/
void	InitDCA( int *DCArray )
{
	int i = 0;
	for	( i=0;i<DIM;i++ )
		DCArray[i] = -1;
}
/*------------------------------------------------
	Salva nell'array DupColArray l'elemento
	corrente
--------------------------------------------------*/
void	PushDCA( int *DCArray,int Elem )
{
	int i = 0;
	for	( i=0;( (i < DIM) && (DCArray[i] != -1) );i++ );
	if	( i < DIM)
		DCArray[i] = Elem;
}
/*--------------------------------------------------
	Controlla se l'elemento e' un doppione,
	in caso affermativo non viene elaborato
----------------------------------------------------*/
int	CheckDCA	(int *DCArray,int Elem )
{
	int i = 0;
	for	( i=0;( (i < DIM) && (DCArray[i] != Elem) );i++ );
	if	( i < DIM)
		return 0;
	else
		return 1;
}
/*------------------------------------------------
	Inizializza l'array DupRowArray,che serve a
	controllare che la riga presa in considerazione
	non faccia gia' parte della catena
--------------------------------------------------*/
void	InitDRA()
{
	int i = 0;
	for	( i=0;i<SIZE_ARR_TRACE;i++ )
		DupRowArray[i] = -1;
}
/*------------------------------------------------
	Salva nell'array DupRowArray la riga dell'
	elemento corrente
--------------------------------------------------*/
void	PushDRA(int Elem )
{
	int i = 0;
	for	( i=0;( (i < SIZE_ARR_TRACE) && (DupRowArray[i] != -1) );i++ );
	if	( i < SIZE_ARR_TRACE)
		DupRowArray[i] = Elem;
}
/*------------------------------------------------
	Estrae dall'array DupRowArray la riga dell'
	elemento corrente,per evitare che la funzione
	di livello superiore si trovi con lo stack
	di righe pieno e non sia piu' in grado di
	ricercare nuove catene
-------------------------------------------------*/
void	PopDRA(int Elem )
{
	int i = 0;
	for	( i=0;(DupRowArray[i] != Elem);i++ );
		DupRowArray[i] = -1;
}
/*--------------------------------------------------
	Controlla se l'elemento dell'array DupRowArray
	e' presente,in caso affermativo la riga
	corrispondente non viene elaborata
----------------------------------------------------*/
int	CheckDRA	(int Elem )
{
	int i = 0;
	for	( i=0;( (i < SIZE_ARR_TRACE) && (DupRowArray[i] != Elem) );i++ );
	return ( i < SIZE_ARR_TRACE)?0:1;
}
Ivan Molella
--
Posted from 
mta02-acc.tin.it
 [212.216.176.33]
via Mailgate.ORG Server - 
http://www.mailgate.org

Correzione:
...............
..............
void CheckDom( int *dArray,int *trArray )
{
 int i = 0, j = 0;
 for ( i=0;( (i<dim) && (dArray[i] != y) );i++ );
-------------------------------------------------
if ( dArray[i] == y )    ERRATO
--------------------------------------------------
 if ( ( i < dim ) && (dArray[i] == y) )    ESATTO
--------------------------------------------------
................
................




Questa modifica evita il caso di sequenze duplicate a causa del ripetersi
di uno stesso numero sulla stessa cartella(riga).I numeri tra parentesi in
output indicano le cartelle x tracciare il percorso della sequenza,la
matrice non e' piu' statica ma dinamica e la dimensione e' stabilita da argv[3]
e argv[4].
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define XNOTFOUND               999
	int	**CreaMat	(int,int);
        int     SeekX           ();
        void    ParseRows       ( int,int *,int *,int );
        void    CheckDom        (int *,int *,int *);
        void    InitDCA         (int*);
        void    PushDCA         (int *,int);
        int     CheckDCA        (int *,int);
        void    InitDRA         ();
        void    PushDRA         (int);
        void    PopDRA          (int);
        int     CheckDRA        (int);
/*
        int     dArray[][ DIM ] =
                                {
                                { 1,2,3,4,99    },
                                { 4,5,6,7,98    },
                                { 7,8,9,10,50   },
                                { 5,22,8,50,200 }
                                };
*/
int	**dArray = NULL;
int     size = 0;
int     dim  = 0;
int     x = 0, y = 0;
int     trIndex = 0;
int     *DupRowArray = NULL;
void    main(int argc,char **argv)
{
        int     trArray         [ 4096 ];
        int     trArrayRow      [ 4096 ];
        int     *DupColArray = NULL;
        int     xPos = 0;
        int     i = 0;
	int	xDim =0,yDim = 0;
        if      (	(argc < 5) || 
			(!(x=atoi(argv[1])) || !(y=atoi(argv[2])))||
			(!(xDim=atoi(argv[3])) || !(yDim=atoi(argv[4])))
		)
                {
                printf( "Formato parametri di input errato\n" );
                printf( "Usage: %s <ValoIni> <ValoFine> <Dimx>
<Dimy>\n",argv[0] );
                exit(1);
                }
	if	( (dArray = CreaMat(yDim,xDim)) == NULL )
		exit(1);
	size = yDim;
	dim  = xDim;
	if	( (DupRowArray = (int*)malloc(size * sizeof(int))) == NULL )
		{
		printf( "Errore in allocazione DRArray\n");
		exit(1);
		}
	if	( (DupColArray = (int*)malloc(dim * sizeof(int))) == NULL )
		{
		printf( "Errore in allocazione DCArray\n");
		exit(1);
		}
        if      ( (xPos = SeekX()) == XNOTFOUND )
                {
                printf( "\nParametro iniziale non trovato\n");
                exit(1);
                }
        InitDCA( DupColArray );
        for     ( i=0;i<dim;i++)
                {
                InitDRA( DupRowArray );
                if      (       (dArray[xPos][i] != x)  &&
                                (dArray[xPos][i] != y)  &&
                                (CheckDCA( DupColArray, dArray[xPos][i] ))
                        )
                        {
                        memset( trArray, 0, (size*sizeof(int)) );
                        memset( trArrayRow, 0, (size*sizeof(int)) );
                        trIndex = 0;
                        trArray[trIndex] = x;
                        trArrayRow[trIndex++] = xPos;
                        PushDRA( xPos );
                        ParseRows( xPos,trArrayRow,trArray,dArray[xPos][i]
);
                        PopDRA( xPos );
                        }
                PushDCA( DupColArray, dArray[xPos][i] );
                }
	free( DupColArray );
	free( DupRowArray );
}
/*------------------------------------------
        Ricerca la riga contenente l'elemento
        da cui iniziare.
--------------------------------------------*/
int     SeekX()
{
        int i = 0;
        int j = 0;
        for     ( i=0;i<size;i++ )
                for ( j = 0;j<dim;j++ )
                    if ( dArray[i][j] == x )
                        return i;
        return XNOTFOUND;
}
/*--------------------------------------------------
        Dato un elemento facente parte della
        catena cerca nella sua riga i numeri che possono
        far continuare la catena e quando li trova esegue
        ricorsivamente la stessa ricerca.
-----------------------------------------------------*/
void    ParseRows( int  xPos,int *trArrayRow,int *trArray,int Elem )
{
        int i = 0;
        int j = 0;
        int z = 0;
        int w = 0;
        int appIndex = 0;
        int     *DupColArray = NULL;
        int     *DupColzArray = NULL;
	if	( (DupColArray = (int*)malloc(dim * sizeof(int))) == NULL )
		{
		printf( "Errore in allocazione array\n");
		exit(1);
		}
	if	( (DupColzArray = (int*)malloc(dim * sizeof(int))) == NULL )
		{
		printf( "Errore in allocazione array\n");
		exit(1);
		}
        for ( w=0,i=++xPos;w<size;w++,i++)
            {
                i = ( i == size )?0:i;
                if      ( CheckDRA( i ) )
                        {
                        InitDCA( DupColArray );
                        for    ( j=0;j<dim;j++)
                               {
                               if       (       (dArray[i][j] != x)
&&
                                                (dArray[i][j] != y)
&&
                                                (CheckDCA( DupColArray,
dArray[i][j] ))
                                        )
                                  {
                                  if ( dArray[i][j] == Elem )
                                     {
                                     trArray[trIndex] = Elem;
                                     trArrayRow[trIndex++] = i;
                                     CheckDom(
dArray[i],trArrayRow,trArray );
                                     PushDRA( i );
				     InitDCA( DupColzArray );
                                     for	(z=0;z<dim;z++)
						{
						if	(	(dArray[i][z] != Elem)	&&
								(CheckDCA( DupColzArray, dArray[i][z] ))
					 		)
                                               	 {
                                               	 appIndex = trIndex;
                                               	 ParseRows(
i,trArrayRow,trArray,dArray[i][z] );
                                               	 trIndex = appIndex;
                                               	 }
						PushDCA( DupColzArray, dArray[i][z] );
                                         }
                                     PopDRA( i );
				     trIndex--;
                                     }
                                  }
                               PushDCA( DupColArray, dArray[i][j] );
                               }
                        }
            }
	    free( DupColArray );
 
}
/*---------------------------------------------------
        Controlla se la catena e' finita
-----------------------------------------------------*/
void    CheckDom( int *dArray,int* trArrayRow,int *trArray )
{
        int i = 0, j = 0;
        for     ( i=0;( (i<dim) && (dArray[i] != y) );i++ );
        if      ( (i<dim) && (dArray[i] == y) )
                {
                printf("\nSequenza:");
                for	( j=0;j<trIndex;j++ )
                    	printf("%d(%d)-",trArray[j],trArrayRow[j]);
                printf("%d\t",y);
                }
}
/*------------------------------------------------
        Inizializza l'array DupColArray per
        il controllo di elementi duplicati
        nella stessa riga
--------------------------------------------------*/
void    InitDCA( int *DCArray )
{
        int i = 0;
        for     ( i=0;i<dim;i++ )
                DCArray[i] = -1;
}
/*------------------------------------------------
        Salva nell'array DupColArray l'elemento
        corrente
--------------------------------------------------*/
void    PushDCA( int *DCArray,int Elem )
{
        int i = 0;
        for     ( i=0;( (i < dim) && (DCArray[i] != -1) );i++ );
        DCArray[i] = ( i < dim)?Elem:DCArray[i];
}
/*--------------------------------------------------
        Controlla se l'elemento e' un doppione,
        in caso affermativo non viene elaborato
----------------------------------------------------*/
int     CheckDCA        (int *DCArray,int Elem )
{
        int i = 0;
        for     ( i=0;( (i < dim) && (DCArray[i] != Elem) );i++ );
        return ( i < dim)?0:1;
}
/*------------------------------------------------
        Inizializza l'array DupRowArray,che serve a
        controllare che la riga presa in considerazione
        non faccia gia' parte della catena
--------------------------------------------------*/
void    InitDRA()
{
        int i = 0;
        for     ( i=0;i<size;i++ )
                DupRowArray[i] = -1;
}
/*------------------------------------------------
        Salva nell'array DupRowArray la riga dell'
        elemento corrente
--------------------------------------------------*/
void    PushDRA(int Elem )
{
        int i = 0;
        for     ( i=0;( (i < size) && (DupRowArray[i] != -1) );i++ );
        if      ( i < size)
                DupRowArray[i] = Elem;
}
/*------------------------------------------------
        Estrae dall'array DupRowArray la riga dell'
        elemento corrente,per evitare che la funzione
        di livello superiore si trovi con lo stack
        di righe pieno e non sia piu' in grado di
        ricercare nuove catene
-------------------------------------------------*/
void    PopDRA(int Elem )
{
        int i = 0;
        for     ( i=0;(DupRowArray[i] != Elem);i++ );
                DupRowArray[i] = -1;
}
/*--------------------------------------------------
        Controlla se l'elemento dell'array DupRowArray
        e' presente,in caso affermativo la riga
        corrispondente non viene elaborata
----------------------------------------------------*/
int     CheckDRA        (int Elem )
{
        int i = 0;
        for     ( i=0;( (i < size) && (DupRowArray[i] != Elem) );i++ );
        return ( i < size)?0:1;
}
int	**CreaMat(int xDim,int yDim)
{
	int i = 0;
	int j = 0;
	int **pArray = NULL;
	if	( (pArray = (int**)malloc(yDim * sizeof(int *))) == NULL )
		{
		printf( "Errore in allocazione matrice\n");
		return pArray;
		}
	else
		{
		for	( i=0;i<yDim;i++)
			if	( (pArray[i] =(int*)malloc(xDim*sizeof(int))) == NULL )
				{
				printf( "Errore in allocazione array\n");
				return (int**)pArray[i];
				}
		for	( i=0;i<yDim;i++)
			{
			printf( "\n");
			srand(i);
			for	( j=0;j<xDim;j++)
				printf("%d ",(pArray[i][j] = (rand() / (RAND_MAX / 10 + 1))) );
			}
		}
	return	pArray;


 ha scritto:
