Empêcher l'allocation de mémoire dans la génération de combinaison récursive

Liasse

(Désolé pour le titre, ce n'est pas le meilleur descriptif)

Je joue avec la théorie des graphes et je génère toutes les combinaisons possibles d'un ensemble donné de nombres d'entrée. Compte tenu de l'ensemble d'entrée {2,3,4}, mes combinaisons possibles (dont il y a 3!), sont:

Arbre

La solution récursive suivante fonctionne, mais je n'aime pas le fait que je doive "copier" le vecteur d'entrée pour "supprimer" l'élément qui représente le nœud que je suis afin d'éviter de l'inclure à nouveau pour la sortie. Les éléments que je vais générer sont stockés dans vecValuestandis que les éléments parmi lesquels je peux actuellement choisir sont stockés dans vecInput:

void OutputCombos(vector<int>& vecInput, vector<int>& vecValues)
{
    // When hit 0 input size, output.
    if (vecInput.size() == 0)
    {
        for (int i : vecValues) cout << i << " ";
        cout << endl;
    }
    size_t nSize = vecInput.size();
    for (vector<int>::iterator iter = begin(vecInput); iter != end(vecInput); ++iter)
    {
        auto vecCopy = vecInput;
        vecCopy.erase(find(begin(vecCopy), end(vecCopy), *iter));
        vecValues.push_back(*iter);
        OutputCombos(vecCopy, vecValues);
        vecValues.pop_back();
    }
}

void OutputCombos(vector<int>& vecInput)
{
    vector<int> vecValues;
    OutputCombos(vecInput, vecValues);
}

int main()
{
    vector<int> vecInput{ 2,3,4 };
    OutputCombos(vecInput);
    return 0;
}

Comme prévu dans mon arbre d'espace d'états, la sortie est

2 3 4 2 4 3 3 2 4 3 4 2 4 2 3 4 3 2

Comment puis-je contourner cela sans avoir à faire une copie du vecteur pour chaque appel récursif s'il vous plaît?

Liasse

Après de nombreuses études, j'ai trouvé l'inspiration dans cet article qui m'a donné la solution ultime. L'idée est que nous conservons un vecteur de Booleanvaleurs qui indique si une valeur particulière a été utilisée ou non dans la combinaison; de cette façon, nous n'avons pas besoin de supprimer l'élément que nous avons déjà utilisé, il n'y a donc pas de surcharge d'allocation de mémoire.

Ainsi, lors de la construction de la branche {2,4,3}, si nous y arrivons {2,4}, vecTakensera {true, false, true}et nNumBoolsSetsera 2. Ainsi, lorsque nous bouclerons, nous n'utiliserons que l'élément à l'index 1 de vecInputpuisque c'est le seul élément qui n'a pas été utilisé comme dicté par vecTaken.

void OutputCombos(vector<int>& vecInput, vector<int>& vecValues, vector<bool>& vecTaken, int& nNumBoolsSet)
{
    size_t nSize = vecInput.size();
    if (nNumBoolsSet == nSize)
    {
        for (int i : vecValues) cout << i << " ";
        cout << endl;
        return;
    }
    for (vector<int>::size_type i = 0; i < nSize; ++i)
    {
        if (vecTaken[i] == false)
        {
            vecValues.push_back(vecInput[i]);
            vecTaken[i] = true;
            ++nNumBoolsSet;
            OutputCombos(vecInput, vecValues, vecTaken, nNumBoolsSet);
            vecTaken[i] = false;
            vecValues.pop_back();
            --nNumBoolsSet;
        }
    }
}

void OutputCombos(vector<int>& vecInput)
{
    vector<int> vecValues;
    vector<bool> vecTaken(vecInput.size(), false);
    int nNumBoolsSet = 0;
    OutputCombos(vecInput, vecValues, vecTaken, nNumBoolsSet);
}

int main()
{
    vector<int> vecInput{ 2,3,4 };
    OutputCombos(vecInput);
}

Cet article est collecté sur Internet, veuillez indiquer la source lors de la réimpression.

En cas d'infraction, veuillez [email protected] Supprimer.

modifier le
0

laisse moi dire quelques mots

0commentaires
connexionAprès avoir participé à la revue

Articles connexes

Problème dans l'allocation de mémoire pour le pointeur de la structure

Comment trouver l'utilisation maximale de la mémoire dans une génération Maven

Comment empêcher la génération de JAXBElement <String> dans un client CXF Web Service?

GoLang: allocation de mémoire pour l'héritage de type et la conversion dans Go

Comment empêcher l'injection SQL lors de la génération dynamique de DDL?

L'allocation de mémoire de la structure JNA dans le tableau est incorrecte

Comment empêcher la régénération du mot de passe?

Comment empêcher la génération d'éléments XML «nil» dans le client de service Web de savon?

Échec de l'allocation d'une mémoire tampon gérée de 268435456 octets. La quantité de mémoire disponible peut être faible

Empêcher la dégradation du tableau lors de l'allocation de mémoire sur le tas?

Réallocation de la mémoire dans les vecteurs

Comment empêcher la génération de versions pour l'application dans Crashlytics avec la version Gradle

L'allocation de mémoire en C # n'alloue pas réellement de mémoire

Empêcher la génération de fichiers vides à l'aide de l'activité de copie Azure Data Factory

Énorme allocation de mémoire gérée lors de la lecture (itération) de données avec DbDataReader

Empêcher l'allocation de mémoire dans la génération de combinaison récursive

Erreur lors de la régénération d'un tableau: dépassement de la mémoire tampon lors de l'écriture dans

Utilisation de pointeurs dans l'allocation de mémoire dynamique

Existe-t-il un moyen d'interroger ce que ferait la réallocation ou de l'empêcher de copier toute la mémoire sous Windows et Linux?

Comment empêcher la croissance de l'utilisation de la mémoire lors de la mise à jour des pondérations et des biais dans un modèle Pytorch

Allocation de mémoire dans la pile

Réduction de l'allocation mémoire d'un générateur dans Julia

NullPointer dans la méthode récursive (obtention du chemin général de l'arborescence)

Haxe Javascript : Empêcher la génération de '$bind' ?

Comment puis-je empêcher l'attrition de la mémoire dans MATLAB ?

Importance de l'attribution de la taille pendant l'allocation de mémoire dans Malloc

Comment empêcher la génération automatique de @UpdateTimestamp dans Spring Boot

gestion de la mémoire dans l'analyseur C généré par BNFC

Empêcher l'alias de mémoire lors de la copie de blocs mem en C

TOP liste

  1. 1

    Comment désactiver ou activer le balayage de Viewpager dans Android

  2. 2

    Créer une table externe Hive à partir de fichiers de parquet partitionnés dans Azure HDInsights

  3. 3

    Comment changer le navigateur par défaut en Microsoft Edge pour Jupyter Notebook sous Windows 10 ?

  4. 4

    Enregistrer le chemin de l'image de la galerie vers la base de données de la salle et l'afficher dans la liste des recycleurs

  5. 5

    Concaténer des variables dans ansible

  6. 6

    ESP8266 HADRWARE MINUTERIE, USA pour cocher une macro étrange

  7. 7

    Stop jQuery execution after one time execution

  8. 8

    Filtrer les données en fonction des conditions d'une trame de données

  9. 9

    Comment analyser un fichier avec un tableau d'objets JSON en utilisant Node.js?

  10. 10

    obtenir le nombre de marqueur affiché sur la carte

  11. 11

    Comment centrer un div tout en utilisant la transition et transformer avec l'échelle

  12. 12

    Comment utiliser le stockage local et le supprimer lorsqu'il n'est pas nécessaire

  13. 13

    Redirection HTTP vers HTTPS dans Java à l'aide de HTTPURLConnection

  14. 14

    Comment envoyer plusieurs variables de la lame au contrôleur

  15. 15

    Comment définir du texte dans un QLabel et afficher les caractères '<>'?

  16. 16

    Échec de l'exécution de 'insertBefore' sur 'Node': le paramètre 1 n'est pas de type 'Node'

  17. 17

    System.Data.SqlClient.SqlException: 'Nom de colonne non valide' ApplicationRoleId '.'

  18. 18

    Générer une variable binaire avec une corrélation prédéfinie avec une variable déjà existante

  19. 19

    la mise en place Spring dans Eclipse - Échec d'initialisation de contexte

  20. 20

    comment afficher un bouton au-dessus d'un autre élément ?

  21. 21

    Uncaught TypeError: map n'est pas une fonction dans Reactjs avec Firebase

chaudétiquette

Archive