Алгоритм получения декартового произведения
У меня есть массив как [0,2,3,0,1] и мне нужно найти декартово произведение {0}x{0,1,2}x{0,1,2,3}x{0}x{0,1}Точнее мне нужно иметь вывод, как показано ниже.
Входные данные:
[0, 2, 3, 0, 1]
Выход:
[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]
Мне нужен общий алгоритм. Любая идея ? Я хотел бы написать это на C ++.
Спасибо
Решение
Решение жесткого кода будет:
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);
}
}
}
}
}
Вы можете использовать следующие для общего способа (положить все as в вектор):
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));
}
Другие решения
Из вашего примера кажется, что вы хотите считать со смешанным основанием, и ваш ввод — это максимальное значение цифры для каждой позиции.
Простой способ заключается в использовании арифметическое кодирование, специально обрабатывать максимальную цифру 0 позиций. Вот псевдокод для случая без 0 максимальных цифр:
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
Я оставляю обработку 0 как максимальную цифру в позиции, как упражнение. 🙂
Я не могу вспомнить какую-либо особенно актуальную поддержку для этого в стандартной библиотеке C ++. То есть это в основном независимый от языка вопрос, который не имеет ничего общего с C ++, не имеет ничего общего с перестановками и не имеет ничего общего с массивами. При условии, что моя интерпретация верна: было бы лучше, если бы проблема была описана также словами, а не просто примером.
Рекурсия кажется самым простым способом решения этой проблемы, учитывая, что вы можете не знать длину входного вектора. Что-то вроде этого:
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);
}
}
Первоначальный вызов будет printCartesian("[", a) где a ArrayList, содержащий элементы вашего массива по порядку. Дополнительный if пункт должен быть добавлен для size == 1 потому что в противном случае печатается слишком много запятых.
Перевод этого в структуры данных C ++ не должен быть сложным.