Calcul du rang d'une combinaison?

Question

Je souhaite pré-calculer certaines valeurs pour chaque combinaison dans un ensemble de combinaisons. Par exemple, lors du choix de 3 nombres de 0 à 12 ans, je vais calculer une valeur pour chacun:

>>> for n in choose(range(13), 3): 
    print n, foo(n) 

(0, 1, 2) 78 
(0, 1, 3) 4 
(0, 1, 4) 64 
(0, 1, 5) 33 
(0, 1, 6) 20 
(0, 1, 7) 64 
(0, 1, 8) 13 
(0, 1, 9) 24 
(0, 1, 10) 85 
(0, 1, 11) 13 
etc... 

Je veux stocker ces valeurs dans un tableau afin que compte tenu de la combinaison, je peux calculer et obtenir son la valeur. Par exemple:

>>> a = [78, 4, 64, 33] 
>>> a[magic((0,1,2))] 
78 

Que serait magic? Au début, je pensais juste le stocker sous forme de matrice en 3 dimensions de 13 x 13 x 13, donc je peux facilement l'indexer de cette façon. Bien que ce soit correct pour 13 choisir 3, cela aurait beaucoup trop de frais pour quelque chose comme 13 choisir 7.

Je ne veux pas utiliser un dict parce que finalement ce code sera en C, et un tableau serait beaucoup plus efficace de toute façon. MISE À JOUR: J'ai aussi un problème similaire, mais en utilisant des combinaisons avec des répétitions, donc toutes les réponses sur la façon d'obtenir le rang de ceux-ci seraient très appréciées =). MISE À JOUR: Pour être clair, j'essaie de conserver de l'espace. Chacune de ces combinaisons indexe en réalité quelque chose qui prend beaucoup de place, disons 2 kilo-octets. Si je devais utiliser un tableau 13x13x13, ce serait 4 mégaoctets, dont je n'ai besoin que de 572 kilo-octets en utilisant (13 choisir 3).

Answer 1

Voici une réponse conceptuelle et un code basé sur le fonctionnement de la commande lex. (Donc je suppose que ma réponse est comme celle de "moron", sauf que je pense qu'il a trop peu de détails et ses liens ont trop.) J'ai écrit une fonction unchoose(n,S) pour vous qui fonctionne en supposant que S est un sous-ensemble de la liste ordonnée de range(n). L'idée: Soit S contient 0 ou pas. Si c'est le cas, supprimez 0 et calculez l'index pour le sous-ensemble restant. Si elle ne le fait pas, il vient après les binomial(n-1,k-1) sous-ensembles qui ne contiennent 0.

def binomial(n,k): 
    if n < 0 or k < 0 or k > n: return 0 
    b = 1 
    for i in xrange(k): b = b*(n-i)/(i+1) 
    return b 

def unchoose(n,S): 
    k = len(S) 
    if k == 0 or k == n: return 0 
    j = S[0] 
    if k == 1: return j 
    S = [x-1 for x in S] 
    if not j: return unchoose(n-1,S[1:]) 
    return binomial(n-1,k-1)+unchoose(n-1,S) 

def choose(X,k): 
    n = len(X) 
    if k < 0 or k > n: return [] 
    if not k: return [[]] 
    if k == n: return [X] 
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k) 

(n,k) = (13,3) 
for S in choose(range(n),k): print unchoose(n,S),S 

Maintenant, il est vrai aussi que vous pouvez mettre en cache ou les valeurs de hachage des deux fonctions, binomiale et unchoose. Et ce qui est bien, c'est que vous pouvez faire un compromis entre pré-calculer tout et ne rien calculer. Par exemple, vous pouvez précalculer seulement pour len(S) <= 3.

Vous pouvez également optimiser unchoose pour qu'il ajoute les coefficients binomiaux avec une boucle si S[0] > 0, au lieu de décrémenter et d'utiliser la récursion de queue.

Answer 2

Vous pouvez essayer d'utiliser l'index lexicographique de la combinaison. Peut-être que cette page vous aidera: http://saliu.com/bbs/messages/348.html

Cette page MSDN a plus de détails: Generating the mth Lexicographical Element of a Mathematical Combination.

Pour être un peu plus précis:

Lorsqu'ils sont traités comme un tuple, vous pouvez commander les combinaisons lexicographique.

donc (0,1,2) < (0,1,3) < (0,1,4), etc.

que vous aviez le nombre 0 à n-1 et choisi k sur les .

Maintenant, si le premier élément est zéro, vous savez que c'est un parmi le premier n-1 choisissez k-1.

Si le premier élément est 1, alors c'est l'un parmi les n-2 suivants, choisissez k-1. De cette façon, vous pouvez calculer récursivement la position exacte de la combinaison donnée dans l'ordre lexicographique et l'utiliser pour la mapper à votre numéro.

Cela fonctionne aussi en inverse et la page MSDN explique comment faire cela.

Answer 3

