Trouver les combinaisons de k parmi n

**saturn1** · 06/08/2010, 23h14

Bonjour,
je sais qu'il existe beaucoup de topic existant sur ce sujet.
Mais c'est apres beaucoup de recherches que je fais un n(ieme) posts.

Le but est avec une combinaison de chiffre, generer toutes les nombres possibles.

Par exemple pour :
0, 1, 2 => 6 possibilites
0, 1, 2, 3 => 24 possibilites.
Le but n'etant pas de les compter mais de les afficher.

J'ai fais un script mais le probleme c'est qu'il est beaucoup trop long pour les combinaisons a 10 chiffres.

Voici mon script :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 
 
function perm($nbrs, $res)
{
  for ($i = 0; $i != count($nbrs); $i++)
    {
      $prev = $res[count($res) - 1];
      $tmp = $prev[$i];
      $prev[$i] = $prev[($i + 1) % count($nbrs)];
      $prev[($i + 1) % count($nbrs)] = $tmp;
      if (!in_array($prev, $res))
        {
          $res[] = $prev;
          echo $prev . "\n";
          perm($nbrs, &$res);
        }
    }
  return $res;
}
 
$nbrs = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$res = array("0123456789");
echo $res[0] . "\n";
$res = perm($nbrs, &$res);

Comment optimiser ce code ?

Merci bien!

**Fredchkek** · 07/08/2010, 09h54

Bonjour,

Beaucoup trop long : c'est à dire ?

Il y a près de 4 millions de solutions (si j'ai bien compris le problème), c'est normal que ce soit long non ?

**saturn1** · 07/08/2010, 10h10

j'ai abandonne au bout de 1 mn...

Je pense qu'il y a moyen d'optimiser ca car la je dois faire un in_array voir si il n'est pas deja dans le tableau... ca doit prendre du temps :/

Merci

**pseudocode** · 07/08/2010, 13h45

itération des 10!=3628800 permutations en 70 millisecondes sur mon PC

itérateur de permutations

(bon c'est du java, alors c'est un peu lent

)

**saturn1** · 07/08/2010, 15h46

euh 70 milliseconde ca me semble ... impossible pour le nombre de resultat trouves ^^

Voila mon temps avec un nouvel algo:

total res = 3628800
real 1m24.465s
user 0m21.233s
sys 0m6.308s

PS : j'ai rien compris a ton algo en iteratif !

**pseudocode** · 07/08/2010, 16h04

Envoyé par saturn1

euh 70 milliseconde ca me semble ... impossible pour le nombre de resultat trouves ^^

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
long t0 = System.currentTimeMillis(), i=0;
 
Character[] sample = new Character[] {'0','1','2','3','4','5','6','7','8','9'};
Permutation<Character> permut = new Permutation<Character>(sample);
 
while(permut.next()) i++;
 
long t1 = System.currentTimeMillis();
 
System.out.println("Nombre de permutations : "+i);
System.out.println("temps écoulé : "+(t1-t0)+"ms");

Résultat:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Nombre de permutations : 3628800
temps écoulé : 70ms

Dans ce code, l'algo ne fait que énumérer en mémoire les permutations. S'il faut les afficher ou faire un traitement dessus, ca sera évidement plus long.

PS : j'ai rien compris a ton algo en iteratif !

C'est un odomètre. C'est pas facile a comprendre, mais ca marche.

**Zavonen** · 07/08/2010, 17h14

@pseudocode:
Ton 'itérateur' ne renvoie qu'un booléen.
De fait le programme ne fait que compter les permutations
Voici un itérateur qui les calcule effectivement (sans les imprimer ni rien en faire).
Le temps est de l'ordre de 30 secondes (python n'est pas réputé être rapide)

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
import time
 
def time_this(func):
    """The time_this decorator"""
 
    def decorated(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "Ran in", time.time() - start, "seconds"
        return result
    return decorated
 
 
def permutations(iterable):
    """itérateur fonctionnant avec n'importe quel itérable peut être 
    utilisé avec chaines, listes, tuples, etc..."""
    pool = tuple(iterable)
    n = len(pool)
    indices = range(n)
    cycles = range(n, 0, -1)
    yield tuple(pool[i] for i in indices[:n])
    while n:
        for i in reversed(range(n)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:n])
                break
        else:
            return
@time_this       
def main():        
    P=permutations(range(10))
    for x in P:
        pass
 
main()
#résultat Ran in 31.0496931076 seconds

**pseudocode** · 07/08/2010, 17h18

Envoyé par Zavonen

