Newsgroup: it.comp.lang.c
Titolo: Calcolo combinatorio ricorsivo

Ciao a tutti!
mi servirebbero i sorgenti per stampare le Permutazioni
di n numeri 1,2,..,n e delle Disposizioni semplici degli
stessi a k a k (cioe' D_n,k che pero' gli americani chiamano
"Permutations nPk").
Credo che dovrebbero essere delle funzioni ricorsive, ma se
non lo sono vanno bene ugualmente.
 
Grazie a chi me li da' o mi da' un link dove li trovo, io
non li ho trovati da nessuna parte :-(  ciao!
 
-- 
Saluti,
Guido
 


Googla meglio.
Oppure, visto che probilmente e' un compito per scuola, sporcati un po' le mani.
 
Poi se hai problemi vieni pure a chiedere qua, ma qua dentro difficilmente troverai la pappa pronta.
 
Ciao Jack

difficilmente troverai la pappa pronta.
 
Grazie per l'attenzione. Ecco i problemi.
 
1) gcc con Linux mi da' molti warnings e un errore nella funzione
Combina. Io non sono in grado d'individuarlo, inoltre per motivi
contingenti e personali non mi e' possibile approfondire il C
(altrimenti non avrei chiesto aiuto qui).
=========================== codice 1 ============>
#include <string.h>
 
int Combinazione[10];
int NrElem;
int qta;
 
void mostraComb(char Elementi[])
{
int i = 0;
for(i = 0; i < 3; i++)
{
printf(" %c", Elementi[Combinazione[i]]);
}
printf("\n");
}
 
void Combina(char Elementi[], int k, int Primo)
{
if(k == 0 || k == NrElem)
{
printf("\nOttenuta una combinazione: ");
mostraComb(Elementi);
return;
}
for (int j=Primo; j<NrElem-k+1; j++)
{
Combinazione[qta] = j;
qta++;
Combina(Elementi, k-1, j+1);
qta--;
}
}
 
int main()
{
char Elementi[10];
int Gruppi = 3;
int i;
qta=0;
printf("\nInserire gli elementi da combinare: ");
gets(Elementi);
NrElem = strlen(Elementi);
i=0;
Combina(Elementi, Gruppi, i);
system("PAUSE");
return 0;
}
<===================== 1 fine =====================
 
 
 
2) Manca la funzione main(). Impensabile per me scriverla.
Peccato, perche' questo sembra un ottimo codice (ma a giudizio
mio di incompetente! ma ho visto la brevita' e poi tutti i
puntatori... insomma secondo me meno lo capisco e migliore e').
========================= codice 2 ==================>
#include <stdio.h>
 
int perm_sempl(int pos, int *val, int *sol, int *mark, int n, int count)
{
int j;
if(pos>=n)
{
for(j=0; j<n; j++)
printf("%d ", sol[j]);
printf("\n");
return count+1;
}
for(j=0; j<n; j++)
{
if(mark[j]==0)
{
mark[j]=1;
sol[pos]=val[j];
count=perm_sempl(pos+1, val, sol, mark, n, count);
mark[j]=0;
}
}
return count;
}
<====================== fine 2 ==================
 
 
3) Eccone uno che gira perfettamente, ma e' per le Pn e non ci
riesco a trasformarlo anche per le Dn,k. Non ci riesco perche' ho
provato in tutti i modi a cercare di capire la permute() ma non so come
possa fare ad arrivare ad eseguire la seconda volta la riga:
temp=a[i];a[i]=a[j];a[j]=temp;
percio' non posso modificarla aggiungendo un k diverso da n.
============================ codice 3 buono ======>
#include <stdio.h>
#define lunghezza 99   /* messo io */
 
int enne;
/* int a[10];          cambiato io */
int a[lunghezza];      /* messo io */
 
void permute(int i, int N);
int main()
{
scanf("%d", &enne);
  const int N=enne;
  int i;
  for (i=0;i<N;i++)
    a[i]=i+1;
  permute(0,N);
  return 0;
}
 
void permute(int i, int N)
{
   int j,temp;
   if (i==N-1) {
     for (j=0;j<N;j++)
       printf("%3d",a[j]);
     printf("\n");
   }
   else
     for (j=i;j<N;j++){
       temp=a[i];a[i]=a[j];a[j]=temp;
       permute(i+1,N);
       temp=a[i];a[i]=a[j];a[j]=temp;
     }
}
<======================= fine 3 ==========
 
 
-- 
Saluti,
Guido
 

 Combina.
 
