Discussion :

[Loceka]

Bonjour, le titre n'étant pas très explicite je vais essayer de rendre l'énoncé assez compréhensible.

Considérons une liste d'éléments de longueur N. Je voudrais réordonner successivement cette liste de sorte qu'à chaque nouveau réordonnancement apparaissent des tuples différents de longueur K au début de la liste (et parallèlement, mais c'est inévitable, des tuples différents de longueur N-K en fin de liste).

Mathématiquement ça permet de lister les combinaisons associées à chaque coefficient C(N,K) dans l'équation :
(X + Y)^N = C(N,0)*Y^N + C(N,1)*X*Y^(N-1) + ... + C(N,N)*X^N

Par exemple, pour une liste d'éléments L de longueur N = 4 :
L = [1, 2, 3, 4]

Si on cherche toutes les combinaisons associées à K = 2 soit :
C(4,2) * X^2 * Y^2 = 6 * X^2 * Y^2
Ce qui est équivalent à rechercher tous les couples X distincts dans L, on devrait obtenir un ensemble de solutions de la forme :
S1 = [1, 2, 3, 4] <=> X1 = [1, 2] et Y1 = [3, 4]
S2 = [1, 3, 2, 4] <=> X2 = [1, 3] et Y2 = [2, 4]
S3 = [1, 4, 2, 3] <=> X3 = [1, 4] et Y3 = [2, 3]
S4 = [2, 3, 1, 4] <=> X4 = [2, 3] et Y4 = [1, 4]
S5 = [2, 4, 1, 3] <=> X5 = [2, 4] et Y5 = [1, 3]
S6 = [3, 4, 1, 2] <=> X6 = [3, 4] et Y6 = [1, 2]

ou encore toutes celles associées à K = 3 soit :
C(4,3) * X^3 * Y = 4 * X^3 * Y
Ce qui est équivalent à rechercher tous les triplets X distincts dans L :
S1 = [1, 2, 3, 4] <=> X1 = [1, 2, 3] et Y1 = [4]
S2 = [1, 2, 4, 3] <=> X2 = [1, 2, 4] et Y2 = [3]
S3 = [1, 3, 4, 2] <=> X3 = [1, 3, 4] et Y3 = [2]
S4 = [2, 3, 4, 1] <=> X4 = [2, 3, 4] et Y4 = [1]

Ce que je cherche à faire c'est d'obtenir la liste des solutions Si pour un K et un N donnés correspondant à une liste L donnée.

J'ai recherché du côté de findall/3 ou setof/3 mais je ne vois pas comment m'y prendre.

J'ai bien des solutions pour des cas particuliers (K=0, K=N : il n'y a rien à faire ; K=1, K=N-1 : il suffit d'une permutation circulaire) mais pour les autres cas je ne vois pas.

Si vous connaissez une solution qui fonctionne dans le cas général, ou si vous avez une idée de comment faire, faites-le moi savoir !

J'ai hésité à poster ça dans le forum Algorithmes mais comme je le fais en Prolog autant profiter des spécificités et des prédicats déjà existants du langage.

Merci d'avance,
Loceka.

[Trap D]

Je ne sais pas si ça peux t'aider, mais en SWI-Prolog il y a un prédicat permutation(?List1, ?List2) :

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
1 ?- permutation([1,2,3], List2).
 
List2 = [1, 2, 3] ;
 
List2 = [2, 1, 3] ;
 
List2 = [2, 3, 1] ;
 
List2 = [1, 3, 2] ;
 
List2 = [3, 1, 2] ;
 
List2 = [3, 2, 1] ;
 
No

[pcaboche]

Je ne sais pas si ça peux t'aider, mais en SWI-Prolog il y a un prédicat permutation(?List1, ?List2).

Ca serait trop long de faire toutes les permutations possibles puis de vérifier si les listes ainsi générées sont bien ordonnées.

Par contre, on peut faire ceci:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
split(L, [], L).
 
split([T|Q], [T|L1], L2) :-
  split(Q, L1, L2).
 
 
sol(0,L,[], L).
sol(N,L,[T|L3],R) :-
  N>0,
  split(L, L1, [T|L2]),
  N1 is N-1,
  sol(N1,L2,L3,L4),
  append(L1,L4,R).

Ce qui donne cela à l'exécution:

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
|?- sol(2, [1,2,3,4], X, Y).
 
X = [1, 2],
Y = [3, 4] ;
 
X = [1, 3],
Y = [2, 4] ;
 
X = [1, 4],
Y = [2, 3] ;
 
X = [2, 3],
Y = [1, 4] ;
 
X = [2, 4],
Y = [1, 3] ;
 
X = [3, 4],
Y = [1, 2] ;

[Loceka]

Merci beaucoup, ça me semble être ce que je recherche !

Je n'ai pas encore testé si ça correspondait parfaitement, et j'ai dû mal m'exprimer dans mon premier message parce que je ne demandais pas forcément que les résultats soient ordonnés (mais s'ils le sont c'est tant mieux), ni même à séparer les X et les Y.

J'avais 'juste' besoin de trouver l'ensemble des solutions S1..Sc et de les ranger dans une liste.

Encore merci.

PS : j'éditerai ce message quand j'aurai bien vérifié que ça fonctionne

[pcaboche]

Mje ne demandais pas forcément que les résultats soient ordonnés (mais s'ils le sont c'est tant mieux)

En fait, je voulais plutôt dire "qui conserve l'ordre des éléments de la liste" (donc si on passe une liste ordonnée, le résultat sera ussi ordonné, ce qui n'est évidemment pas le cas si on fait des permutations).

[Loceka]

Bon ben rien à redire, ça fait exactement ce que je voulais.

Bravo à tous les deux pour les codes et la réactivité (surtout un samedi soir) !

Heureusement que vous étiez là parce que je partais apparement dans une mauvaise voie en essayant de lister "moi-même" toutes les solutions, sans me servir du backtrack.

Voici donc le code qui liste toutes les solutions (en majeure partie le même que ci-dessus excepté un renommage de variable pour être cohérent avec mon premier post et un cut) :

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
split(L, [], L).
split([T|Q], [T|L1], L2):-
	split(Q, L1, L2).
 
 
sol(0,L,[], L):-
	!.
sol(K,L,[T|L3],R):-
	split(L, L1, [T|L2]),
	K1 is K-1,
	sol(K1,L2,L3,L4),
	append(L1,L4,R).
 
 
sol(K, L, R):-
	sol(K, L, X, Y),
	append(X, Y, R).
 
 
all_sol(K,L,Sol):-
	findall(R, sol(K,L,R), Sol).