Utilisez une table de hachage pour stocker les résultats. Une fonction de hachage décente pourrait être quelque chose comme:

h(x) = (x1*p^(k - 1) + x2*p^(k - 2) + ... + xk*p^0) % pp

Où x1 ... xk sont les numéros dans votre combinaison (par exemple (0, 1, 2) a x1 = 0, x2 = 1, x3 = 2) et p et pp sont des nombres premiers.

Donc vous stockez Hash[h(0, 1, 2)] = 78 et ensuite vous le récupéreriez de la même manière.

Remarque: la table de hachage est juste un tableau de taille pp, pas un dict.

Answer 4

Je suggère une table de hachage spécialisée. Le hachage pour une combinaison doit être l'exclusif - ou des hachages pour les valeurs. Les hachages pour les valeurs sont essentiellement des modèles de bits aléatoires. Vous pouvez coder la table pour faire face aux collisions, mais il devrait être assez facile de dériver un schéma de hachage parfait minimal - un où deux combinaisons de trois éléments ne donnent pas la même valeur de hachage, et où la table de hachage et la table -size sont gardés à un minimum.

Il s'agit en gros de Zobrist hashing - pensez à un "déplacement" en ajoutant ou en supprimant un élément de la combinaison.

EDIT

La raison d'utiliser une table de hachage est que le rendement de conversion O (n) où n est le nombre d'éléments dans la combinaison (en supposant qu'aucune collision). Le calcul des index lexicographiques dans les combinaisons est significativement plus lent, IIRC.

L'inconvénient est évidemment le travail initial effectué pour générer la table.

Answer 5

Pour l'instant, je suis arrivé à un compromis: j'ai un tableau de 13x13x13 qui mappe juste pour l'indice de la combinaison, en prenant 13x13x13x2 octets = 4 kilo-octets (en utilisant ints courts), ainsi que la taille normale (13 choisir 3) * 2 kilooctets = 572 kilooctets, pour un total de 576 kilooctets. Beaucoup mieux que 4 mégaoctets, et aussi plus rapide qu'un calcul de rang! Je l'ai fait en partie parce que je n'arrivais pas à faire fonctionner la réponse de Moron. C'est aussi plus extensible - j'ai un cas où j'ai besoin de combinaisons avec des répétitions, et je n'ai pas encore trouvé le moyen d'en calculer le rang.

Answer 6

Ce que vous voulez est appelé combinadics.Voici ma mise en œuvre de ce concept, en Python:

def nthresh(k, idx): 
    """Finds the largest value m such that C(m, k) <= idx.""" 
    mk = k 
    while ncombs(mk, k) <= idx: 
    mk += 1 
    return mk - 1 


def idx_to_set(k, idx): 
    ret = [] 
    for i in range(k, 0, -1): 
    element = nthresh(i, idx) 
    ret.append(element) 
    idx -= ncombs(element, i) 
    return ret 


def set_to_idx(input): 
    ret = 0 
    for k, ck in enumerate(sorted(input)): 
    ret += ncombs(ck, k + 1) 
    return ret 

Answer 7

J'ai écrit une classe pour gérer des fonctions communes pour travailler avec le coefficient binomial, qui est le type de problème que votre problème relève. Il exécute les tâches suivantes:

1. Génère tous les K-index dans un format agréable pour tout N choisir K dans un fichier. Les index K peuvent être remplacés par des chaînes ou des lettres plus descriptives. Cette méthode rend la résolution de ce type de problème assez triviale.

2. Convertit les index K en l'index approprié d'une entrée dans la table de coefficients binomiaux triés. Cette technique est beaucoup plus rapide que les anciennes techniques publiées qui reposent sur l'itération et n'utilisent pas beaucoup de mémoire. Il le fait en utilisant une propriété mathématique inhérente au triangle de Pascal. Mon article parle de cela. Je crois que je suis le premier à découvrir et à publier cette technique, mais je peux me tromper.

3. Convertit l'index dans une table de coefficients binomiaux triés en les index K correspondants.

4. Utilise Mark Dominus méthode pour calculer le coefficient binomial, qui est beaucoup moins susceptible de déborder et fonctionne avec des nombres plus grands.

5. La classe est écrite en .NET C# et fournit un moyen de gérer les objets liés au problème (le cas échéant) en utilisant une liste générique. Le constructeur de cette classe prend une valeur bool appelée InitTable qui, lorsqu'elle est vraie, créera une liste générique pour contenir les objets à gérer. Si cette valeur est false, la table ne sera pas créée. La table n'a pas besoin d'être créée pour exécuter les 4 méthodes ci-dessus. Des méthodes d'accès sont fournies pour accéder à la table.

6. Il existe une classe de test associée qui montre comment utiliser la classe et ses méthodes. Il a été largement testé avec 2 cas et il n'y a pas de bugs connus.

Pour en savoir plus sur cette classe et télécharger le code, voir Tablizing The Binomial Coeffieicent.

Il ne devrait pas être difficile de convertir cette classe en C++.