Permutation avec Predicate

**pio_killer** · 18/10/2016, 11h39

Bonjour,

je suis débutant en JAVA et j'aimerais avoir une petite explication sur le fonctionnement de predicate.

je voudrais faire une classe qui permette de trouver toutes les permutations d'un ensemble de string.

Sur ce site https://rosettacode.org/wiki/Permuta...petitions#Java , j'ai trouvé cette fonction :

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
29
30
31
32
33
34
35
36
37
import java.util.function.Predicate;
 
public class PermutationsWithRepetitions {
 
    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd'};
        // looking for bba
        permute(chars, 3, i -> i[0] == 1 && i[1] == 1 && i[2] == 0);
    }
 
    static void permute(char[] a, int k, Predicate<int[]> decider) {
        int n = a.length;
        if (k < 1 || k > n)
            throw new IllegalArgumentException("Illegal number of positions.");
 
        int[] indexes = new int[n];
        int total = (int) Math.pow(n, k);
 
        while (total-- > 0) {
            for (int i = 0; i < n - (n - k); i++)
                System.out.print(a[indexes[i]]);
            System.out.println();
 
            if (decider.test(indexes))
                break;
 
            for (int i = 0; i < n; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
    }
}

Qui donne en sortie :

Code :

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

1
2
3
4
5
6
aaa
baa
caa
daa
aba
bba

Je suis en train de l'adapter car je veux trouver les permutations d'un ensemble de string et non d'un ensemble de charactères.

Voici mon code modifié :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package pk_Permutation;
 
import java.util.function.Predicate;
 
public class PermutationsWithRepetitions {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
		char[] tabChars = {'a', 'b', 'c', 'd'};
		String[] tabString = {"T60196", "T60210", "T60367", "T60419", "T60659", "T60760", "T60925", "T61325", "T61356", "T62522", "T62672", "T62682", "T63479", "T63480", "T64218", "T64239", "T64240", "T64352", "T64884", "T65025", "T65093", "T66377", "T66430", "T66552", "T66953", "T67125", "T67150", "T67221", "T68426", "T68689", "T68717", "T68765", "T68789", "T68815", "T68849", "T69154", "T69876", "T69936", "T70009", "T70010", "T70259", "T70684", "T70978", "T71133", "T71171", "T72778", "T73792", "T73803", "T73929", "T75373", "T75660"};
 
 
 
		System.out.print("Permutation de charactères unique");
				permute_Char(tabChars, tabChars.length, i -> i[0] == 1 && i[1] == 1 && i[2] == 1 && i[3] == 0);
 
 
 
		System.out.print("Permutation de chaine de charactère");
		permute_String(tabString, tabString.length, i -> i[0] == 1 && i[1] == 1 && i[2] == 0);
 
 
	}
 
	static void permute_Char(char[] a, int k, Predicate<int[]> decider) {
        int n = a.length;
        if (k < 1 || k > n)
            throw new IllegalArgumentException("Illegal number of positions.");
 
        int[] indexes = new int[n];
        int total = (int) Math.pow(n, k);
 
        while (total-- > 0) {
            for (int i = 0; i < n - (n - k); i++)
                System.out.print(a[indexes[i]]);
            	System.out.println();
 
            if (decider.test(indexes))
                break;
 
            for (int i = 0; i < n; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
 
 
    }
 
    static void permute_String(String[] a, int k, Predicate<int[]> decider) {
        int n = a.length;
 
        System.out.print("a.length"+a.length);
        System.out.println();
 
        if (k < 1 || k > n)
            throw new IllegalArgumentException("Illegal number of positions.");
 
        int[] indexes = new int[n];
        int total = (int) Math.pow(n, k);
 
        //print
        System.out.print("total="+total);
        System.out.println();
 
        while (total-- > 0) {
            for (int i = 0; i < n - (n - k); i++)
                System.out.print(a[indexes[i]]+"/");
            	System.out.println();
 
            if (decider.test(indexes))
                break;
 
            for (int i = 0; i < n; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
    }
 
}

Les chaines de caractère sont dans "tabString" et ma fonction perso est "permute_String"

Le problème est que cela ne fonctionne pas.

En essayant de comprendre le code, je me demandais comment fonctionnait l'outils "Predicate".
J'ai trouvé la doc en anglais mais j'ai du mal à comprendre.

Est-ce que quelqu'un saurait m'expliquer svp.

Merci d'avance

**adiGuba** · 18/10/2016, 12h14

Salut,

Un Predicate déclare juste une méthode qui renvoi true/false selon l'objet qu'on lui passe.

Par contre j'ai un peu de mal à comprendre son intérêt ici et la logique du code.
Le but c'est d'obtenir quoi exactement ?

a++

**hwoarang** · 18/10/2016, 13h38

Ton code est quand meme bien compliqué pour une fonction tres simple. Un Predicate permet de tester si certaines conditions sont reunies (dans ton cas, si les indices de permutation ont une certaine valeur).
La dessus, tu utilises une lambda (dans l'appel à la fonction permute) qui definie le Predicate pour qu'il renvoie true lorsque le premier item a été permuté 1 fois, le 2e 1 fois et le 3e 0 fois. C'est pour ca que ton code s'arrete à "bba".

Note que si ton objectif est d'obtenir toutes les permutations possibles (ce qui est généralement ce qu'on veut), il te suffit de virer tout ce qui concerne le Predicate (dans la fonction permute, dans l'appel puis le break conditionnel).

**pio_killer** · 18/10/2016, 13h48

Merci pour ta réponse.

Mon but final est de prendre une liste de STRING (par exemple "toto","tata","titi") et de lister toutes les configurations possibles mais en tenant compte de l'ordre.

Dans cet exemple on aura :
configuration n°1 : toto
configuration n°2 : toto + tata
configuration n°3 : toto + titi
configuration n°4 : toto + tata + titi
configuration n°5 : titi
configuration n°6 : titi + tata
configuration n°7 : tata

Je précise en tenant compte de l'ordre car la configuration "tata + titi" est déjà dans la "configuration n°6" mais sous un autre ordre.

J'ai fait une appli en vb et en vba qui fait ce genre de calcul mais cela devient très long lorsqu'il y a beaucoup STRING à prendre en compte.

Je voulais donc voir si cela pouvait être plus rapide en JAVA.

Permutation avec Predicate

avec Java

Discussions similaires

Partager

Partager