@pseudocode:
Ton 'itérateur' ne renvoie qu'un booléen.
De fait le programme ne fait que compter les permutations

rhooo, c'est mal me connaitre.

L'itérateur permute les éléments du tableau de départ. Le tableau contient donc une nouvelle permutation à chaque appel.

**Zavonen** · 07/08/2010, 18h34

L'itérateur permute les éléments du tableau de départ. Le tableau contient donc une nouvelle permutation à chaque appel

Oui, tu as raison, j'ai regardé ça de plus près ça a l'air vraiment bien.

**Zavonen** · 07/08/2010, 19h15

Voici une traduction de ton algo en python
On tombe à 7 secondes (seulement).
Je pense que c'est surtout dû au fait que Python ignore les tableaux (accès séquentiel) et travaille avec des listes doublement chaînées.
Les accès aux deux tableaux sont donc beaucoup plus longs.

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import time
 
def time_this(func):
    """The time_this decorator"""
 
    def decorated(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "Ran in", time.time() - start, "seconds"
        return result
    return decorated
 
 
class Permutations ():
 
    def __init__(self, L):
        self.n=len(L)
        self.array=L
        self.state=[0]*self.n
        self.position=0
 
    def next(self):
        if self.position==0:
            self.position+=1
            return True
        while self.position<self.n:
            if self.state[self.position]<self.position:
                index=0 if self.position%2==0 else self.state[self.position]
                temp=self.array[self.position]
                self.array[self.position]=self.array[index]
                self.array[index]=temp
                self.state[self.position]+=1
                self.position=1
                return True
            else:
                self.state[self.position]=0
                self.position+=1
        return False
 
@time_this
def main():
    P=Permutations(range(10))
    x=P.next()
    while x:
        x=P.next()
 
main()
"""Ran in 7.8425590992 seconds"""

Enfin je confirme que ton algo marche bien et même très bien

**Fredchkek** · 07/08/2010, 21h53

Bonsoir,

Bon et bien ça me semble résolu cette histoire...

Pour le plaisir, je propose une autre façon de faire, cette fois en C/C++.
Sur mon PC le temps de calcul est 79ms.
L'idée de départ est qu'on connaît a priori le nombre de permutations à faire (N!) (d'où la boucle for).

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include "time.h"
 
char machaine[]="0123456789";
 
int main(int argc, char *argv[])
{
	//std::cout << "Affichage de toutes les permutations \n";
 
	// longueur de la chaine
	int nbrcar=strlen(machaine);
 
	// Calcul du nombre de permutations (factorielle)
	long int nbr_permut=1;
	for(int i=2; i<=nbrcar ; i++) nbr_permut=nbr_permut*i;
	//std::cout << "Temps de calcul " << 1000*double(clock())/CLOCKS_PER_SEC << "ms" << std::endl;
 
	int j=0,k; // indices des caractères à permuter
	for(long int i=0; i<nbr_permut ; i++)
	{
		// indice du second caractère impliqué dans la permutation
		k=j+1;
		if(k==nbrcar) k=0; // condition cyclique sur le 2nd caractère à permuter
 
		// "LA" permutation
		char tampon;
		tampon=machaine[j];
		machaine[j]=machaine[k];
		machaine[k]=tampon;
 
		// Affichage
		for(int ii=0; ii<nbrcar ; ii++) std::cout << machaine [ii] << " ";
		std::cout << "\n";
 
		j++;
		if(j==nbrcar) j=0; // condition cyclique sur le 1er caractère à permuter
	}
 
	std::cout << "Temps de calcul " << 1000*double(clock())/CLOCKS_PER_SEC << "ms" << std::endl;
	return 0;
}

**pseudocode** · 07/08/2010, 23h41

C'est pas un peu fini de copier mon odomètre.

**Zavonen** · 08/08/2010, 01h50

@Fredchkek
Je ne sais pas comment tu t'y prends pour mesurer le temps.
Il est bizarre que C soit plus lent que java (jamais vu ça)
avec ton code je trouve 7.5 millisecondes.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <time.h>
 
main()
{
    char machaine[]="0123456789";
    clock_t
    temps_initial, /* temps initial  */
    temps_final;   /* temps final  */
    double
    temps_cpu;     /* temps total en secondes */
    int nbrcar=strlen(machaine);
    long int i;
    // Calcul du nombre de permutations (factorielle)
    long int nbr_permut=1;
    int h;
    for (h=2; h<=nbrcar ; h++) nbr_permut=nbr_permut*h;
    temps_initial = clock ();
    int j=0,k; // indices des caractères à permuter
    char tampon;
    int m;
    for (m=0;m<100;m++) // on fait 100 fois pour mesurer le temps
    {
        for ( i=0; i<nbr_permut ; i++)
        {
            // indice du second caractère impliqué dans la permutation
            k=j+1;
            if (k==nbrcar) k=0; // condition cyclique sur le 2nd caractère à permuter
            tampon=machaine[j];
            machaine[j]=machaine[k];
            machaine[k]=tampon;
            j++;
            if (j==nbrcar) j=0; // condition cyclique sur le 1er caractère à permuter
        }
    }
    temps_final = clock ();
    temps_cpu = (temps_final - temps_initial);
    printf("%lf",10*temps_cpu/CLOCKS_PER_SEC); // on multiplie par 1000 les microsecondes et on divise par 100 d'où le facteur 10.
}

**pseudocode** · 08/08/2010, 02h10

Envoyé par Zavonen

@Fredchkek
Je ne sais pas comment tu t'y prends pour mesurer le temps.
Il est bizarre que C soit plus lent que java (jamais vu ça)
avec ton code je trouve 7.5 millisecondes.

Oui, un facteur 10 entra Java/C ca me parait raisonnable. Peut être qu'il a encore un 486DX ?

**Fredchkek** · 08/08/2010, 11h02

@Zavonen

Je ne sais pas comment tu t'y prends pour mesurer le temps.
Il est bizarre que C soit plus lent que java (jamais vu ça)
avec ton code je trouve 7.5 millisecondes.

Dans mon code clock() renvoie le temps écoulé depuis le lancement du programme ... Donc c'est bien 79ms pour tout faire !
En utilisant un start-stop dans le coeur du programme (comme toi) je "tombe" à encore 27 ms (avec ta version aussi d'ailleurs 27ms)...
Bref, nous ne sommes pas tous égaux en terme de puissance de calcul (ta machine calcule 4 fois plus vite que la mienne....

)

**Zavonen** · 08/08/2010, 14h53

A tout hasard, voici les caractéristiques de mon système

description: Computer
width: 64 bits
capabilities: vsyscall64 vsyscall32
*-core
description: Motherboard
physical id: 0
*-memory
description: System memory
physical id: 0
size: 3962MiB
*-cpu
product: Intel(R) Pentium(R) Dual CPU E2220 @ 2.40GHz
vendor: Intel Corp.
physical id: 1
bus info: cpu@0
size: 1203MHz
capacity: 1203MHz
width: 64 bits
capabilities: fpu fpu_exception wp vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx x86-64 constant_tsc arch_perfmon pebs bts rep_good aperfmperf pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm cpufreq
*-pci
description: Host bridge
product: nVidia Corporation
vendor: nVidia Corporation
physical id: 100
bus info: pci@0000:00:00.0
version: a2
width: 32 bits
clock: 66MHz

Compilateur GNU GCC système Linux Ubuntu Lucid

**Fredchkek** · 08/08/2010, 17h42

@Zavonen

Il est normal ce facteur 4 entre nos machines ?
(compilo Visual express)

Nom du système d’exploitation Microsoft Windows 7 Professionnel
Version 6.1.7600 Numéro 7600
Autre description du système d’exploitation Non disponible
Fabricant du système d’exploitation Microsoft Corporation
Fabricant Dell Inc.
Modèle Latitude E4300
Type PC à base X86
Processeur Intel(R) Core(TM)2 Duo CPU P9600 @ 2.53GHz, 2535 MHz, 2 cœur(s), 2 processeur(s) logique(s)
Version du BIOS/Date Dell Inc. A14, 22/12/2009
Version SMBIOS 2.4
Répertoire Windows C:\Windows
Répertoire système C:\Windows\system32
Couche d’abstraction matérielle Version = "6.1.7600.16385"
Fuseaux horaires Paris, Madrid (heure d’été)
Mémoire physique (RAM) installée 4,00 Go
Mémoire physique totale 3,45 Go
Mémoire physique disponible 1,72 Go
Mémoire virtuelle totale 6,90 Go

**Zavonen** · 08/08/2010, 18h59

Il est normal ce facteur 4 entre nos machines ?

Non, nos machines sont comparables.
Donc c'est soit le compilateur (Visual a pourtant bonne réputation), soit le système.
Ah, oui cela a peut être son importance; je compile toujours avec l'option 'release' et pas 'debug' mon EDI est code::blocks. J'ai remarqué qu'en mode 'debug' le code était beaucoup plus volumineux et s'exécutait plus lentement.