Principe simple mais pourtant terriblement prise de tête

[Ubiquitous]

Bonsoir à tous,

Prenons un tableau en entrée : t[4] = {1,1,1,1}.

Je souhaiterais obtenir en sortie ceci :
{0,1,1,1}
{1,0,1,1}
{1,1,0,1}
{1,1,1,0}

{0,0,1,1}
{0,1,0,1}
{0,1,1,0}
{1,0,1,0}
{1,1,0,0}
{1,0,0,1}

{0,0,0,1}
{0,0,1,0}
{0,1,0,0}
{1,0,0,0}

{0,0,0,0}

L'idée est de remplir au fur et à mesure l'ensemble du tableau initial avec des 0.
Malheureusement, algorithmiquement, je n'arrive pas à en tirer quelque chose, que ce soit en itératif ou récursif. Des pistes de recherches ou des idées seraient bienvenues afin de résoudre mon problème.

Bonne soirée à tous

Bien cordialement
-----

[Jack]

Autant dans les 2 groupes de 4 lignes, il y a une logique, autant dans le groupe de 6, je n'en trouve aucune. Quel est l'intérêt de générer ces combinaisons plutôt que de les définir directement?

[pm42]

autant dans le groupe de 6, je n'en trouve aucune

J'ai regardé vite mais ce n'est pas l'ensemble des permutations de {0,0,1,1} ? Et chaque bloc les permutations avec 1, 2 et 3 fois 1 ?

[Jack]

Il faudrait savoir si l'ordre doit être respecté

[A voir en vidéo sur Futura]

[pm42]

Il faudrait savoir si l'ordre doit être respecté

Oui. On va voir si la personne qui s'est inscrite pour poster sa question revient pour faire le suivi.

[Ubiquitous]

J'ai regardé vite mais ce n'est pas l'ensemble des permutations de {0,0,1,1} ? Et chaque bloc les permutations avec 1, 2 et 3 fois 1 ?

Oui c'est exactement l'idée, il s'agit de l'ensemble des permutations de 0 seulement. Mais attention, je ne veux pas permuter un 0 avec un 1 mais REMPLACER un 1 avec un 0. C'est à dire que si le tableau en entrée est t[3] = {1,2,3}, la sortie serait, sans ordre précis :

{0,2,3}
{1,0,3}
{1,2,0}

{0,0,3}
{0,2,0}
{1,0,0}

{0,0,0}

Le but serait que cela marche pour n'importe quel taille de tableau en entrée.

Pour répondre à la question de quel est l'intérêt ? Et bien c'est une idée de solution que j'ai trouvée pour résoudre une partie d'un problème donné ouvert, mais pour laquelle malgré moultes tentatives, je n'arrive pas à implémenter algorithmiquement.

[pm42]

Cela se programme récursivement je pense.
Tu as un nombre n de zéros
pour chaque élément de la liste
- tu construis une liste sans cet élément
- tu appelles la même méthode avec cette sous-liste et n
- pour chaque résultat tu réinsère l'élément supprimé au même endroit
- tu appelles la même méthode avec cette sous-liste et n - 1
- pour chaque résultat tu réinsère 0 à l'endroit de l'élément supprimé
- si n = 0 ou la liste est vide, tu ne fais rien

Et tu peux faire ça avec n variant de 1 à la taille de la liste (ou optimiser et faire la taille de la liste - 1 et renvoyer des 0 pour le dernier).
On peut optimiser en ne construisant pas physiquement la sous-liste mais en passant à la méthode la liste des éléments déjà remplacés par des 0 et donc à ne pas traiter, idéalement comme un tableau de booléens ou un bitfield mais il faut raffiner.

Là aussi à vérifier, j'ai un peu la flemme de le coder.

[Ubiquitous]

Salut,

Grâce à tes indications, j'ai tenté de réaliser une ébauche de code. Voici ce que j'ai compris de tes indications :

#include <stdio.h>

void complete(int *t, int n){
    if (n == 0){
        for (int k=0; k<4; k++){
            printf("%d ",t[k]);
        }
        printf("\n");
    }
    
    int tmp[4] = {0};
    for (int i=0; i<4; i++){
        if(i != n){
            tmp[i] = t[i];
        }
    }
    complete(tmp,n);
    
    tmp[n] = t[n];
    complete(tmp,n-1);
    
    tmp[n] = 0;
    
}


