Я обнаружил, что использование рекурсивной функции не годится для больших длин и целых чисел, поскольку она отнимает слишком много оперативной памяти, а использование функции генератора / возобновляемости (которая выдает значения) слишком медленное и требует большой библиотеки длясделать это кроссплатформенным.
Итак, вот нерекурсивное решение на C ++, которое создает разделы в отсортированном порядке (что также идеально подходит для перестановок).Я обнаружил, что это в 10 раз быстрее, чем, казалось бы, умных и кратких рекурсивных решений, которые я пробовал для длин разделов 4 или больше, но для длин 1-3 производительность не обязательно лучше (и мне не нужны короткиедлины, потому что они бывают быстрыми при любом подходе).
// Inputs
unsigned short myInt = 10;
unsigned short len = 3;
// Partition variables.
vector<unsigned short> partition(len);
unsigned short last = len - 1;
unsigned short penult = last - 1;
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3.
unsigned short sum = 0;
// Prefill partition with 0.
fill(partition.begin(), partition.end(), 0);
do {
// Calculate remainder.
partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints.
/*
*
* DO SOMETHING WITH "partition" HERE.
*
*/
if (partition[cur + 1] <= partition[cur] + 1) {
do {
cur--;
} while (
cur > 0 &&
accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt
);
// Escape if seeked behind too far.
// I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3.
if (cur < 0) {
break;
}
// Increment the new cur position.
sum++;
partition[cur]++;
// The value in each position must be at least as large as the
// value in the previous position.
for (unsigned short i = cur + 1; i < last; ++i) {
sum = sum - partition[i] + partition[i - 1];
partition[i] = partition[i - 1];
}
// Reset cur for next time.
cur = penult;
}
else {
sum++;
partition[penult]++;
}
} while (myInt - sum >= partition[penult]);
Где я написал ДЕЛАЙТЕ ЧТО-ЛИБО С «разделом» ЗДЕСЬ. - это место, где вы на самом деле потребляете значение.(На последней итерации код продолжит выполнение оставшейся части цикла, но я обнаружил, что это лучше, чем постоянная проверка условий выхода - он оптимизирован для более крупных операций)
0,0,10
0,1,9
0,2,8
0,3,7
0,4,6
0,5,5
1,1,8
1,2,7
1,3,6
1,4,5
2,2,6
2,3,5
2,4,4
3,3,4
О, я использовал "unsigned short", потому что я знаю, что моя длина и целое число не превысят определенные пределы, измените это, если это не подходит для вас :) Проверьте комментарии;одна переменная там (cur) должна была быть подписана для обработки длины 1 или 2, и есть соответствующий if-оператор, который идет с этим, и я также отметил в комментарии, что если ваш вектор разбиения имеет подписанные целые, есть другая строкаэто можно упростить.
Чтобы получить все композиции, в C ++ я бы использовал эту простую стратегию перестановок, которая, к счастью, не дает дубликатов:
do {
// Your code goes here.
} while (next_permutation(partition.begin(), partition.end()));
Гнездо, которое в ДЕЛАЙТЕ ЧТО-ТО С «разделом» ЗДЕСЬ spot, и все готово.
Альтернатива поиску композиций (на основе Java-кода здесь https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) заключается в следующем. IВы обнаружили, что это работает лучше, чем next_permutation ().
// Process lexicographic permutations of partition (compositions).
composition = partition;
do {
// Your code goes here.
// Find longest non-increasing suffix
i = last;
while (i > 0 && composition[i - 1] >= composition[i]) {
--i;
}
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0) {
break;
}
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
j = last;
while (composition[j] <= composition[i - 1])
--j;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
temp = composition[i - 1];
composition[i - 1] = composition[j];
composition[j] = temp;
// Reverse the suffix
j = last;
while (i < j) {
temp = composition[i];
composition[i] = composition[j];
composition[j] = temp;
++i;
--j;
}
} while (true);
Там вы заметите некоторые необъявленные переменные, просто объявите их ранее в коде перед всеми вашими циклами: i, j, pos и temp (шорты без знака) и composition (того же типа и длины, что и partition). Вы можете повторно использовать объявление i для его использования в цикле for в разделахтрескаэлектронный фрагмент.Также обратите внимание на используемые переменные, такие как last, которые предполагают, что этот код вложен в код разделов, указанный ранее.
Снова "Ваш код идет сюда" - это место, где вы используете композицию для своих собственных целей.
Для справки вот мои заголовки.
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;
Несмотря на значительное увеличение скорости с использованием этих подходов, для любых значительных целых чисел и длин разделов это все равно заставит вас злиться на ваш процессор:)