Comment générer le produit cartésien d'un tableau avec lui-même en C?

Question

J'ai du mal à trouver un moyen d'obtenir le produit cartésien d'un tableau et de spécifier combien de fois. Ceci est un exemple de ce que je veux faire (pseudocode):

int arr = {0, 1, 2, 3}; 
int n = 2; 

int[][] result = cartesian(arr, n); 
//result would be {{0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0},..., {3, 3}} 

n = 3; 
result = cartesian(arr, n); 
//since n is now 3, result would be{{0, 0, 0}, {0, 0, 1},..., {3, 3, 3}} and so on. 

aide serait grandement apprécié

Answer 1

La meilleure façon de le faire est récursive. Si vous avez une séquence de taille N et que vous souhaitez trouver le produit cartésien de Kème ordre avec lui-même, il y a des éléments N^K à générer. Voici quelques pseudo-codes pour vous aider à démarrer:

generate_helper(A, k, C, S): 
    if k = 0: 
     C.append(S) 
    else: 
     for each a in A: 
      S.push(a) 
      generate_helper(A, k - 1, C, S) 
      S.pop() 

generate(A, k): 
    C := {} -- Empty collection of sequences of order k. 
    S := {} -- Empty sequence of elements 
    generate_helper(A, k, C, S) 
    return C 

Ici, ceci générera récursivement tous les éléments. Pour générer les séquences de longueur k, on choisit d'abord un élément, on le fixe et on génère toutes les séquences possibles de longueur k-1 en commençant par l'élément choisi. Si nous faisons cela pour tous les éléments de la séquence, nous aurions généré tous les éléments du produit cartésien.

Maintenant, puisque vous avez le pseudo-code, j'espère qu'il devrait être routinier pour l'implémenter. :)

Answer 2

Sans récursion :) En C++ 11 vous le feriez comme celui-ci (où cartesian() est la fonction que vous voulez)

#include <deque> 
#include <iostream> 
using namespace std; 

void add_all_once(deque<deque<int>>& result, const deque<int>& vec, int which) { 
    for (decltype(vec.size()) i = 0; i < vec.size(); ++i) { 
     deque<int> to_be_pushed = result[which]; 
     to_be_pushed.push_back(vec[i]); 
     result.emplace_back(std::move(to_be_pushed)); 
    } 
} 

deque<deque<int>> cartesian(const deque<int>& vec, int n) { 
    deque<deque<int>> cartesian_product; 
    decltype(vec.size()) size = vec.size(); 

    // Fill 1 dimension 
    for (decltype(vec.size()) i = 0; i < size; ++i) { 
     cartesian_product.push_back(deque<int>({vec[i]})); 
    } 

    // Fill all possibilities once 
    for (int i = 0; i < n; ++i) { 
     decltype(cartesian_product.size()) current_size = cartesian_product.size(); 

     for (decltype(cartesian_product.size()) j = 0; j < current_size; ++j) { 
      add_all_once(cartesian_product, vec, j); 
     } 

     for (decltype(cartesian_product.size()) j = 0; j < current_size; ++j) { 
      cartesian_product.pop_front(); 
     } 
    } 


    return cartesian_product; 
} 

int main() { 
    deque<int> vec = {1, 2, 3}; 

    auto n = 2; 
    auto return_val = cartesian(vec, n); 

    for (int i = 0; i < return_val.size(); ++i) { 
     for (int j = 0; j < return_val.at(i).size(); ++j) { 
      cout << return_val[i][j] << ' '; 
     } cout << endl; 
    } 

    return 0; 
} 

Answer 3

Vous essayez de générer le produit cartésien k fois d'un mettre avec soi-même. Ceci est fondamentalement équivalent au k-combinations of the set with repetitions. Il existe un algorithme simple from Rosetta Code mettre en œuvre ce dans C:

#include <stdio.h> 

const char * donuts[] = { "iced", "jam", "plain", "something completely different" }; 

long choose(int * got, int n_chosen, int len, int at, int max_types) 
{ 
     int i; 
     long count = 0; 
     if (n_chosen == len) 
     { 
       if (!got) return 1; 

       for (i = 0; i < len; i++) 
       { 
         printf("%s\t", donuts[got[i]]); 
       } 
       printf("\n"); 
       return 1; 
     } 

     for (i = at; i < max_types; i++) 
     { 
       if (got) got[n_chosen] = i; 
       count += choose(got, n_chosen + 1, len, i, max_types); 
     } 
     return count; 
} 

int main() 
{ 
     int chosen[3]; 
     choose(chosen, 0, 2, 0, 3); 

     printf("\nWere there ten donuts, we'd have had %ld choices of three\n", 
       choose(0, 0, 3, 0, 10)); 
     return 0; 
} 

Sortie:

iced iced 

iced jam 
iced plain 
jam  jam 
jam  plain 
plain plain 

Were there ten donuts, we'd have had 220 choices of three 

Vous pouvez modifier facilement que cela fonctionne sur les tableaux de nombres au lieu de chaînes de style C.