avé le forum

dans un projet d'école nous devons trouver la permutation qui permet de passer d'un tableau à un autre si c'est possible. Par exemple si j'ai le tableau [a d b c] et qu'on nous donne [c a b d] on doit trouver la permutation (2 4 3 1) parce que le a du premier se retrouve en position 2 dans le deuxième, le d en 4, etc ... mais si on me donne [a b c d] et [a b c e] on doit dire que c'est pas possible et tout pareil pour [a b c d] et [a b c d e]. Si y a des éléments identiques alors on doit juste donner une permutation possible par exemple si on part de [a a b c] et qu'on doit aller a [a b c a] on peut donner (1 4 2 3) ou (4 1 2 3) c'est pas grave.

le problème c'est que nous ne savons pas par où commencer et on full bloque sur tout. Vous pouvez nous donner un idée par où commencé svp ?

Il faut commencer par faire les tableaux : celui de départ, celui de fin et celui des permutations ! (As-tu des contraintes spécifique pour ces tableaux ?).

Puis chercher la position du premier caractère du tableau de départ dans le tableau de fin et inscrire cette position dans la première case du tableau de permutation. faire la même chose pour les case suivantes jusqu'à la fin du tableau. Traiter les cas impossible (taille des tableaux différente, caractère absent...) 

bonjour,

c'est pas hypercompliqué, faut juste un peu de rigueur pour le faire proprement.

Trouver une permutation qui trie un tableau est trivial (dans le sens c'est simple et il y a une tonne de littérature là-dessus). Donc si tu as deux tableaux A et B, tu calcules la permutation ta qui trie A, et tb qui trie B. La permutation que tu cherches est p= tb⁻¹ ∘ ta ssi A et B contiennent les mêmes éléments et ont la même taille. Si A et B ont des tailles différentes tu abortes rapidement, sinon tu calcules p et tu vérifies ensuite que A[i] = B[p[i]] pour tout i …

Tu tries en O(n lg n) deux fois, en te débrouillant bien tu peux composer les permutations en O(n) et vérifier en O(n) ce qui au final n'est pas trop mal (àmha).

Donc expliqué comme cela il te faudrait :

• quelque chose qui représente une permutation sur laquelle tu puisses appliquer des opérations comme la composition et l'inversion ;
• quelque chose qui représente un tableau ;
• quelque chose qui représente le chemin pour passer de l'un à l'autre ;

Je verrai bien qqch comme :

enum path_status {PATH_TODO, PATH_OK, PATH_IMPOSSIBLE, PATH_OTHER_ERROR};
struct path {
  struct array *from;
  struct array *to;
  struct perm *perm;
  enum path_status status;
};

avec toute l'API de base qui va autour pour la création, la libération, les accès et au moins :

struct path *path_from_str(const char *from, const char *to);

et si tu as :

struct array {
  size_t size;
  char *elements;
};

struct array *array_from_str(char *str);
...
...

et qqch comme :

struct perm {
  size_t size;
  size_t *perm;
};

...
...

et tu commences par écrire des tests 

bool test_1(void) {

  struct path *p = path_from_str("adbc", "cabd");
  bool res = path_status(p)==PATH_OK && perm_equal(path_permutation(p), perm_from(4, ( (size_t []) {2,4,3,1}) ));
  path_delete(p);
  return res;
}

bool test_2(void) {

  struct path *p = path_from_str("adbc", "abcde");
  bool res = path_status(p)==PATH_IMPOSSIBLE;
  path_delete(p);
  return res;
}

bool test_3(void) {

  struct path *p = path_from_str("abcd", "efgh");
  bool res = path_status(p)==PATH_IMPOSSIBLE;
  path_delete(p);
  return res;
}

bool test_4(void) {

  struct path *p = path_from_str("aabc", "abca");
  bool res = path_status(p)==PATH_OK && (
                              perm_equal(path_permutation(p), perm_from(4, ( (size_t []) {1,4,2,3}) ))
                              ||
                              perm_equal(path_permutation(p), perm_from(4, ( (size_t []) {4,1,2,3}) ))
                            );
  path_delete(p);
  return res;
}

J'aime bien la méthode consistant à partir à un niveau global et rentrer dans les détails peu à peu. Ici, si je devais faire ce travail, je décomposerais en deux parties :

1. D'abord tester si les deux tableaux sont permutables.

2. Si oui, déterminer la permutation.

Puis je décompose la partie 1 :

1-a. Tester si les deux tableaux ont même nombre d'éléments (si non, c'est pas permutable).

