Discussion :

[Tehko]

Bonjour à tous,

Je suis actuellement en train de développer une fonction Java à partir d'un code MatLab. Je bloque pour retourner le résultat de la fonction MatLab nchoosek(n,k) sachant que dans mon cas n correspond à un vecteur.

Pour être plus explicite, voici le morceau de code MatLab que je souhaite coder en Java :

Code MatLab :

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

1
2
3
4
5
6
7
8
9
10
A=zeros(2^n-2,n);
A1=A;
k1=1:n;
nn1=1;
for  i=1:n
    x=nchoosek(k1,i);
    [n1 n2]=size(x);
    A(nn1:nn1+n1-1,1:n2)=x;
    nn1=nn1+n1;
end

Pour l'instant, voici ma fonction retournant le coefficient binomial, mais qui ne prend pas en paramètre un vecteur.

Code fct binomialCoef(n,m) équivalente à nchoose(n,m) MatLab :

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

1
2
3
4
5
6
7
8
9
10
11
    public static int binomialCoef(int n, int m) {
        int[] b = new int[n + 1];
        b[0] = 1;
        for (int i = 1; i <= n; i++) {
            b[i] = 1;
            for (int j = i - 1; j > 0; j--) {
                b[j] += b[j - 1];
            }
        }
        return b[m];
    }

Je ne suis pas le roi de l'algorithmique (ni de MatLab d'ailleurs), du cout j'aimerai de l'aide pour passer ce casse-tête.

Cordialement,
Tehko

[Tehko]

Personne pour un coup de pouce ?

[Tehko]

Je m'étais attaché à vouloir absolument faire ce que la fonction MatLab faisait et j'en ai oublié l'essentiel.

L'objectif de la fonction principale est de retourner une matrice de toutes les permutations binaires possibles suivant un paramètre.
Concrètement, j'ai une fonction coalition(n), n étant le paramètre. Je cherche à retourner la matrice, contenant (2^n)-2 éléments.
Par exemple:

- si n = 2, on aura (2^2)-2 = 2 solutions :

1 0
0 1

- si n = 3, (2^3)-2 = 6 solutions :

1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1

- si n = 4, (2^4)-2 = 14 solutions :

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1

La matrice serait donc en 2D de taille [2^n-2][n].
Je ne sais toujours pas comment m'y prendre pour obtenir ce résultat.

Aux modérateurs : ce sujet devrait peut-être être déplacé dans la rubrique Algorithmique ?

[Tehko]

Aux modérateurs : ce sujet devrait peut-être être déplacé dans la rubrique Algorithmique ?

Le nombre de "Vues" augmentent mais toujours pas de réponse. Je ré-itère ma question aux modérateurs : suis-je toujours dans la bonne rubrique avec ce que je souhaite faire ?

[Jerome Briot]

Pose les permutations dans le bon ordre, et tu verras apparaitre les pattern par colonne :

n = 2

0 0
0 1
1 0
1 1

n = 3

0 0 0
0 1 0
0 0 1
0 1 1
1 0 0
1 1 0
1 0 1
1 1 1

n = 4

0 0 0 0
0 1 0 0
0 0 1 0
0 1 1 0
0 0 0 1
0 1 0 1
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 0
1 0 1 0
1 1 1 0
1 0 0 1
1 1 0 1
1 0 1 1
1 1 1 1

Il suffit ensuite de ne pas tenir compte ni de la première, ni de la dernière permutation.

[Tehko]

J'étais bien bête. Je m'étais obstiné à vouloir ces permutations dans l'ordre où je les avais précisé plus haut alors que je n'étais pas obligé.

Du coût, j'ai trouvé encore plus simple comme approche. Je fais une conversion décimal vers binaire d'un integer dans une string. J'ajoute des 0 afin d'avoir un résultat sur n bits. Ainsi, je génère toutes les permutations possibles.

Voici le code, si ça peut servir à quelqu'un d'autre (même si le titre du sujet ne répond pas au problème).

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
26
27
28
public static void permut(int n)
    {
        String s_binary = "";   //utilisé pr la conversion
        int col = n;       //nb de colonnes
        int lin = (int)Math.pow(2, n)-2; //nb de lignes
        int[][] matrix = new int[lin][col];
 
        for (int i_line = 0; i_line < lin; i_line++)
        {
            s_binary = Integer.toBinaryString(i_line+1);//conversion
            while (s_binary.length() < col)//tant que la taille de s_binary est < aux nb de colonnes
                s_binary = "0" + s_binary;//0>>s_binary
 
            //remplissage de la matrice
            for (int i_col = 0; i_col < col; i_col++)
            {
                matrix[i_line][i_col] = Character.digit(s_binary.charAt(i_col),10);//conversion caractère vers integer (base 10)
            }
        }
 
        //affichage de la matrice
        for (int i = 0; i < lin; i++)
        {
            for (int j = 0; j < col; j++)
                System.out.print(matrix[i][j]);
            System.out.println();
        }
    }

Pour tester :

Code :

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

1
2
3
    public static void main(String[] args) {
        permut(3);
    }

Résultat :
001
010
011
100
101
110

En tout cas, merci Dut. Je n'ai pas utilisé ta technique mais tu m'as aidé à faire tilt.