combinatoire et tableau

J'ai un tableau sous RealBasic de N éléments.

Je désirerai combiner les différents éléments de ce tableau:

Sortir les éléments, deux par deux, trois par trois, ... jusqu'à N.

Pose plutôt la question sur un forum d'algorythmique.

je propose :

{a,b,c,d} représente un tableau contenant a b c et d
i(l) représente i indice l

pour avoir les éléments k par k il suffit de faire

pour i(1)=0 à N-k
pour i(2)=i1+1 à N-k-1
pour i(3)=i2+1 à N-k-2
...
pour i(k)=i(k-1)+1 à N-k-(k-1)
ajouter {element i(0), ... , element i(k)} à la liste
des k-uplets

--
Schmurtz

Petite correction :

pour i(1)=0 à N-k
pour i(2)=i1+1 à N-k+1
pour i(3)=i2+1 à N-k+2
...
pour i(k)=i(k-1)+1 à N-k+(k-1)
ajouter {element i(0), ... , element i(k)} à la liste
des k-uplets

--
Schmurtz

Schmurtz <moi@ici.com> wrote:

{a,b,...x,d} représente un tableau contenant a b c, ...,d soit N élément

j'obtiens la taille de monTableau(Z) avec:

N=ubount(monTableau) qui est variable

je veux une sortie de deux par deux:

a+b
b+c
...
x+d

et ensuite trois par trois:

a+b+c
b+c+d
.....
w+x+d

ect.

et pour finir l'ensemble N une fois

a+b+...x+d

Une formule récursive sans doute avec deux varialbes, mais je n'arrive
pas à me représenter comment elle devrait fonctionner. Je mouline à
vide. Si N avait toujours la même taille, J'y arriverai pas à pas, mais
là, je suis vraiment bloqué.

Merci de ton aide.

--
Sois très humble devant chacun car la destinée
de l'homme est d'être la proie des vers.
(Avoth 4.4)

Une formule récursive sans doute avec deux varialbes, mais je n'arrive
pas à me représenter comment elle devrait fonctionner. Je mouline à
vide. Si N avait toujours la même taille, J'y arriverai pas à pas, mais
là, je suis vraiment bloqué.

La méthode que je t'ai proposé marche pour sortir les liste de k
éléments, k étant fixé.

-------

pour avoir les éléments k par k il suffit de faire (k est fixé).

pour i(1)=0 à N-k
pour i(2)=i1+1 à N-k-1
pour i(3)=i2+1 à N-k-2
...
pour i(k)=i(k-1)+1 à N-k-(k-1)
afficher {element i(0), ... , element i(k)}

-------

pour avoir un code indépendant de k, il faut gérer les indices dans un
tableau :

#include <stdio.h>

int incremente(int* indices,int* indicesmax, int i);

int main(int argn, char** args) {

if( argn <= 1 ) {
printf("Mettre au moins un paramètre.n");
printf("Calcule l'ensemble des sous ensembles des paramètres.n");
return 1;
}

int N = argn-1;
int indices[N]; // indices[l-1] = i(l)
int indicesmax[N];
int i;
int K;

for( K=1; K<=N; K++ ) {
for(i=1;i<=K;i++) {
indicesmax[i-1] = N-K+(i-1);
indices[i-1] = i-1;
}

do {
for(i=1;i<=K;i++)
printf(""%s" ",args[indices[i-1]+1]);
printf("n");
} while( incremente(indices,indicesmax,K) );
}

return 0;
}

int incremente(int* indices,int* indicesmax, int i) {
if( indices[i-1] == indicesmax[i-1] ) {
if( i == 1 ) return 0;
if( !incremente(indices,indicesmax,i-1) ) return 0;
indices[i-1] = indices[i-2]+1;
} else {
indices[i-1]++;
}
return 1;
}

-------

ça marche, j'ai testé.

tu le compiles avec "gcc code.c -o test"
puis tu exécutes "./test coucou pascoucou lui elle"

--
Schmurtz

J'ai même encore plus simple. Il s'agit en fait de faire la liste de
tout les sous ensembles d'un ensemble E = {e1,Š,eN}. Pour ça, il sufit
de compter en binaire avec des nombres à N bits. Chaque nombre a peut
alors être considérer comme une fonction f de {1,2,Š,N} dans {0,1},
telle que f(n)=bit n de a. Ainsi, on peit assicier à chaque nombre a un
sous ensemble de E défini par {en|f(n)=1}.

Par exemple, pour N=5 :
00001 -> {e1}
00010 -> {e2}
00011 -> {e1,e2}
00100 -> {e3}
00101 -> {e3,e1}
00110 -> {e3,e2}
00111 -> {e3,e2,e1}
01000 -> {e4}
Š

Il suffit juste d'écrire une fonction qui compte en binaire sur des
nombres arbitrairement grands.

--
Schmurtz

Schmurtz <moi@ici.com> wrote:

ça marche, j'ai testé.

tu le compiles avec "gcc code.c -o test"
puis tu exécutes "./test coucou pascoucou lui elle"

J'ai posté sur fr.comp.algorithmes ou j'ai eu la structure de
l'algorithme.

Avec RealBasic, en peu de lignes:

******************
dim g, taille, cycle, pas as integer
dim monTableau(0), resultat(0) as string

g=ubound(monTableau)

for taille=g downTo 1
for cycle=taille downTo 1
for pas=taille downTo cycle
z=monTableau(pas) + " " + z
next
z=trim(z)
resultat.append Z
Z=""
next
next
*****************

Je viens de tester, et cela donne toutes les combinatioires requises.
D'un point de vue théorique, c'est la troisième ligne, qui indique de
faire un travail entre deux variables (qui varient :) ) qui me
bloquaient dans mon raisonnement.

D'habitude, le code reflète fidèlement une manipulation que je pourrais
faire manuellement: "je coupe un bout de phrase, je le colle avec cet
autre bout, je le déplace dans tel endroit à tel tableau, ect."

Ensuite je regarde si tout se passe comme je l'ai imaginé à priori.
C'est surtout aux limites que cela pose problème, quand c'est zéro, ou
en haut du tableau.

Merci de ton conseil d'aller sur fr.comp.algorithmes, et merci à
Alexandre Michelot de m'avoir indiqué la voie.

Y-a-t'il quelque chose qui traite de la conceptualisation des
algorithmes sur le net ?

(suivi sur fr.comp.algorithmes)

--
Sois très humble devant chacun car la destinée
de l'homme est d'être la proie des vers.
(Avoth 4.4)