Список n-кортежей в C++

Question

Каков способ создания списка n-кортежей в C++? Я хотел бы генерировать, учитывая массив чисел, все возможные п-кортежи элементов из этого массива:

В Mathematica это делается с помощью: например

Tuples[{0, 1, 2}, 3] 

генерирует:

0,0,0 
0,0,1 
0,0,2 
0,1,0 
0,1,1 
0,1,2 
0,2,0 
0,2,1 
0,2,2 
1,0,0 
... 
2,2,2 

В Python это делается с помощью (см How to create N-tuples in Python?)

list(product(range(0, 2), repeat=3)) 

Однако я cá Не знаю, как это сделать на C++. Я хотел бы иметь массив [0,1, ..., num] и генерировать n-кортежей назначенной длины.

Возможно, на C++ можно использовать std :: next_permutation или некоторые вложенные?

Answer 1

Я собираюсь предположить, что ваш вектор чисел уникален.

Вы заметили, как кортежи очень похожи на приращение чисел? Мы можем использовать этот факт для этого.

Во-первых, поймите, что набор, который мы вытягиваем элементы кортежа, в основном образует «цифры» в нашей «системе чисел». Итак, мы знаем, что у нас будет digits^tupleSize кортежей.

Затем мы просто увеличиваем счетчик и вытаскиваем «цифры» со счетчика.

#include <cstddef> 
#include <cstdint> 
#include <vector> 

// Not strictly necessary. You can find other ways to end the loop 
uint32_t ipow(uint32_t base, uint32_t exp) 
{ 
    uint32_t result = 1; 
    while (exp) 
    { 
     if (exp & 1) 
      result *= base; 
     exp >>= 1; 
     base *= base; 
    } 

    return result; 
} 

std::vector<std::vector<uint32_t>> tuples(const std::vector<uint32_t> &set, uint32_t tupleSize) 
{ 
    std::vector<std::vector<uint32_t>> result; 

    uint32_t maxValue = ipow(set.size(), tupleSize); 

    for (uint32_t counter = 0; counter < maxValue; counter++) { 
     std::vector<uint32_t> tuple(tupleSize); 

     uint32_t currentValue = counter; 
     for (size_t i = 0; i < tupleSize; i++) { 
      uint32_t digit = currentValue % set.size(); 
      tuple[tupleSize - i - 1] = set[digit]; 
      currentValue /= set.size(); 
     } 

     result.push_back(tuple); 
    } 

    return result; 
} 

Demo