Trouver toutes les combinaisons de valeur possibles entre deux tableaux

Votre problème est équivalent au problème suivant:

Déclaration de problème: strong>

Compte tenu de deux vecteurs A code> avec la taille n code>, B code> avec la taille m code>, où n .
A = [0, 1, 2, ..., N - 1] Code>.
B = [0, 1, 2, ..., M - 1] Code>.
Trouver tout mappings injectif et non surjectif à partir de A code> à B code>. p>

Solution forte>: de
Comme la taille d'A est plus petite, dans un mappage, le nombre de correspondances est égal à la taille d'A, I.e., n. p>

Ensuite, nous générons toutes les permutations possibles de B, de sorte que les éléments du début N dans chaque permutation peuvent avoir une correspondance à une une à une correspondance avec les éléments de A. p>

les premières permutations et les mappages vont comme suit: p>

Mise en œuvre: strong> p>

class Helper {
public:
    /**
     * @brief generateArray
     * @param size
     * @return A vector [0, 1, ..., size - 1]
     */
    vector<int> generateArray(int size) {
        vector<int> arr;
        for (int i = 0; i < size; ++i) {
            arr.push_back(i);
        }
        return arr;
    }

    /**
     * @brief generateMatches
     * @param n, cardinality of the vector X, where X = [0,1, ..., n - 1].
     * @param m, cardinality of the vector Y, where Y = [0,1, ..., m - 1].
     * @return All possible injective and non-surjective mappings 
     * from the smaller vector to the larger vector.
     */
    vector<vector<pair<int, int> > > generateMatches(int n, int m) {
        // Deal with n > m. Swap back when generating pairs.
        bool swapped = false;
        if (n > m) {
            swapped = true;
            swap(n, m);
        }
        // Now n is smaller or equal to m
        vector<int> A = generateArray(n);
        vector<int> B = generateArray(m);
        vector<vector<pair<int, int> > > matches;
        // Generate all the permutations of m
        do {
            vector<pair<int, int> > match;
            for (int i = 0; i < n; ++i) {
                pair<int, int> p;
                if (swapped) {
                    // Swap back to the original order.
                    p = make_pair(A[i], B[i]);
                } else {
                    p = make_pair(B[i], A[i]);
                }
                match.push_back(p);
            }
            matches.push_back(match);
                // Generate next permutation.
        } while(next_permutaion(B.begin(), B.end())); 
        return matches;
    }
};

J'ai examiné ce défi lorsque j'ai vu un puzzle de style croisé où chaque carré a un numéro et que vous devez trouver quelle lettre correspond à quel numéro afin de rendre les mots corrects. Sachant que je touche des réponses déjà données, je vais essayer de résumer le problème et montrerai comment il peut être résolu de manière récursive.

Dans l'affaire X-Word, le plus petit tableau A est une série de chiffres et le grand Array B contient les lettres de l'alphabet. Le problème est d'attribuer chaque numéro à une lettre et de trouver toutes les combinaisons possibles. Généralement, nous avons: p>

   AllPairs (A,B,C)
    if Size(A)>1             ' check no of elements in A        
      for i=1 to Size(B)
       C(Size(C)-Size(A)+1)= B(i)
       A'=Remove element 1 from A
       B'=Remove element i from B
       Call AllPairs(A',B',C)     'recursive call
      Next i
    else                          ' only one element in A
      for j=1 to Size(B)
      C(Size(C)) = B(i)  'looping last element in C through all unused in B
      Collect.ADD(C)      'collect C-arrays here for later use
      Next j                 
  End AllPairs