int main(int argc, const char * argv[]) {
    
    int t[4] = {1,1,1,1};
    complete(t,4);
    
    return 0;
}

Quels sont les modifications nécessaires à faire selon toi (car même si je sais que ce code ne peut pas marcher, je ne parviens pas à visualiser la manière de faire pour le faire marcher).

Bonne journée

[pm42]

Je ne sais pas si j'aurais le temps de creuser mais si j'ai 10 min, je regarde.

[minushabens]

Tu peux engendrer tous les vecteurs de la bonne longueur (disons k) et contenant 0 ou 1, et en faire le produit avec ton vecteur de départ. Les vecteurs en 0,1 sont les écritures binaires des nombres de 0 à 2^k - 1.

[Ubiquitous]

Ok ça marche.
Je continue à chercher de mon côté.

Bonne soirée

[bdom001]

Bonjour,

Jack avait demandé si l'ordre avait une importance. Pour ma part, la réponse à cette question, du moins comme je l'ai comprise, n'est toujours pas claire :

Donc est-ce que cet ordre là :

{0,0,1,1}
{0,1,0,1}
{0,1,1,0}
{1,0,1,0}
{1,1,0,0}
{1,0,0,1}

doit être respecté, ou bien alors est-ce que celui-là :

{0,0,1,1}
{0,1,0,1}
{0,1,1,0}
{1,0,0,1}
{1,0,1,0}
{1,1,0,0}

peut convenir aussi ?

Cordialement

[bdom001]

Bonjour,

bon, j'ai élaboré un algorithme fonctionnant pour une dimension n quelconque, qui pour l'entrée {1,2,3,4,5} (dimension 5) produit la sortie :

{0, 2, 3, 4, 5}
{1, 0, 3, 4, 5}
{1, 2, 0, 4, 5}
{1, 2, 3, 0, 5}
{1, 2, 3, 4, 0}
_______________

{0, 0, 3, 4, 5}
{0, 2, 0, 4, 5}
{0, 2, 3, 0, 5}
{0, 2, 3, 4, 0}
{1, 0, 0, 4, 5}
{1, 0, 3, 0, 5}
{1, 0, 3, 4, 0}
{1, 2, 0, 0, 5}
{1, 2, 0, 4, 0}
{1, 2, 3, 0, 0}
_______________

{0, 0, 0, 4, 5}
{0, 0, 3, 0, 5}
{0, 0, 3, 4, 0}
{0, 2, 0, 0, 5}
{0, 2, 0, 4, 0}
{0, 2, 3, 0, 0}
{1, 0, 0, 0, 5}
{1, 0, 0, 4, 0}
{1, 0, 3, 0, 0}
{1, 2, 0, 0, 0}
_______________

{0, 0, 0, 0, 5}
{0, 0, 0, 4, 0}
{0, 0, 3, 0, 0}
{0, 2, 0, 0, 0}
{1, 0, 0, 0, 0}

Est-ce que cela correspond au cahier des charges ?

Cordialement

[Ubiquitous]

Salut !

Oui c'est exactement cela, je n'ai rien à redire, la sortie est parfaite.

[bdom001]

Bonjour,
l'idée, c'est d'avoir un tableau d'index contenant autant d'élément qu'il doit y avoir de zéro sur une ligne, chaque élément de ce tableau correspondant à une valeur d'index permettant de référencer un élément dans le tableau d'entrée.

Puis, en commençant par la fin du tableau d'index (TI), on fait varier la valeur de l'élément TI[i]
- de TI[i-1]+1 à sa valeur maximum incluse (n-1); si i > 0
- de 0 à n-1; si i=0

Pour cela j'ai utilisé la récursivité, qui me paraît plus simple et aussi par réflexe (il y a sûrement moyen de faire autrement), et j'ai transcris cet algorithme en C/C++ que je vous livre directement car je ne pense pas que cela soit un exercice pour étudiant.

 Cliquez pour afficher

void Enumerate(const int inputTable[], int iTableSize, int nbZeros);
void Enumerator(const int inputTable[], int inputTableSize, int zeroIndexes[], int nbZeros, int pivot);
void InitTable(int outputTable[], const int inputTable[], int nSize, int zeroIndexes[], int nbZeros);
void OutputTable(const int Table[], int nSize);