1-b. Si oui, tester si les éléments sont les mêmes.

Pour le 1-a c'est pas compliqué.

Comment faire le 1-b ? Il y a deux choses :

1-b(i). Vérifier que chaque tableau a ses éléments distincts.

1-b(ii). Vérifier que tous les éléments du premier tableau se retrouvent dans le second tableau.

(Attention, ce sont des idées naïves, ce n'est pas très optimal...)

Ces vérifications se font avec une double boucle. Par exemple pour 1-b(i) :

// A, B : les deux tableaux
// nbelem : leur nombre d'éléments commun
ok = vrai
Pour i = 0 à nbelem-1
    // On regarde si [i] est présent dans A (normalement non à part en i)
    pas_trouvé = vrai
    Pour j = 0 à nbelem-1
        Si A[i] = A[j] et i <> j : pas_trouvé = faux ; break
    Fin Pour
    Si pas_trouvé = faux :
        ok = faux, break // pas bon
Fin Pour

et on fait pareil avec le tableau B.

Pour 1-b(ii) c'est le même genre de chose, sauf qu'on test A[i] = B[j], et si on trouve quelqu'un, cette fois c'est bon.

Bref, l'idée est de partir du global et rentrer dans les détails petit à petit.

-
Edité par robun 28 février 2022 à 16:16:14

En plus de tester si tous les éléments du tableau A se retrouvent dans le tableau B,
il faut tester si tous les éléments du tableau B se retrouvent dans le tableau A.
Par ex. A=[a, b, c, d] B=[c, a, d, a]
Avec un tableau de fréquences égal à la longueur des deux autres, on place 1 à chaque case [1, 1, 1, 1]
Si on retrouve dans A un élément de B on soustrait 1 à la position trouvée.
Si à la fin, on n'a pas 0 partout, il n'y a pas concordance
Et si c'es A qui contient [a, b, a, d] on fait quoi?
on doit ajouter 1 à la première position trouvée, donc [2, 1, 0, 1]
C'est une ébauche rapide ...

Trouver LES permutations qui ordonnent les deux tableaux, puis les composer (l'une avec l'inverse de l'autre).

La première étape est dérivée du tri  : ordonner la séquence p =  (1 2 .. n)  de façon à ce que  i < j  implique t[p[i]] <= t[p[j]]

Ps: ah, déjà proposé 

-
Edité par michelbillaud 28 février 2022 à 18:44:01

Ou bien, comme semble le suggérer White Crow, faire un tri avec indices des deux tableaux.
Les tableaux ne sont pas triés, seulement les tableaux de leurs indices.
Ils permettent de vérifier si les éléments sont les mêmes et faire la permutation dans un sens ou l'autre (1 vers 2 ou 2 vers 1).

Je dirai même plus, c'est la même chose.

Alors, voici un code minimal où je ne teste pas si les longueurs sont identiques.
Je ne me suis pas cassé la tête sur la façon de saisir les chaînes ni sur la gestion de la mémoire.
J'utilise un tri par insertions. C'est le plus rapide des tris lents ...
Je trie les indices, pas les chaînes elles-mêmes.
Je peux vérifier si les caractères sont les mêmes dans les deux chaînes peu importe la fréquence de chaque caractère
(même fréquences pour les deux chaîne).
On pourrait modifier facilement le code pour permuter autre chose que des caractères
-
#include <stdio.h>
void indexSort(char array[], int index[], int length) {
    for(int i = 0; i < length; i++)
        index[i] = i;
    for(int i = 1; i < length; i++) {
        int m = index[i];
        int j;
        for(j = i; j > 0 && array[m] < array[index[j-1]]; j--)
            index[j] = index[j-1];
        index[j] = m;
    }
}
int main(void) {
    char array1[] = "abcd";
    char array2[] = "cadb";
    int lg = 4;
    int index1[lg];
    int index2[lg];
    indexSort(array1, index1, lg);
    indexSort(array2, index2, lg);
    for(int i = 0; i < lg; i++) {
        if(array1[index1[i]] != array2[index2[i]]) {
            printf("Permutation impossible\n");
            return 1;
        }
    }
    int permutations[lg];
    for(int i = 0; i < lg; i++)
        permutations[index1[i]] = index2[i];
    for(int i = 0; i < lg; i++)
        printf("%d ", permutations[i]);
    printf("\n");
    return  0;
}
-
1 3 0 2
-
le caractère en 0 va en 1, le 1 en 3, le 2 en 0, le 3 en 2.
En C, les indices commencent à 0.

Trouver (efficacement) la permutation qui ordonne un tableau, on peut le faire facilement avec le fonction qsort_r

#define _GNU_SOURCE 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int comparator_r(const void *v1, const void *v2, void *context) {
	const int *p1 = v1, *p2 = v2;
	int *array = context;
	return array[*p1] - array[*p2];
}

void test_qsort_r() 
{
	int array[9] = { 66, 11, 44, 22, 88, 55, 77, 99, 33};
	int perm[9]  = {  0,  1,  2,  3,  4,  5,  6,  7,  8};
	qsort_r(perm, 9, sizeof(array[0]), comparator_r, array);

	for (int i = 0; i < 9; i++) {
		printf("[%d]=%d ", perm[i], array[perm[i]]);
	}
	printf("\n");
} 

parce qu'il faut à la fois passer le tableau à trier, et le tableau de valeurs.

Exécution

[1]=11 [3]=22 [8]=33 [2]=44 [5]=55 [0]=66 [6]=77 [4]=88 [7]=99 

Mais bon, c'est une extension GNU. On peut le faire avec qsort: au lieu de faire du "contexte" un paramètre du comparateur, on utilise dans le comparateur une variable globale

void * comparator_context;

int comparator(const void *v1, const void *v2) {
	const int *p1 = v1, *p2 = v2;
	int *array = comparator_context;
	return array[*p1] - array[*p2];
}

void test_qsort() 
{
	int array[9] = { 66, 11, 44, 22, 88, 55, 77, 99, 33};
	int perm[9]  = {  0,  1,  2,  3,  4,  5,  6,  7,  8};
	comparator_context = array;
	qsort(perm, 9, sizeof(array[0]), comparator);

	for (int i = 0; i < 9; i++) {
		printf("[%d]=%d ", perm[i], array[perm[i]]);
	}
	printf("\n");
} 

ce qui est typiquement le genre de choses malpropre à éviter parce qu'elles conduisent à du code non réentrant (si plusieurs threads font des tris en même temps, ça va pas le faire).

C'est sans doute pour ça qu'ils ont appelé qsort_r, avec le suffixe habituel des fonctions réentrantes qui ont été ajoutées (exemple strtok_r). Par lui-même, qsort est réentrant, mais si on veut l'utiliser on est souvent obligé de faire un hack qui ne l'est pas. qsort_r évite ça.

PS: complément  à partir d'un algo de tri, comment passer par étapes à un tel tri "réentrant", dans https://www.mbillaud.fr/notes/permutation-tri.html

-
Edité par michelbillaud 1 mars 2022 à 11:35:09

Une solution sans tri. C'est un peu vite fait ! Je fait fait un pointage de ce qui a été traité directement dans le tableau end par simplification (mise en négatif du caractère, on peut faire le pointage autrement). C'est plus un algo qu'un code C ! Ça traite tout les cas (du moins je crois, j'ai pas trop testé) ! 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void printTab(int tab[], int taille)
{
    int i;
    for(i=0; i<taille; i++)
    {
        printf("%d  ", tab[i]);
    }
}


int main(void)
{
    char start[] = "abca";
    char end[] = "caba";

    size_t size = strlen(start);
    if(strlen(end)!=size)
    {
        puts("Impossible !");
        return 0;
    }

    int* perm = calloc(size, sizeof(int));

    for(size_t i=0; i<size; i++)
    {
        for(size_t j=0; j<size; j++)
        {
            if(start[i]==end[j])
            {
                end[j]= -end[j];
                perm[i]=j+1;
                break;
            }
        }
        if(perm[i]==0)
        {
            puts("Impossible !");
            return 0;
        }
    }

    printTab(perm, size);

    return 0;
}

@rouIoude:
Tu as exprimé en plus clair ce que je proposais dans mon premier message.

Ok, J'avoue que je n'ai pas trop lu les messages !

Par contre tu as eu la bonne idée "d'effacer" le caractère en sortie pour éviter un problème si c'est en double, comme "aabc" vers "baca"

-
Edité par PierrotLeFou 1 mars 2022 à 19:26:50

C'est bien pour ça que je l'ai fait.

merki le forum