Ora dovrebbe compilare senza warnings né errori. Se ci sono ancora 
messaggi riportali. Per vedere cosa ho modificato confronta questo 
codice con quello da te riportato.
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int Combinazione[10];
int NrElem;
int qta;
 
void mostraComb(char Elementi[])
{
int i;
for(i = 0; i < 3; i++)
{
printf(" %c", Elementi[Combinazione[i]]);
}
printf("\n");
}
 
void Combina(char Elementi[], int k, int Primo)
{
int j;
if(k == 0 || k == NrElem)
{
printf("\nOttenuta una combinazione: ");
mostraComb(Elementi);
return;
}
for (j=Primo; j<NrElem-k+1; j++)
{
Combinazione[qta] = j;
qta++;
Combina(Elementi, k-1, j+1);
qta--;
}
}
 
int main()
{
char Elementi[10];
int Gruppi = 3;
int i;
qta=0;
printf("\nInserire gli elementi da combinare: ");
gets(Elementi);
NrElem = strlen(Elementi);
i=0;
Combina(Elementi, Gruppi, i);
system("PAUSE");
return 0;
}
 
EMG
 
--
http://www.emagsoftware.it
 
http://www.emagsoftware.it/emgmusic
 
http://www.emagsoftware.it/spectrum
 
http://www.emagsoftware.it/tbosg
 

codice con quello da te riportato.
 
Grazie! adesso l'ho compilato e gira, ma:
1) mi da' questi avvisi:
---------------------------------
emg.c: In function ‘main’:
emg.c:44:1: warning: ‘gets’ is deprecated (declared at
/usr/include/stdio.h:638) [-Wdeprecated-declarations]
 gets(Elementi);
 ^