int main()
{
    int Table[] = { 1, 2, 3, 4, 5 };
    int nbItem = sizeof(Table) / sizeof(int);

    for (int nbZeros = 1; nbZeros < nbItem; ++nbZeros)
    {
        Enumerate(Table, nbItem, nbZeros);
        printf_s("________________________\n\n");
        OutputDebugStringA("________________________\n\n");
    }

    printf("Press any key to exit ...");
    _getch();
    return 0;
}

void Enumerate(const int inputTable[], int iTableSize, int nbZeros)
{
    int* zeroIndexes = new int[nbZeros];
    for (int i = 0; i < nbZeros; ++i)
        zeroIndexes[i] = i;

    Enumerator(inputTable, iTableSize, zeroIndexes, nbZeros, 0);

    delete[]zeroIndexes;
}

void Enumerator(const int inputTable[], int iTableSize, int zeroIndexes[], int nbZeros, int pivot)
{
    int *outTable = new int[iTableSize];
    int iStart = (pivot == 0) ? 0 : zeroIndexes[pivot - 1] + 1;

    for (zeroIndexes[pivot] = iStart; zeroIndexes[pivot] < iTableSize; ++zeroIndexes[pivot])
    {
        if (pivot == nbZeros - 1) // Si on atteint la fin du tableau d'index, on peut envisager une sortie
        {
            InitTable(outTable, inputTable, iTableSize, zeroIndexes, nbZeros);
            OutputTable(outTable, iTableSize);
        }
        else            // Sinon on continue le processus récursif
            Enumerator(inputTable, iTableSize, zeroIndexes, nbZeros, pivot + 1);
    }

    delete[]outTable;
}

void InitTable(int outputTable[], const int inputTable[], int nSize, int zeroIndexes[], int nbZeros)
{
    for (int idx = 0; idx < nSize; ++idx)
        outputTable[idx] = inputTable[idx];

    for (int idxZero = 0; idxZero < nbZeros; ++idxZero)
        outputTable[zeroIndexes[idxZero]] = 0;
}

void OutputTable(const int Table[], int nSize)
{
    int nBuffSize = 5 * nSize + 3;
    char* outBuffer = new char[nBuffSize];
    char* sOutput = outBuffer;
    int nbPrintedChar = sprintf_s(sOutput, nBuffSize, "{");
    sOutput += nbPrintedChar;
    nBuffSize -= nbPrintedChar;

    for (int i = 0; i < nSize; ++i)
    {
        nbPrintedChar = sprintf_s(sOutput, nBuffSize, "%d", Table[i]);
        sOutput += nbPrintedChar;
        nBuffSize -= nbPrintedChar;
        if (i < nSize - 1)
        {
            nbPrintedChar = sprintf_s(sOutput, nBuffSize, ", ");
            sOutput += nbPrintedChar;
            nBuffSize -= nbPrintedChar;
        }
    }

    sprintf_s(sOutput, nBuffSize, "}\n");
    printf_s("%s", outBuffer);
    OutputDebugStringA(outBuffer);
    delete[]outBuffer;
}

À noter que la fonction 'OutputTable' fonctionne comme une "callback". Elle est appelée autant de fois que nécessaire avec les bonnes valeurs de sortie. Vous pouvez la modifiez comme vous le souhaitez en utilisant son paramètre d'entrée (const int Table[]) pour accéder aux lignes générées automatiquement.

Pour toute question, n'hésitez pas ...

Cordialement

[Ubiquitous]

Merci beaucoup !

Je vais étudier votre code afin d'en comprendre plus précisément les rouages.

A savoir que je me suis concocté un petit code à ma sauce que voici. Si vous avez des remarques à faire dessus, je suis preneur.

 Cliquez pour afficher

#define NB_CASE_BOARD 8

