Algorithme pour obtenir le produit cartésien

Question

J'ai un tableau comme [0,2,3,0,1] en entrée, et j'ai besoin de trouver un produit cartésien de {0}x{0,1,2}x{0,1,2,3}x{0}x{0,1}, plus précisément j'ai besoin d'avoir une sortie comme suit.

---

Entrée:

[0, 2, 3, 0, 1] 

Sortie:

[0, 0, 0, 0, 0] 
[0, 0, 0, 0, 1] 
[0, 0, 1, 0, 0] 
[0, 0, 1, 0, 1] 
[0, 0, 2, 0, 0] 
[0, 0, 2, 0, 1] 
[0, 0, 3, 0, 0] 
[0, 0, 3, 0, 1] 
[0, 1, 0, 0, 0] 
[0, 1, 0, 0, 1] 
[0, 1, 1, 0, 0] 
[0, 1, 1, 0, 1] 
[0, 1, 2, 0, 0] 
[0, 1, 2, 0, 1] 
[0, 1, 3, 0, 0] 
[0, 1, 3, 0, 1] 
[0, 2, 0, 0, 0] 
[0, 2, 0, 0, 1] 
[0, 2, 1, 0, 0] 
[0, 2, 1, 0, 1] 
[0, 2, 2, 0, 0] 
[0, 2, 2, 0, 1] 
[0, 2, 3, 0, 0] 
[0, 2, 3, 0, 1] 

je besoin d'un algorithme général. Une idée ? Je voudrais l'écrire en C++. Merci

Answer 1

Une solution de code dur serait:

for (int a1 : {0}) { 
    for (int a2 : {0,1,2}) { 
    for (int a3 : {0,1,2,3}) { 
     for (int a4 : {0}) { 
     for (int a5 : {0,1}) { 
      do_job(a1, a2, a3, a4, a5); 
     } 
     } 
    } 
    } 
} 

Vous pouvez utiliser le suivant pour une manière générique (mettre tous a s dans le vecteur):

bool increase(const std::vector<std::size_t>& v, std::vector<std::size_t>& it) 
{ 
    for (std::size_t i = 0, size = it.size(); i != size; ++i) { 
     const std::size_t index = size - 1 - i; 
     ++it[index]; 
     if (it[index] > v[index]) { 
      it[index] = 0; 
     } else { 
      return true; 
     } 
    } 
    return false; 
} 

void iterate(const std::vector<std::size_t>& v) 
{ 
    std::vector<std::size_t> it(v.size(), 0); 

    do { 
     do_job(it); 
    } while (increase(v, it)); 
} 

Live Demo

Answer 2

Dans votre exemple, il semblerait que vous vouliez compter avec une base mixte, et votre entrée est la valeur numérique maximale pour chaque position.

Une méthode simple consiste à utiliser le codage arithmétique , en traitant spécialement les positions du chiffre maximum 0. Voici pseudo-code pour le cas sans 0 chiffres max:

input radixes 
let n_numbers = product_of radixes 
for i = 0 to n_numbers-1 inclusive 
    let n = i 
    for digit_pos = 0 to number-of-radixes-1 
     output n mod radix[digit_pos] 
     let n = n div radix[digit_pos] 
    output newline 

Je laisse le traitement de 0 comme max chiffres dans une position, comme un exercice. :)

---

Je ne me souviens pas de la prise en charge particulièrement pertinente pour cela dans la bibliothèque standard C++. C'est à dire. c'est surtout une question indépendante du langage qui n'a rien à voir avec le C++, rien à voir avec les permutations, et rien à voir avec les tableaux. Pourvu que mon interprétation soit correcte: il aurait mieux valu que le problème soit décrit aussi avec des mots, pas seulement un exemple.

Answer 3

La récurrence semble être la manière la plus simple d'aborder ce problème, étant donné que vous ne connaissez peut-être pas la longueur du vecteur d'entrée. Quelque chose comme ceci:

import java.util.ArrayList; 
import java.util.Arrays; 

public class Cartesian { 

    public static void printCartesian(String head, ArrayList<Integer> array) { 
    if (array.size() == 0) { 
     System.out.println(head); 
     return; 
    } 
    if (array.size() == 1) { 
     for (int i = 0; i <= array.get(0); ++i) { 
     System.out.println(head + i + "]"); 
     } 
     return; 
    } 
    // assert array.size() > 1 
    int a0 = array.get(0); 
    ArrayList<Integer> array0 = new ArrayList<Integer>(array); 
    array0.remove(0); 
    for (int i = 0; i <= a0; ++i) { 
     printCartesian(head + i + ", ", array0); 
    } 
    } 

    public static void main(String[] args) { 
    Integer[] input = { 0, 2, 3, 0, 1 }; 
    ArrayList<Integer> array = new ArrayList<Integer>(Arrays.asList(input)); 
    printCartesian("[", array); 
    } 
} 

L'appel initial serait printCartesian("[", a) où a est un ArrayList contenant les éléments de votre tableau en ordre. Une clause if supplémentaire doit être ajoutée pour size == 1 car sinon, une trop grande quantité de virgules est imprimée.

La traduction de ceci en structures de données C++ ne devrait pas être difficile.