/tmp/ccCYe7q8.o: nella funzione "main":
emg.c:(.text.startup+0x2d): attenzione: the `gets' function is dangerous
and should not be used.
---------------------------
 
 
2) Il programma (tu non c'entri) dev'essere non per le
disposizioni (ma neanche per le combinazini come dice),
perche' questo e' l'output:
 
Inserire gli elementi da combinare:
1 2 3
 
Ottenuta una combinazione:  1   2
 
Ottenuta una combinazione:  1
 
Ottenuta una combinazione:  1   3
 
Ottenuta una combinazione:  1 2
 
Ottenuta una combinazione:  1 2 3
 
Ottenuta una combinazione:  1   3
 
Ottenuta una combinazione:    2
 
Ottenuta una combinazione:    2 3
 
Ottenuta una combinazione:      3
 
Ottenuta una combinazione:  2   3
----------------------
 
 
3) Mi da' anche questo allo stderr:
sh: 1: PAUSE: not found
 
che pero' secondo me da reminescenze del DOS dev'essere non per
Linux, quindi basta togliere l'istruzione (o modificarla con slip?).
 
 
-- 
Saluti,
Guido
 

 for (int j=Primo; j<NrElem-k+1; j++)
 
 
-- 
Saluti,
Guido
 

Il 29/5/2017 09:49:38 guido84 scrisse:

Be' le comb non lo trovo, in compenso trovo incredibile questa
differenza di tempi per i 3.628.800 di perm di 10 numeri-oggetti:
progr1: 5.419 secondi (col sorgente che ho postato ieri)
progr2: 0.248 secondi (ma e' con c99, che non so neanche cosa vuol dire)
progr3: 4.327 secondi
 
Mah... il fatto e' che bisogna saper preogrammare!
 
-- 
Saluti,
Guido
 

 Mah... il fatto e' che bisogna saper preogrammare!
 
Ovvio.


Ovvio.
 
A tutti?
 
-- 
Saluti,
Guido
 

 A tutti?
 
Hai ragione, no, non è ovvio a tutti... :-(



 
Non vorrei dire eresie perché ciò che affermo deriva da reminiscenze e 
non ho trovato conferme in rete per cui lo dico e pure lo nego :) :
 
l'opzione -lm serve per includere, durante il link, le librerie 
matematiche; cosa che potrebbe significare l'utilizzo di librerie 
matematiche alterative che si sostituiscono all'utilizzo del 
coprocessore matematico. Non dovrebbe essere utilizzata.
 


no.
 
la roba in "math.h" deve essere linkata, e viene fatto con -lm
 
Ciao Jack

Scusa ma non sono molto pratico di Linux e gcc e ogni compilatore ha i 
[snip]
 
OK grazie! Poi per il programma adesso l'ho trovato, ciao!
 
-- 
Saluti,
Guido
 


no


sorry... me ne son perso un pezzo :-)
 
https://stackoverflow.com/questions/38604278/c-libm-a-not-needed-to-be-linked-when-compiling
 
 
 

Il 31/5/2017 09:43:57 Jack scrisse:

Infatti quella command line che ho usato l'avevo presa da un post
proprio tuo, era di uno o due anni fa, percio' abbastanza recente,
su googlegruppi.
 
-- 
Saluti,
Guido
 


l'ahi letto tutto il post o cosa?
 
Dipende dal compilatore, se ha le funzioni matematiche builtin o, meglio, se linka automaticamente la libm (come fa per la libc).
 
Quindi in generale dire che -lm non serve e' sbagliato. Se il compilatore la linka in automatico, aggiungere il flag non comporta nessun problema.
D'altra parte se non lo metti e il compilatore non lo fa in automatico (o disattivi i builtin per qualche motivo) avrai errore.
Se vuoi un codice portabile (makefile compreso) -lm va messo.
 
Ciao Jack

 è _no_, non _deve_ col gcc (di cui si parlava).
 
di nuovo no.
uso versioni del gcc (per processori specifici) dove DEVE essere linkata per forza (se usi roba nella math.h chiaramente), non lo fa lui in automatico.
Anche perche' ho due versioni diverse di libm, una standard e una "fast-math" (quindi -lm e -lmfast) che hanno le stesse funzioni (quindi stesso header) ma implementate in modo differente.
 
Quindi per concludere il tuo "-lm non dovrebbe essere usato" a cui ho risposto con un secco no, e' semplicemente sbagliato.
 
La risposta giusta e': -lm serve a linkare la libm (math.h), spesso non e' necessario perche' il compilatore (linker) lo fa in automatico come per la libc (cfr. il tuo link a stackoverflow), ma usarlo non comporta problemi.
 
Poi sei liberissimo dimostrarmi il contrario, e cioe' che:
 
gcc pippo.c -lm -o sticazzi
gcc pippo.c -o sticazzi
 
non creano lo stesso eseguibile (indipendentemente se pippo.c usi la math.h o meno).
Sempre che nel secondo caso il linker non si incazzi perche' non hai usato -lm.
 
Ciao Jack

è _no_, non _deve_ col gcc (di cui si parlava).
 
Eccheppalle! e' tutta colpa come al solito della m$ e in
particolare del tuo NT, vedi un po' che succede se tolgo -lm:
------------------
/tmp/ccFUDoK2.o: nella funzione "main":
logdieci.c:(.text.startup+0x3b): riferimento non definito a "log"
collect2: error: ld returned 1 exit status
------------
e poi ESCE e NON compila.
 
 
Il sorgente e' questo prova.c:
====================
#include <stdio.h>
#include <math.h>
 
double lognat, enne;
double log(double x);
 
main()
{
printf("\nIntrodurre il numero: ");
scanf("%lf", &enne);
lognat = log(enne);
printf("%lf\n", lognat);
 
return 0;
}
==================
 
-- 
Saluti,
Guido
 


Hei... non ti ci mettere anche tu. L'ho scritto nella risposta. Aggiungi 
nel tuo codice:
0.0;
e funzionerà.
 


ma te sei fuori! math.h non è che un pezzo di codice incluso nei 
sorgenti dove tra le altre cose sono definiti i prototipi delle funzioni 
matematiche ma ci puoi legate una qualsiasi libreria contenente funzioni 
compatibili come parametri e valore di ritorno.
Tu stai cercando fedeli non becessiti di verità!
 

 Dipende dal compilatore, se ha le funzioni matematiche builtin o, meglio, se linka automaticamente la libm (come fa per la libc).
 
Faccio notare che nel sorgente non ci sono floating point, la matematica 
si limita agli interi.

e funzionerà.
 
L'ho provato ad aggiungere, dove lo metto lo metto, mi da' sempre
"error" ed esce.
 
Ma poi non capisco il problema tuo: in Linux e' OBBLIGATORIO dare
il path delle librerie - non c'e' altro d'aggiungere sulla questione.
 
E poi perche' dovrei preferire mettere "0.0;" invece del path?
 
Il coprocessore NON c'entra NULLA, questo lo so anch'io che sono
principiante. E' Ld, il linker di Gcc, che non trova le librerie.
 
Si vede che la m$ ha provveduto diversamente per agevolare i suoi
utenti prediletti deboli e indifesi, ma non puoi pretendere che
il mondo giri intorno a lei.
 
-- 
Saluti,
Guido
 


...ad esempio così:
int main()
{
    double enne = 0.0;
    .
    .
    .
}
Il problema mio? Ma io non ho problemi; semplicemente quando l'op ha 
scritto '_deve_', siccome è una cosa non vera, mi sono permesso di farlo 
notare. Quasi tutti i compilatori, quando vedono utilizzare dati in 
virgola mobile, includono una libreria matematica. Nella fattispecie, il 
gcc ne utilizza una versione composta da built-in function che magari 
non è la migliore ma sicuramente produce file eseguibili dalle 
dimensioni più contenute. Potresti anche volerne utilizzare una ottenuta 
da terze parti e non quella standard e siccome il parametro -lm utilizza 
la 'fast link table' e cioè cerca nei percorsi che hai dichiarato una 
libreria che inizia per 'lib' e finisce per quel che hai messo dopo la 
'l' (in questo caso libm.a) ti troveresti, in questo caso errori del 
linker per entry duplicate. Quindi no, l'opzione -lm non _deve_ esser 
messa, eventualmente _può_.
Approfitterei anche per far notare che la portabilità dipende da come 
scrivi il codice sorgente e, sicuramente, non dalle librerie con cui 
linki il codice oggetto compilato. Anzi.

linki il codice oggetto compilato. Anzi.
 
 
-- 
Saluti,
Guido
 

 re
strano... è pur vero che sto usando una versione per dos però:
 
$> gcc --version
gcc (tdm-1) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
 
[D:\Users\jak]
 
$> type pp.c
#include <stdio.h>
#include <math.h>
 
int main()
{
         double enne = 0.0;
 
         scanf("%lf", &enne);
         printf("\nlog(%lf) = %lf\n\n", enne, log(enne));
 
         return 0;
}
 
[D:\Users\jak]
 
$> gcc pp.c -o pp
 
[D:\Users\jak]
 
$> pp
12
 
log(12.000000) = 2.484907
 
 
[D:\Users\jak]
 
$>

$>
 
Come fai ad usare il DOS su NT lo saprai tu... chi e'
l'interprete? 
COMMAND.COM
 e' morto, almeno quello della m$.
Hai cmd.exe nella "finestra del prompt del DOS"?
 
Perche' non provi a metterti, su di un file di 1/2 giga, una
Debian virtuale SENZA grafica (solo la console a caratteri),
cosi' provi l'onnipotenza di bash?  ..e puoi testare il gcc
vero. Ciao alla prossima
 
-- 
Saluti,
Guido
 


 
Era più che altro pigrizia:
 
jak@###-###:[~/Documenti/Dev]
$ uname -a
Linux ###-### 4.4.0-78-generic #99-Ubuntu SMP Thu Apr 27 15:29:09 UTC 
2017 x86_64 x86_64 x86_64 GNU/Linux
jak@###-###:[~/Documenti/Dev]
$ echo ${SHELL}
/bin/bash
jak@###-###:[~/Documenti/Dev]
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
jak@###-###:[~/Documenti/Dev]
$ cat pp.c
#include <stdio.h>
#include <math.h>
 
int main()
{
	double enne = 0.0;
 
	scanf("%lf", &enne);
	printf("\nlog(%lf) = %lf\n\n", enne, log(enne));
 
	return 0;
}
jak@###-###:[~/Documenti/Dev]
$ gcc pp.c -o pp
jak@###-###:[~/Documenti/Dev]
$ pp
12
 
log(12.000000) = 2.484907
 
jak@###-###:[~/Documenti/Dev]
$
 
Che dirti... sarà una questione di configurazione. Chi sa cosa non gli 
ho combinato nel tempo a 'sti poveri sistemi.
 
Un saluto

ho combinato nel tempo a 'sti poveri sistemi.
 
Si'.. dev'essere Ubuntu che ci ha messo lo zampino nel compilare
il pacchetto gcc, a parte che e' la 5.4, io lo la Debian stable,
con la testing probabilmente c'e' la 5.4 anche nella Debian.
Ciao!
 
P.S. Certo che, se non c'e' bisogno, il -lm  e' certamente
meglio non mettercelo! ho fatto la prova con altro sorgente e
l'eseguibile viene diverso e va anche piu' lento (l'ho testato
con time).
 
-- 
Saluti,
Guido
 


 
Lavoro su sistemi unix/xenix/linux da oltre 30 anni ma la gente usa 
windows :(
 
 
 

 windows :(
 
E' ora di disintossicarsi:
http://www.art.net/~hopkins/Don/unix-haters/x-windows/disaster.html
 
 
-- 
I'm not anti-social;
I'm just not user friendly


X-XD
rofl