int checkSave(FILE* save, int *t, int *count_lines){
    int tobeload[NB_CASE_BOARD] = {0};
    int c=0;
    int count = 0;
    
    while(c < *count_lines){
        count = 0;
        if (c==0){
            rewind(save);
        }

        fscanf(save, "%d %d %d %d %d %d %d %d", &tobeload[0], &tobeload[1], &tobeload[2], &tobeload[3], &tobeload[4], &tobeload[5], &tobeload[6], &tobeload[7]);
        
        for (int k=0; k<NB_CASE_BOARD; k++){
            if(tobeload[k] == t[k]){
                count++;
            }
        }
        
        if (count == NB_CASE_BOARD){
            return 0;
        }
        c++;
    }
    return 1;
}

void permut(int n, int *t,FILE* save,int *count_lines){
    int tmp;

    if (n==1){

        if (checkSave(save, t, count_lines) == 1){
            for (int k=0; k<NB_CASE_BOARD; k++){
                fprintf(save, "%d ",t[k]);
            }
            fprintf(save,"\n");
            *count_lines = *count_lines + 1;
        }
        
    } else {
        for (int i=0; i<n-1; i++){
            permut(n-1,t,save, count_lines);
            if (n%2==0){
                tmp = t[i];
                t[i] = t[n-1];
                t[n-1] = tmp;
            } else{
                tmp = t[0];
                t[0] = t[n-1];
                t[n-1] = tmp;
            }
        }
        permut(n-1,t,save,count_lines);
    }
}

void add0(int *t){
    int ind = 0;
    for (int i=0; i<NB_CASE_BOARD; i++){
        if(t[i] == 1){
            ind = i;
        }
    }
    t[ind] = 0;
}



int main(int argc, const char * argv[]) {
    FILE* save = NULL;
    save = fopen("save4achievement3.txt", "w+");
    int t[NB_CASE_BOARD] = {1,1,1,1,1,1,1,1};
    int count_lines = 0;
    for (int i=0; i<=NB_CASE_BOARD; i++){
        permut(NB_CASE_BOARD, t,save, &count_lines);
        add0(t);
    }
    
    return 0;
}

Si je ne comprends pas quelque chose, je vous recontacte.

Merci encore et bonne soirée

Cordialement

[bdom001]

Bonjour,
j'ai jeté in œil sur votre code, mais c'est toujours un peu délicat de faire de la rétro-ingénierie sur du code qui n'est pas commenté/documenté, et qui plus est non fonctionnel.

Parfois/souvent il est peu aisé, voire quasi impossible de relire son propre code si on l'a laissé reposer trop longtemps et si ce dernier n'est pas assez explicite.

Un conseil allant dans ce sens : Pour chaque procédure/fonction :
- Décrire globalement dans le langage courant (français, ...) ce qu'est censé accomplir la fonction/procédure en question, sans oublier la valeur de retour;
- Décrire de la même manière chacun des paramètres d'entrée/sortie.
- Utiliser des noms de variable les plus explicites possible.
- Écrire du code qui ne soit pas incompatible avec les règles d'encapsulation, c'est-à-dire au moins écrire des fonctions dont la totalité des paramètres contiennent toutes les données qui vont lui permettre de mener sa tâche à bien. (Par exemple, votre fonction 'add0' n'est pas autonome dans le sens où l'un de ses paramètres dépend d'une valeur qui est externe, la taille d'un tableau en l'occurrence)

Un exemple parmi d'autres, en ce qui concerne la fonction 'add0' prototypée de la manière suivante : void add0(int* t), vous pourriez plutôt écrire : (sans aucunement juger de la pertinence de cette fonction, dans un sens ou dans l'autre)

////////////////////////////////
//
//        Nom de fonction  : add0

void add0(int* Tableau, int size)

/*        Cette fonction prend en entrée/sortie un tableau d'entier d'une taille donnée, et annule le premier élément
/* non nul de ce tableau en partant de la fin.
/*
/* Paramètres :
/*        Tableau : (entrée/sortie) Le tableau d'entier à traiter;
/*        size : (entrée) La taille en nombre d'éléments du tableau à traiter.
*/
{
    for (int i=size-1; i>=0; --i)
    {
        if (Tableau[i]!=0)
        {
            Tableau[i] = 0;
            return;
        }
    }
}

Vous remarquerez qu'après avoir expliqué clairement ce qu'une fonction est censée faire, on peut éventuellement la réécrire différemment et plus efficacement.


