Trouver toutes les combinaisons, en utilisant au moins n éléments d'avant l'indice j

Question

algorithme désir

Je suis en train d'écrire un algorithme qui trouve toutes les combinaisons de longueur k des éléments d'un tableau, mais il faut aussi utiliser n articles avant index j, pour autant de ces (n,j) paires que nous désirons.

Exemples

1. Trouver toutes les deux combinaisons d'articles de {1,2,3,4} en utilisant au moins un élément avant deux index (aka restrictions = {{1,2}}). Cela devrait entraîner {{1,2},{1,3},{1,4},{2,3},{2,4}}.

2. Trouvez les trois combinaisons d'éléments de {1,2,3,4,5,6,7} en utilisant au moins un élément avant l'index 2 et deux avant l'index 4, alias restrictions = {{1,2},{2,4}}.

Progress

Je suis en mesure de trouver toutes les combinaisons de choisir un élément chacun d'un groupe d'ensembles.

void add_combinations_to(vector<int> prefix, vector<vector<int>>::iterator start, 
         vector<vector<int>>::iterator stop, vector<vector<int>>& ret) { 
    if(start == stop) {ret.push_back(prefix); return;} 
    for(auto v : *start) { 
     auto next = prefix; 
     next.push_back(v); 
     add_combinations_to(next, start + 1, stop, ret); 
    } 
}; 

int main() { 
    vector<vector<int>> v{{1,2},{3,4}}; 
    vector<vector<int>> ret; 
    vector<int> init{}; 
    add_combinations_to(init, v.begin(), v.end(), ret); 
    // ret now contains {{1,3},{1,4},{2,3},{2,4}} 
} 

Je pense qu'il y a un moyen de prolonger cela. Pour l'instant je dois prendre du recul, mais le conseil serait génial. Pour la plupart, cela est juste un

Answer 1

Comme de nombreux problèmes d'énumération de séquence, celui-ci cède à l'algorithme standard de l'énumération lexicographique (cité de Algorithm for "consolidating" N items into K):

• Commencez par la plus petite séquence possible lexicographique
• Bien que possible:
  • a. Balayez en arrière pour trouver le dernier élément qui pourrait être augmenté. ("Pourrait être" signifie que l'augmentation de cet élément entraînerait toujours le préfixe d'une séquence valide.)
  • b. Incrémenter cet élément à la plus grande valeur possible suivante
  • c. Remplissez le reste de la séquence avec le plus petit suffixe possible.

S'il n'y a pas d'autres restrictions, la séquence j pourrait être p == p0, p1, …, pj−1 longueur-préfixe d'une combinaison de k longueur-n choses ssi k−j < n−pj−1. Nous pouvons réécrire cela comme pj−1 < n − k + j).

Ainsi, la simple fonction suivante accomplirait les étapes a et b de l'algorithme générique ci-dessus pour un k sans restriction, n combinaison:

/* Finds the (lexicographically) next prefix of a k-combination from n 
* values, and returns the length of that prefix. 
* If there is no possible next prefix, returns 0. 
* Note: k is implicit in the length of the combination 
*/ 
size_t nextPrefix(std::vector<size_t>& comb, size_t n) { 
    size_t k = comb.size(); 
    for (size_t j = k; j;) { 
    --j; 
    if (comb[j] < n - k + j) { 
     ++comb[j]; 
     return j + 1; 
    } 
    } 
    return 0; 
} 

Pour se déplacer sur le problème réel, nous notons que toute restriction de la forme "la combinaison comprend ki des premières valeurs ni" finira par être exactement le même test, puisque cette restriction pourrait être reformulée comme "le préfixe ki-longueur est une combinaison de ni valeurs."

On pourrait donc remplacer le paramètre n dans la fonction ci-dessus avec un vecteur de paires (où la dernière paire est précisément <k, n>):

size_t nextPrefix(std::vector<size_t>& comb, 
        std::vector<std::pair<size_t, size_t>> const& restrictions) { 
    for (size_t j = comb.size(); j;) { 
    --j; 
    /* Test all applicable conditions */ 
    if (std::all_of(restrictions.begin(), restrictions.end(), 
        [&j, &comb](std::pair<size_t, size_t> const& rest) { 
         return j >= rest.first 
          or comb[j] < rest.second - rest.first + j;})) { 
     ++comb[j]; 
     return j + 1; 
    } 
    } 
    return 0; 
} 

(Ce n'est pas optimale, évidemment lieu de vérifier tous. les restrictions sur chaque élément, nous pourrions simplement calculer un simple vecteur de valeurs maximales, puis tester l'élément par rapport à ce maximum.)

Pour générer réellement les séquences, nous devons être en mesure de remplir le suffixe (le dernier étape de l'algorithme générique) et construire la boucle:

void firstSuffix(std::vector<size_t>& comb, size_t pfx_length) { 
    size_t val = pfx_length ? comb[pfx_length - 1] + 1 : 0; 
    for (auto it = comb.begin() + pfx_length; it != comb.end(); ++it) 
    *it = val++; 
} 

Et nous pouvons écrire la boucle:

int main() { 
    std::vector<std::pair<size_t, size_t>> restrictions = {{1, 2}, {2, 4}, {3, 7}}; 
    size_t k = std::max_element(restrictions.begin(), restrictions.end())->first; 
    if (k == 0) return 0; /* Empty set */ 
    std::vector<size_t> comb(k); 
    std::size_t pfx = 0; 
    do { 
    firstSuffix(comb, pfx); 
    for (auto const& val : comb) std::cout << std::setw(3) << val; 
    std::cout << '\n'; 
    } while (pfx = nextPrefix(comb, restrictions)); 
    return 0; 
} 

(live on coliru)