Permutation permettant de trier un vecteur

**Christophe Genolini** · 08/09/2016, 15h20

Bonjour,

(toutes mes excuses si ca n'est pas le bon endroit pour poster cette question...)
Je cherche une fonction C qui me donnerait la permutation permettant de trier un vecteur dans l'ordre croissant. Par exemple, j'ai la vecteur age=(18,16,21,15). La vecteur "age après tri" est (15,16,18,21). La permutation permettant d'obtenir age après tri est (4,2,1,3). Je cherche donc la fonction qui me donnerait (4,2,1,3). Savez-vous si elle existe ?

Merci beaucoup pour votre aide.
Christophe

**Matt_Houston** · 08/09/2016, 15h46

Elle n'existe pas dans la bibliothèque standard, mais tu peux - par exemple - encapsuler tes éléments dans un struct indexed { Type data; size_t index; }, initialiser index puis effectuer un qsort sur le tableau. La nouvelle séquence des valeurs de index te donnera la permutation.

**Christophe Genolini** · 09/09/2016, 12h42

Merci. Effectivement, c'est une possibilité.
Sinon, elle n'existe pas dans une librairie non-standard ?

**Matt_Houston** · 09/09/2016, 13h11

Très probablement, reste à la trouver. Cela dit la méthode que j'ai suggéré serait probablement implémentée en dix lignes et quinze minutes chrono, tests unitaires compris.

**picodev** · 09/09/2016, 15h15

Bonjour,

Comme le dit très bien Matt_Houston, quand il n'y a pas et que c'est simple à implémenter autant le faire. J'imagine que le prototype de ta fonction idéale prend pour paramètre un tableau et sa taille et te renvoie un tableau de même taille contenant la permutation. Quelque chose comme :

Code :

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

size_t *perm_sort(size_t size, int array[static size]);

Un algorithme pour faire ça sans passer par une structure pourrait suivre l'idée suivante : si on regarde un algo de tri (par comparaison) de plus près on s'aperçoit qu'en gros on suit une procédure de décision pour savoir quels éléments échanger, et on fait ça tant qu'on a pas le tableau trié. Si on se crée un tableau auxiliaire A={0,1,...,n} avec n+1 la taille du tableau à trier T et qu'au lieu d'échanger les éléments de T on échange les éléments correspondant de A alors à la fin A contient la permutation cherchée. Les comparaisons ne porteront plus sur T[i] et T[j] mais sur T[A[i]] et T[A[j]].

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
size_t *perm_sort(size_t size, int array[static size])
{
  // On crée et initialise A
  size_t *A=malloc(sizeof(size_t[size]));
  for(size_t i=0; i<size; ++i)
    A[i]=i;
 
  // On «tri», ici j'ai choisi gnome sort pour l'exemple
  size_t i=1,j=2;
  while (i<size) {
    if ( array[ A[i-1] ] > array[ A[i] ] ) {
      swap(A, i, i-1);
      if (--i) continue;
    }
    i=j++;
  }
 
  // éventuellement tu rajoutes 1 à chaque élément de A pour obtenir une permutation
  // qui commence avec 1 et non 0
  ...
 
  return A;
}

Code incomplet non testé juste pour donner l'idée.

**sambia39** · 23/09/2016, 21h43

Bonsoir,

Envoyé par Matt_Houston

Elle n'existe pas dans la bibliothèque standard, mais tu peux - par exemple - encapsuler tes éléments dans un struct indexed { Type data; size_t index; }, initialiser index puis effectuer un qsort sur le tableau. La nouvelle séquence des valeurs de index te donnera la permutation.

Je ne suis pas d’accord sur le principe d’utiliser une structure dès le départ. C’est complexifié la chose pour un résultat qui n’est pas forcements ce que l’on souhaite qu’ils fassent. Il faut voir le problème autrement et se concentrer uniquement sur les notions de tris.

Ce que le primo-postant (collègue enseignant) essayez de faire du moins essayer d’accomplir, est-ce que l’on appelle un tri indirect plus précisément l’implémentation d’un algorithme de tris indirect . C’est-à-dire un tri qui utilise un tableau secondaire indiquant, pour chaque élément du tableau à trier, le rang ou l’indice que celui-ci devrait avoir dans le tableau trié. Ce n’est que par la suite que vous pouvez trier votre tableau grâce à cette séquence et non l’inverse car, la séquence vous permet de réorganiser l’ensemble et obtenir un tableau trié.
Voici comment se présente cet algorithme et son implémentation.

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
 
FUNC_SET_TAB_INDICE( TAB, TAB_INDICE, SIZE_TAB ):
 
ENTIER I = 0
ENTIER J = 0
ENTIER V_VALEUR = 0
ENTIER ID_INDEX = 0
 
POUR I = 0 à (SIZE_TAB-1) FAIRE:
	TAB_INDICE[I] = I
FIN_POUR
 
POUR I = 0 à (SIZE_TAB-1) FAIRE:
	ID_INDEX = TAB_INDICE[I]
	V_VALEUR = TAB[ID_INDEX]
 
	TANT_QUE  0 < J && (V_VALEUR < TAB[TAB_INDICE[J-1]):
		TAB_INDICE[J] = TAB_INDICE[j-1]
		J = J - 1
	FIN_TANT_QUE
	TAB_INDICE[J] = ID_INDEX
FIN_POUR
 
FIN_FUNC_SET_TAB_INDICE

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
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
 
/*
 ============================================================================
 Name        : source.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 23/09/2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
 
 
#include <stdio.h>
#include <stdlib.h>
 
/*
*	Fonction qui fixe les indices. 
*	Elle permet par la suite d’effectuer un tri de 
*	façon indirecte  en déplaçant uniquement 
*	les valeurs des indices.
*/
void f_set_sequence( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;		
	int j = 0;
	int v = 0;			// Variable des valeurs 
	int id = 0;			// Variable des Id
 
	/*
	*	Acquisition des Indices
	*/
	for( i = 0; i < (int)size; i++ )
		TabId[i] = i;
 
	/*
	*	(1) Déplacement des éléments
	*	(2) Placement des indices
	*/
	for( i = 0; i < (int)size; i++ ){
		id = TabId[i];
		v = Tab[id];
 
		j = i;
		//(1)
		while( 0 < j && ( v < Tab[ TabId[j-1]]) ){
			TabId[j] = TabId[j-1];
			j--;
		}
		//(2)
		TabId[j] = id;
	}
}
 
 
 
int main( void ){
 
 
	int Tab[] = { 18, 3, 56, 10 };
	int Itab[4];
	unsigned int i = 0;
	f_set_sequence( Tab, Itab, 4 );
	fprintf( stdout, "Résultat de la séquence de tris\n");
	for( i = 0; i < 4; i++ )
		fprintf( stdout, "%d ", Itab[i] );
	fprintf( stdout, "\nSoit les valeurs suivantes\n");
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d(%d) ", Tab[i],i );
	fprintf( stdout, "\n");
	return EXIT_SUCCESS;
}

Ce qui donne l’implémentation suivante pour la réorganisation des données et la conservation des indices de tableaux:

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
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
/*
 ============================================================================
 Name        : source.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 23/09/2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
 
 
#include <stdio.h>
#include <stdlib.h>
 
/*
*	Fonction qui fixe les indices. 
*	Elle permet par la suite d’effectuer un tri de 
*	façon indirecte  en déplaçant uniquement 
*	les valeurs des indices.
*/
void f_set_sequence( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;		
	int j = 0;
	int v = 0;			// Variable des valeurs 
	int id = 0;			// Variable des Id
 
	/*
	*	Acquisition des Indice
	*/
	for( i = 0; i < (int)size; i++ )
		TabId[i] = i;
 
	/*
	*	(1) Déplacement des éléments
	*	(2) Placement des indices
	*/
	for( i = 0; i < (int)size; i++ ){
		id = TabId[i];
		v = Tab[id];
 
		j = i;
		//(1)
		while( 0 < j && ( v < Tab[ TabId[j-1]]) ){
			TabId[j] = TabId[j-1];
			j--;
		}
		//(2)
		TabId[j] = id;
	}
}
 
 
/*
* 	Fonction qui permet de trier le tableau initial 
* 	grâce au tableau des indices
*	(1) variable de end utilisé pour la permutation
*	(2) variables d’origine utilisée pour la permutation 
*	(3) sauvegarde des valeurs
*	(4) réorganisations 
*/
void f_tris_indirect( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;
	int i_s = 0;
	int i_e = 0; //(1)
	int i_v = 0; //(2)
 
	for( i = 0; i < (int)size; i++ ){
 
		//(3)
		if( i != TabId[i] ){
			i_v = Tab[i];
 
			//(4)
			i_e = i;
			i_s = TabId[i_e];
			while( i != i_s ){
				Tab[i_e] = Tab[i_s];
				TabId[i_e] = i_e;
				i_e = i_s;
				i_s = TabId[i_e];
			}
			Tab[i_e] = i_v;
			TabId[i_e] = i_e;
		}
	}
}
 
/*
*	Programme principale
*/
int main( void ){
 
	int Tab[] = { 18, 3, 56, 10 };
	int Itab[4];
	unsigned int i = 0;
	f_set_sequence( Tab, Itab, 4 );
	fprintf( stdout, "Résultat de la séquence de tris\t:");
	for( i = 0; i < 4; i++ )
		fprintf( stdout, "%d ", Itab[i] );
	fprintf( stdout, "\nSoit les valeurs suivantes\t:");
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d(%d) ", Tab[i],i );
	fprintf( stdout, "\nTableau des valeurs trié \t:");
	f_tris_indirect(Tab, Itab, 4);
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d ", Tab[i]);
	fprintf( stdout, "\nFin de traitement");
	return EXIT_SUCCESS;
}

à bientôt

Permutation permettant de trier un vecteur

C

Vue hybride

Discussions similaires

Partager

Partager