Malgré tout, d'après ce que j'ai pu voir, votre code souffre de manière générale, de ce que jaurais tendance à appeler une mauvaise
stratégie de résolution, qui pour les raisons que j'ai évoquées plus haut reste difficile à discerner.
Mais deux choses me gènent à ce sujet:
1) Votre fonction principale fait des permutations sur le tableau initial, alors qu'il m'avait semblé que les éléments initiaux du tableau devaient rester à leur place quand ils n'étaient pas remplacés par des zéros.
2) Vous avez besoin de relire des résultats que vous avez stockés dans un fichier. Ça fait dresser les cheveux sur la tête

Cordialement

[bdom001]

Bonjour,
je me permets de faire un petit "up" sur le sujet car j'ai cru comprendre que vous vouliez vous atteler à comprendre les rouages de mon code, et il se trouve que j'y ai détecté un bug mineur dans la fonction 'Enumerator' qui fait qu'on peut dire mon code est tombé en marche, ainsi que deux autres maladresses qui peuvent obscurcir certaines choses et dégrader (modérément) les performances.

Donc, trois choses:

1)Fonction 'Enumerator':

1.1) Le bug mineur : Je cherche à faire varier la position de tous les zéros, depuis leur position de départ jusqu'à la position maximale dans le tableau de sortie. Ça tombe bien quand il n'y a qu'un seul zéro, mais quand il y en a deux ou plus, ça n'a pas de sens. Heureusement (ou pas finalement), ça n'empêche pas le programme de fournir le bon résultat dans la mesure où les cas inconsistants se traduisent par l'exécution de boucles "à vide" (sans exécution d'instruction)

1.2) Maladresse par rapport à l'occupation mémoire : J'avais pris le parti d'allouer dynamiquement le tableau de sortie (outTable) sur le tas (par opposition à la pile), ce qui est généralement une bonne idée pour économiser la pile dont la récursivité peut se montrer très friande. Mais le souci est que je le fais au début de la fonction, donc systématiquement. Si la pile est de toute façon économisée, ce n'est pas le cas pour le reste de la mémoire.

2) Fonction 'Enumerate' :
La correction de bugs au cours de la première phase de développement avait rendu caduque la nécessité d'initialiser le tableau d'index des zéros au tout début. J'avais oublié de la retirer.

Voilà, je pense que c'est bon maintenant.
Sinon, encore une fois, en ce qui concerne votre code, je veux bien essayer d'émettre un avis critique, mais d'abord il faut que vous explicitiez clairement en "bon français" la stratégie que vous voulez adopter.

Cordialement

PS. Version corrigée de mon code (avec en gras ce qui concerne le bug mineur) :

void Enumerate(const int inputTable[], int iTableSize, int nbZeros)
{
    int* zeroIndexes = new int[nbZeros];

    // Suppression de l'initialisation du tableau d'index des zeros devenue inutile
    // consistant à mettre en commentaire les deux lignes qui suivent
    //for (int i = 0; i < nbZeros; ++i)
    //    zeroIndexes[i] = i;

    Enumerator(inputTable, iTableSize, zeroIndexes, nbZeros, 0);

    delete[]zeroIndexes;
}

void Enumerator(const int inputTable[], int iTableSize, int zeroIndexes[], int nbZeros, int pivot)
{
    int iStart = (pivot == 0) ? 0 : zeroIndexes[pivot - 1] + 1;
    int nbZeroRemaining = nbZeros - pivot - 1;
    int nMax = iTableSize - nbZeroRemaining;

    for (zeroIndexes[pivot] = iStart; zeroIndexes[pivot] < nMax; ++zeroIndexes[pivot])
    {
        if (pivot == nbZeros - 1)
        {
            int *outTable = new int[iTableSize];
            InitTable(outTable, inputTable, iTableSize, zeroIndexes, nbZeros);
            OutputTable(outTable, iTableSize);
            delete[]outTable;
        }
        else
            Enumerator(inputTable, iTableSize, zeroIndexes, nbZeros, pivot + 1);
    }
}

[Ubiquitous]

Bonsoir,

Merci encore à toi bdom001.

Pas besoin de justifier tes critiques envers mon code puisqu'elles sont constructives. J'en prends note et je tenterais d'améliorer mon style de code à l'avenir afin d'être le plus compréhensible possible et par tous.

Sinon, mon problème est résolu, je peux continuer à coder sereinement

Bonne soirée

Cordialement