Permutations avec restrictions supplémentaires

Question

J'ai un ensemble d'éléments, par exemple: {1,1,1,2,2,3,3,3}, et un ensemble d'ensembles restrictif, par exemple {{3}, { 1,2}, {1,2,3}, {1,2,3}, {1,2,3}, {1,2,3}, {2,3}, {2,3}. Je cherche des permutations d'éléments, mais le premier élément doit être 3, et le second doit être 1 ou 2, etc.

Une telle permutation qui correspond est: {3,1,1,1,2, 2,3}

Existe-t-il un algorithme pour compter toutes les permutations pour ce problème en général? Y a-t-il un nom pour ce type de problème?

Par exemple, je sais comment résoudre ce problème pour certains types de "jeux de restriction". Ensemble d'items: {1,1,2,2,3}, Restrictions {{1,2}, {1,2,3}, {1,2,3}, {1,2}, {1, 2}}. C'est égal à 2!/(2-1)!/1! * 4!/2!/2 !. Permuter efficacement les 3 premiers, puisque c'est le plus restrictif puis permuter les éléments restants où il y a de la place.

Aussi ... temps polynomial. Est-ce possible?

MISE À JOUR: Ceci est discuté plus loin dans les liens ci-dessous. Le problème ci-dessus est appelé "comptage des appariements parfaits" et chaque restriction de permutation ci-dessus est représentée par un {0,1} sur une matrice de fentes aux occupants.

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots

Answer 1

Toutes les autres solutions sont ici exponentielles, même dans les cas où elles ne sont pas nécessaires. Ce problème présente une sous-structure similaire, et devrait donc être résolu avec une programmation dynamique.

Ce que vous voulez faire est d'écrire une classe qui memoizes solutions: sous-problèmes

class Counter { 
    struct Problem { 
    unordered_multiset<int> s; 
    vector<unordered_set<int>> v; 
    }; 

    int Count(Problem const& p) { 
    if (m.v.size() == 0) 
     return 1; 
    if (m.find(p) != m.end()) 
     return m[p]; 
    // otherwise, attack the problem choosing either choosing an index 'i' (notes below) 
    // or a number 'n'. This code only illustrates choosing an index 'i'. 
    Problem smaller_p = p; 
    smaller_p.v.erase(v.begin() + i); 
    int retval = 0; 
    for (auto it = p.s.begin(); it != p.s.end(); ++it) { 
     if (smaller_p.s.find(*it) == smaller_p.s.end()) 
     continue; 
     smaller_p.s.erase(*it); 
     retval += Count(smaller_p); 
     smaller_p.s.insert(*it);  
    } 
    m[p] = retval; 
    return retval; 
    } 

    unordered_map<Problem, int> m; 
}; 

Le code illustre le choix d'un indice i, qui devrait être choisi à un endroit où il y a des v [i] .Size() est petite. L'autre option consiste à choisir un nombre n, qui devrait être un pour lequel il y a peu d'endroits où il peut être placé. Je dirais que le minimum des deux facteurs décisifs devrait gagner.

De plus, vous devrez définir une fonction de hachage pour le problème - cela ne devrait pas être trop dur en utilisant le hachage de boost.

Cette solution peut être améliorée en remplaçant le vecteur par un ensemble <>, et en définissant un opérateur < pour unordered_set. Cela va réduire beaucoup plus de sous-problèmes identiques en un seul élément de la carte, et réduire encore plus l'explosion exponentielle.

Cette solution peut être encore améliorée en rendant les instances de problèmes identiques, sauf que les nombres sont réorganisés en hachage à la même valeur et comparés pour être identiques.

Answer 2

Vous pourriez envisager une solution récursive qui utilise un pool de chiffres (dans l'exemple que vous fournissez, il serait initialisé à {1,1, 1,2,2,3,3,3}, et décide, à l'index donné en paramètre, quel chiffre placer à cet index (en utilisant, bien sûr, les restrictions que vous fournissez).

Si vous le souhaitez, je peux fournir un pseudo-code.

Answer 3

Vous pouvez construire un arbre. Niveau 0: Créer un nœud racine. Niveau 1: Ajoute chaque élément du premier "ensemble restrictif" en tant qu'enfant de la racine. Niveau 2: Ajoute chaque élément du second ensemble restrictif en tant qu'enfants de chacun des nœuds de niveau 1. Niveau 3: Ajouter chaque élément du troisième ensemble restrictif en tant qu'enfants de chacun des nœuds de niveau 2. ...

Le nombre de permutation est alors le nombre de nœuds feuilles de l'arbre final.

Modifier

On ne sait pas ce que l'on entend par "l'ensemble des éléments" {1,1,1,2,2,3,3,3}. Si cela est destiné à limiter le nombre de fois chaque valeur peut être utilisée (« 1 » peut être utilisé 3 fois, « 2 » deux fois, etc.), alors nous avons besoin d'une étape supplémentaire:

• Avant l'ajout d'un nœud l'arborescence, supprime les valeurs utilisées sur le chemin actuel de l'ensemble des éléments. Si la valeur que vous souhaitez ajouter est toujours disponible (par exemple, vous voulez ajouter un "1" et "1" n'a été utilisé que deux fois), ajoutez-la à l'arborescence.

Answer 4

Pour économiser de l'espace, vous pouvez créer un graphique orienté à la place d'un arbre.

• Créez un noeud racine.
• Créez un noeud pour chaque élément dans le premier ensemble et liez de la racine à les nouveaux noeuds.
• Créez un noeud pour chaque élément dans le deuxième ensemble , et reliez chaque premier élément à chaque deuxième élément défini.
• ...

Le nombre de permutations est alors le nombre de chemins à partir du nœud racine aux noeuds de l'ensemble final.