Parfait hachage minimal pour les combinaisons mathématiques

il existe un algorithme pour coder et décoder une combinaison dans son numéro dans l'ordre lexicographique de toutes les combinaisons avec un fixe donné K . L'algorithme est linéaire à N pour le code et le décodage de la combinaison. Quelle est la langue qui vous intéresse?

EDIT: voici un exemple de code en c++(il crée le numéro lexicographique d'une combinaison dans la séquence de toutes les combinaisons d'éléments n par opposition à ceux avec k éléments mais est vraiment bon point de départ):

typedef long long ll;

// Returns the number in the lexicographical order of all combinations of n numbers
// of the provided combination. 
ll code(vector<int> a,int n)
{
    sort(a.begin(),a.end());
    int cur = 0;
    int m = a.size();

    ll res =0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i] == cur+1)
        {
            res++;
            cur = a[i];
            continue;
        }
        else
        {
            res++;
            int number_of_greater_nums = n - a[i];
            for(int j = a[i]-1,increment=1;j>cur;j--,increment++)
                res += 1LL << (number_of_greater_nums+increment);
            cur = a[i];
        }
    }
    return res;
}
// Takes the lexicographical code of a combination of n numbers and returns the 
// combination
vector<int> decode(ll kod, int n)
{
    vector<int> res;
    int cur = 0;

    int left = n; // Out of how many numbers are we left to choose.
    while(kod)
    {
        ll all = 1LL << left;// how many are the total combinations
        for(int i=n;i>=0;i--)
        {
            if(all - (1LL << (n-i+1)) +1 <= kod)
            {
                res.push_back(i);
                left = n-i;
                kod -= all - (1LL << (n-i+1)) +1;
                break;
            }
        }
    }
    return res;
}

je suis désolé, j'ai un algorithme pour le problème que vous demandez pour l'instant, mais je crois que ce sera un bon exercice pour essayer de comprendre ce que je fais ci-dessus. La vérité est que c'est l'un des algorithmes j'enseigne dans le cadre du cours "Conception et analyse d'algorithmes" et c'est pourquoi je l'avais pré-écrit.

C'est ce dont vous (et moi) avez besoin:

hash() cartes k-tuples à partir de [1..n] sur le jeu 1..C(n,k)\subset N . L'effort est k soustractions (et O(k) est une limite inférieure de toute façon, voir la remarque de Strandjev ci-dessus):

// bino[n][k] is (n "over" k) = C(n,k) = {n \choose k}
// these are assumed to be precomputed globals

int hash(V a,int n, int k) {// V is assumed to be ordered, a_k<...<a_1
  // hash(a_k,..,a_2,a_1) = (n k) - sum_(i=1)^k (n-a_i   i) 
  // ii is "inverse i", runs from left to right

  int res = bino[n][k];
  int i;

  for(unsigned int ii = 0; ii < a.size(); ++ii) {
    i = a.size() - ii;   
    res = res - bino[n-a[ii]][i];
  }
  return res;
}

si vous cherchez un moyen d'obtenir l'indice lexicographique ou le rang d'une combinaison unique, alors votre problème tombe sous le coefficient binomial. Le coefficient binomial traite des problèmes de choix des combinaisons uniques dans les groupes de K avec un total de N articles.

j'ai écrit une classe en C# pour gérer les fonctions communes pour travailler avec le coefficient binomial. Il exécute les tâches suivantes:

1. Produit tous les K-indexes dans un format agréable pour n choisir K à un fichier. Les index K peuvent être remplacés par des chaînes ou des lettres descriptives.

2. convertit les indices-K à l'indice lexicographique approprié ou au rang d'une entrée dans la table des coefficients binomiaux triés. Cette technique est beaucoup plus rapide que les anciennes techniques publiées qui reposent sur l'itération. Il le fait en utilisant une propriété mathématique inhérente au Triangle de Pascal et est très efficace comparé à itérer sur l'ensemble.

3. convertit l'indice dans un tableau de coefficients binomiaux triés aux Index-K correspondants. Je crois que c'est aussi plus rapide que les anciennes solutions itératives.

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 dans .NET C# et fournit un moyen de gérer les objets liés au problème (s'il y en a) en utilisant une liste générique. Le constructeur de cette classe prend une valeur bool appelée InitTable qui quand true créera une liste générique pour contenir les objets à gérer. Si cette valeur est fausse, alors elle ne créera pas la table. Il n'est pas nécessaire de créer le tableau pour utiliser les 4 méthodes ci-dessus. Les méthodes Accessor sont fournies pour accéder à la table.

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

pour en savoir plus sur cette classe et télécharger le code, voir Tabliant le coefficient Binomial .

le code testé suivant sera itéré à travers chaque combinaison unique:

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 10;  // Total number of elements in the set.
   int K = 5;  // Total number of elements in each group.
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination.  
      BC.GetKIndexes(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

vous devriez être en mesure de porter cette classe sur assez facilement à la langue de votre choix. Vous n'aurez probablement pas à Porto sur la partie générique de la classe pour accomplir vos objectifs. Selon le nombre de combinaisons que vous travaillez, vous pourriez avoir besoin d'utiliser une plus grande taille de mot de 4 octets entiers.